1、冒泡排序
這個名詞的由來很好理解，一般河水中的冒泡，水底剛冒出來的時(shí)候是比較小的，隨著慢慢向水面浮起會逐漸增大，這物理規(guī)律我不作過多解釋，大家只需要了解即可。
冒泡算法的運(yùn)作規(guī)律如下：
①、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
②、對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)（也就是第一波冒泡完成）。
③、針對所有的元素重復(fù)以上的步驟，除了最后一個。
④、持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
代碼如下：
package com.ys.sort;
public class BubbleSort {
public static int[] sort(int[] array){
//這里for循環(huán)表示總共需要比較多少輪
for(int i = 1 ; i < array.length; i++){
//設(shè)定一個標(biāo)記，若為true，則表示此次循環(huán)沒有進(jìn)行交換，也就是待排序列已經(jīng)有序，排序已經(jīng)完成。
boolean flag = true;
//這里for循環(huán)表示每輪比較參與的元素下標(biāo)
//對當(dāng)前無序區(qū)間array[0......length-i]進(jìn)行排序
//j的范圍很關(guān)鍵，這個范圍是在逐步縮小的,因?yàn)槊枯啽容^都會將最大的放在右邊
for(int j = 0 ; j < array.length-i ; j++){
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = false;
}
}
if(flag){
break;
}
//第 i輪排序的結(jié)果為
System.out.print("第"+i+"輪排序后的結(jié)果為:");
display(array);
}
return array;
}
//遍歷顯示數(shù)組
public static void display(int[] array){
for(int i = 0 ; i < array.length ; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?quot;);
display(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("經(jīng)過冒泡排序后的數(shù)組順序?yàn)椋?quot;);
display(array);
}
}
結(jié)果如下：
本來應(yīng)該是 8 輪排序的，這里我們只進(jìn)行了 7 輪排序，因?yàn)榈?7 輪排序之后已經(jīng)是有序數(shù)組了。
冒泡排序解釋：
冒泡排序是由兩個for循環(huán)構(gòu)成，第一個for循環(huán)的變量 i 表示總共需要多少輪比較，第二個for循環(huán)的變量 j 表示每輪參與比較的元素下標(biāo)【0,1，......，length-i】，因?yàn)槊枯啽容^都會出現(xiàn)一個最大值放在最右邊，所以每輪比較后的元素個數(shù)都會少一個，這也是為什么 j 的范圍是逐漸減小的。相信大家理解之后快速寫出一個冒泡排序并不難。
冒泡排序性能分析：
假設(shè)參與比較的數(shù)組元素個數(shù)為 N，則第一輪排序有 N-1 次比較，第二輪有 N-2 次，如此類推，這種序列的求和公式為：
（N-1）+（N-2）+...+1 = N*（N-1）/2
當(dāng) N 的值很大時(shí)，算法比較次數(shù)約為 N2/2次比較，忽略減1。
假設(shè)數(shù)據(jù)是隨機(jī)的，那么每次比較可能要交換位置，可能不會交換，假設(shè)概率為50%，那么交換次數(shù)為 N2/4。不過如果是最壞的情況，初始數(shù)據(jù)是逆序的，那么每次比較都要交換位置。
交換和比較次數(shù)都和N2 成正比。由于常數(shù)不算大 O 表示法中，忽略 2 和 4，那么冒泡排序運(yùn)行都需要 O(N2) 時(shí)間級別。
其實(shí)無論何時(shí)，只要看見一個循環(huán)嵌套在另一個循環(huán)中，我們都可以懷疑這個算法的運(yùn)行時(shí)間為 O(N2)級，外層循環(huán)執(zhí)行 N 次，內(nèi)層循環(huán)對每一次外層循環(huán)都執(zhí)行N次（或者幾分之N次）。這就意味著大約需要執(zhí)行N2次某個基本操作。私信我，回復(fù)：學(xué)習(xí)，獲取免費(fèi)學(xué)習(xí)資源包。
2、選擇排序
選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最小的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
分為三步：
①、從待排序序列中，找到關(guān)鍵字最小的元素
②、如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換
③、從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)、(2)步，直到排序結(jié)束
代碼如下：
package com.ys.sort;
public class ChoiceSort {
public static int[] sort(int[] array){
//總共要經(jīng)過N-1輪比較
for(int i = 0 ; i < array.length-1 ; i++){
int min = i;
//每輪需要比較的次數(shù)
for(int j = i+1 ; j < array.length ; j++){
if(array[j]<array[min]){
min = j;//記錄目前能找到的最小值元素的下標(biāo)
}
}
//將找到的最小值和i位置所在的值進(jìn)行交換
if(i != min){
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
//第 i輪排序的結(jié)果為
System.out.print("第"+(i+1)+"輪排序后的結(jié)果為:");
display(array);
}
return array;
}
//遍歷顯示數(shù)組
public static void display(int[] array){
for(int i = 0 ; i < array.length ; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args){
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?quot;);
display(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("經(jīng)過選擇排序后的數(shù)組順序?yàn)椋?quot;);
display(array);
}
}
運(yùn)行結(jié)果：
選擇排序性能分析：
選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較：N*（N-1）/2，但是至多只進(jìn)行了N次交換。
當(dāng) N 值很大時(shí)，比較次數(shù)是主要的，所以和冒泡排序一樣，用大O表示是O(N2) 時(shí)間級別。但是由于選擇排序交換的次數(shù)少，所以選擇排序無疑是比冒泡排序快的。當(dāng) N 值較小時(shí)，如果交換時(shí)間比選擇時(shí)間大的多，那么選擇排序是相當(dāng)快的。
3、插入排序
直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。
插入排序還分為直接插入排序、二分插入排序、鏈表插入排序、希爾排序等等，這里我們只是以直接插入排序講解，后面講高級排序的時(shí)候會將其他的。
代碼如下：
package com.ys.sort;
public class InsertSort {
public static int[] sort(int[] array){
int j;
//從下標(biāo)為1的元素開始選擇合適的位置插入，因?yàn)橄聵?biāo)為0的只有一個元素，默認(rèn)是有序的
for(int i = 1 ; i < array.length ; i++){
int tmp = array[i];//記錄要插入的數(shù)據(jù)
j = i;
while(j > 0 && tmp < array[j-1]){//從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
array[j] = array[j-1];//向后挪動
j--;
}
array[j] = tmp;//存在比其小的數(shù)，插入
}
return array;
}
//遍歷顯示數(shù)組
public static void display(int[] array){
for(int i = 0 ; i < array.length ; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args){
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?quot;);
display(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("經(jīng)過插入排序后的數(shù)組順序?yàn)椋?quot;);
display(array);
}
}
運(yùn)行結(jié)果：
插入排序性能分析：
在第一輪排序中，它最多比較一次，第二輪最多比較兩次，一次類推，第N輪，最多比較N-1次。因此有 1+2+3+...+N-1 = N*（N-1）/2。
假設(shè)在每一輪排序發(fā)現(xiàn)插入點(diǎn)時(shí)，平均只有全體數(shù)據(jù)項(xiàng)的一半真的進(jìn)行了比較，我們除以2得到：N*（N-1）/4。用大O表示法大致需要需要 O(N2) 時(shí)間級別。
復(fù)制的次數(shù)大致等于比較的次數(shù)，但是一次復(fù)制與一次交換的時(shí)間耗時(shí)不同，所以相對于隨機(jī)數(shù)據(jù)，插入排序比冒泡快一倍，比選擇排序略快。
這里需要注意的是，如果要進(jìn)行逆序排列，那么每次比較和移動都會進(jìn)行，這時(shí)候并不會比冒泡排序快。
4、總結(jié)
上面講的三種排序，冒泡、選擇、插入用大 O 表示法都需要 O(N2) 時(shí)間級別。一般不會選擇冒泡排序，雖然冒泡排序書寫是最簡單的，但是平均性能是沒有選擇排序和插入排序好的。
選擇排序把交換次數(shù)降低到最低，但是比較次數(shù)還是挺大的。當(dāng)數(shù)據(jù)量小，并且交換數(shù)據(jù)相對于比較數(shù)據(jù)更加耗時(shí)的情況下，可以應(yīng)用選擇排序。
在大多數(shù)情況下，假設(shè)數(shù)據(jù)量比較小或基本有序時(shí)，插入排序是三種算法中最好的選擇。
