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