冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動(dòng)要復(fù)雜，冒泡排序需要3個(gè)賦值操作，而插入排序只需要1個(gè)。因此，插入排序比冒泡排序在性能方面更優(yōu)。
一、時(shí)間復(fù)雜度為O(n^2)排序算法
時(shí)間復(fù)雜度為O(n^2)的排序算法：
冒泡排序、插入排序、希爾排序、選擇排序
二、冒泡排序
冒泡排序(Bubble Sort)，又被稱(chēng)為氣泡排序或泡沫排序。
它會(huì)遍歷若干次需要排序的數(shù)列，每次遍歷時(shí)，它都會(huì)從前往后依次的比較相鄰兩個(gè)數(shù)的大小；如果前者比后者大，則交換它們的位置。
這樣，一次遍歷之后，最大的元素就在數(shù)列的末尾！
采用相同的方法再次遍歷時(shí)，第二大的元素就被排列在最大元素之前。
重復(fù)此操作，直到整個(gè)數(shù)列都有序?yàn)橹梗?/p>
private static void bubbleSortBySorted(int[] a){
if(a == null || a.length < 2){
return;
}
//若不交換值，則表示已排序好，結(jié)束比較
boolean isSorted = true;
//表示每輪比較的終止點(diǎn)，已排序好的不需要再比較
int sortBorder = a.length - 1;
//每輪比較最后一次交換的下標(biāo)
int lastExchangeIndex = 0;
//因?yàn)橛衋.length個(gè)元素，所以需要循環(huán)a.length-1輪
for(int i = 0; i < a.length-1; i++){
for(int j = 0; j < sortBorder; j++){
//前者大于后者，則想換交換值，將前者大的值往后移
if(a[j] > a[j+1]){
swap(a[j],a[j+1]);
lastExchangeIndex = j;
isSorted = false;
}
}
//每輪最后一次交換的下標(biāo)，表示其后面都已排序好，就是下一輪比較的終止點(diǎn)
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
}
}
//相互交互值
public static void swap(int a,int b){
int temp = a;
a = b;
b = temp;
}二、插入排序
插入排序是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入，類(lèi)似于摸牌時(shí)對(duì)撲克牌的排序。
private static void insertSort2(int[]a){
if(a == null || a.length < 2){
return;
}
//有a.length個(gè)元素，需要比較a.length-1輪
//已排序區(qū)默認(rèn)是下標(biāo)0，未排序區(qū)從下標(biāo)1開(kāi)始
for(int i = 1; i < a.length; i++){
//記錄待插入的元素
int temp = a[i];
int j = i;
//若前面已排序元素大于待插入元素，則排序元素往后移，給待插入的元素騰位置
for( ; j >= 1 && a[j-1] > temp; j--){
a[j] = a[j-1];
}
//待插入元素放到合適位置
a[j] = temp;
}
}三、希爾排序
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；
隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
public static void shellSort(int[] a) {
//增量gap代表同組元素間距，也代表有多少組
//初始分為arr.length / 2組，每次減半直至分為1組，進(jìn)行最后一次排序結(jié)束
for(int gap = a.length/2; gap > 0; gap /=2){
//插入排序（同組間距為gap）
//非排序區(qū)從gap開(kāi)始
for(int i = gap; i < a.length; i++){
//記錄待插入的元素
int temp = a[i];
int j = i;
//若前面gap間距已排序元素大于待插入元素
//則已排序元素往后移gap間距，給待插入的元素騰位置
for(;j >= gap && a[j-gap] > temp;j -= gap){
a[j] = a[j-gap];
}
//
a[j] = temp;
}
}
}四、選擇排序
選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類(lèi)似插入排序，也分已排序區(qū)間和未排序區(qū)間。
但是選擇排序每次會(huì)從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。
public void selectSort2(int[] a){
if(a == null || a.length < 2){
return;
}
//進(jìn)行a.length-1次選擇,最后一個(gè)元素不需要再選擇比較
for(int i = 0; i < a.length; i++){
int minIndex = i;
//從無(wú)序區(qū)選取最小元素的下標(biāo)
for(int j = i + 1; j < a.length; j++){
if(a[j] < a[minIndex]){
minIndex = j;
}
}
//無(wú)序區(qū)最小元素放到有序區(qū)
if(i != minIndex){
swap(a[i],a[minIndex]);
}
}
}五、比較
選擇排序是非穩(wěn)定排序，每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。
比如5，8，5，2，9這樣一組數(shù)據(jù)，使用選擇排序算法來(lái)排序的話(huà)，第一次找到最小元素2，與第一個(gè)5交換位置，那第一個(gè)5和中間的5順序就變了，所以就不穩(wěn)定了。正是因此，相對(duì)于冒泡排序和插入排序，選擇排序就稍微遜色了。
冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動(dòng)要復(fù)雜，冒泡排序需要3個(gè)賦值操作，而插入排序只需要1個(gè)。因此，插入排序比冒泡排序在性能方面更優(yōu)。
希爾排序是對(duì)直接插入排序算法更進(jìn)一步優(yōu)化的版本，平均時(shí)間復(fù)雜度為O(n^1.3)，性能更優(yōu)，但是屬于非穩(wěn)定排序。
這四種算法排序，對(duì)于小規(guī)模數(shù)據(jù)的排序，用起來(lái)非常高效。但是在大規(guī)模數(shù)據(jù)排序的時(shí)候，這個(gè)時(shí)間復(fù)雜度還是稍微有點(diǎn)高，所以我們更傾向于用后面要講的時(shí)間復(fù)雜度為O(nlogn)的排序算法。
