當我們進行資料處理的時候，往往需要對資料進行查找操作，一個有序的資料集往往能夠在高效的查找演算法下快速得到結果，所以排序的效率就會顯的十分重要，本篇我們將著重的介紹幾個常見的排序演算法，涉及如下內容：
- 排序相關的概念
- 插入類排序
- 交換類排序
- 選擇類排序
- 歸并排序演算法實作
一、排序相關的基本概念
排序其實是一個相當大的概念，主要分為兩類：內部排序和外部排序，而我們通常所說的各種排序演算法其實指的是內部排序演算法，內部排序是基于記憶體的，整個排序程序都是在記憶體中完成的，而外部排序指的是由于資料量太大，記憶體不能完全容納，排序的時候需要借助外存才能完成（常常是算計著某一部分已經計算過的資料移出記憶體讓另一部分未被計算的資料進入記憶體），而我們本篇文章將主要介紹內排序中的幾種常用排序演算法：
還有一個概念問題，排序的穩定性問題，如果Ai = Aj，排序前Ai在Aj之前，排序后Ai還在Aj之前，則稱這種排序演算法是穩定的，否則說明該演算法不穩定，
二、插入類排序演算法
插入類排序演算法的核心思想是，在一個有序的集合中，我們將當前值插入到適合位置上，使得插入結束之后整個集合依然是有序的，那我們接下來就學習下這幾種同一類別的不同實作，
1、直接插入排序
直接插入排序演算法的核心思想是，將第 i 個記錄插入到前面 i-1 個已經有序的集合中，下圖是一個完整的直接插入排序程序：
因為一個元素肯定是有序的，i 等于 2 的時候，將第二個元素插入到前 i-1個有序集合中，當 i 等于3的時候，將第三個元素插入到前 i-1（2）集合中，等等，直到我們去插入最后一個元素的時候，前面的 i-1 個元素構成的集合已經是有序的了，于是我們找到第 i 個元素的合適位置插入即可，整個插入排序完成，下面是具體的實作代碼：
public class test3 {
public static void InsertSort(int[] array){
int i=0,j=0,key;
for (i=1;i<10;i++){
key = array[i];
j = i-1;
while(j>=0&&key<array[j]){
//需要移動位置,將較大的值array[j]向后移動一個位置
array[j+1] = array[j];
j--;
}
//回圈結束說明找到適當的位置了,是時候插入值了
array[j+1] = key;
}
//輸出排序后的陣列內容
for (int value : array){
System.out.print(value+",");
}
}
public static void main(String[] args){
//主函式中對其進行呼叫
int[] array = {1,13,72,9,22,4,6,781,29,2};
InsertSort(array);
}
}
整個程式的邏輯是從陣列的第二個元素開始，每個元素都以其前面所有的元素為基本，找到合適的位置進行插入，對于這種按照從小到大的排序原則，程式使用一個臨時變數temp保存當前需要插入的元素的值，從前面的子序列的最后一個元素開始，回圈的與temp進行比較，一旦發現有大于temp的元素，讓它順序的往后移動一個位置，直到找到一個元素小于temp，那么就找到合適的插入位置了，
因為我們使用的判斷條件是，key>array[j]，所以來說，插入排序演算法也是穩定的演算法，對于值相同的元素并不會更改他們原來的位置順序，至于該演算法的效率，最好的情況是所有元素都已有序，比較次數為n-1，最壞的情況是所有元素都是逆序的，比較次數為（n+2）（n-1）/2，所以該演算法的時間復雜度為O（n*n），
2、二分折半插入排序
既然我們每次要插入的序列是有序的，我們完全可以使用二分查找到合適位置再進行插入，這顯然要比直接插入的效率要高一些，代碼比較類似，不再做解釋，
public class test4 { public static void halfInsertSort(int[] array){ for(int k=1;k<array.length;k++){ int key = array[k]; //找到合適的位置 int low,high,mid; low = 0;high = k-1; while(low <= high){ mid = (low+high)/2; if(key == array[mid])break; else if(key > array[mid]){ low = mid+1; }else{ high = mid-1; } } //low的索引位置就是即將插入的位置 //移動low索引位置后面的所有元素 for(int x=k-1;x>=low;x--){ array[x+1] = array[x]; } array[low] = key; } //遍歷輸出有序佇列內容 for(int key:array){ System.out.print(key + ","); } } public static void main(String[] args){ int[] array = {1,13,72,9,22,4,6,781,29,2}; halfInsertSort(array); } }
雖然，折半插入改善了查找插入位置的比較次數，但是移動的時間耗費并沒有得到改善，所以效率上優秀的量可觀，時間復雜度仍然為O(n*n)，
2、希爾排序
直接插入排序在整個待排序序列基本有序的情況下，效率最佳，但我們往往不能保證每次待排序的序列都是基本有序的，希爾排序就是基于這樣的情形，它將待排序序列拆分成多個子序列，保證每個子序列的組成元素相對較少，然后通過對子序列使用直接排序，對于本就容量不大的子序列來說，直接排序的效率是相當優秀的，
希爾排序演算法使用一個距離增量來切分子序列，例如：
如圖，我們初始有一個序列，按照距離增量為4來拆分的話，可以將整個序列拆分成四個子序列，我們對四個子序列內部進行直接插入排序得到結果如下：
修改距離增量重新劃分子序列：
很顯然，當距離增量變小的時候，序列的個數也會變少，但是這些子序列的內部都基本有序，當對他們進行直接插入排序的時候會使得效率變高，一旦距離增量減少為1，那么子序列的個數也將減少為1，也就是我們的原序列，而此時的序列內部基本有序，最后執行一次直接插入排序完成整個排序操作，
下面我們看演算法是的具體實作：
public class test4 { /*漸減delete的值*/ public static void ShellSort(){ int[] array = {46,55,13,42,94,17,5,70}; int[] delets = {4,2,1}; for (int i=0;i<delets.length;i++){ oneShellSort(array,delets[i]); } //遍歷輸出陣列內容 for(int value : array){ System.out.print(value + ","); } } /*根據距離增量的值劃分子序列并對子序列內部進行直接插入排序*/ public static void oneShellSort(int[] array,int delet){ int temp; for(int i=delet;i<array.length;i++){ //從第二個子序列開始交替進行直接的插入排序 //將當前元素插入到前面的有序佇列中 if(array[i-delet] > array[i]){ temp = array[i]; int j=i-delet; while(j>=0 && array[j] > temp){ array[j+delet] = array[j]; j -= delet; } array[j + delet] = temp; } } } public static void main(String[] args){ ShellSort(); } }
三、交換類排序
交換類的排序演算法一般是利用兩個元素之間的值的大小進行比較運算，然后移動外置實作的，這類排序演算法主要有兩種：
1、冒泡排序
冒泡排序通過兩兩比較，每次將最大或者最小的元素移動到整個序列的一端，這種排序相當常見，也比較簡單，直接上代碼：
public class test4 { public static void bubbleSort(int[] array){ int temp = 0; for(int i=0;i<array.length-1;i++){ for(int j =0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ //交換兩個陣列元素的值 temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } //遍歷輸出陣列元素 for(int value : array){ System.out.print(value + ","); } } public static void main(String[] args){ int[] array={2,1,55,66,44,22,99,101,100}; bubbleSort(array); } }
2、快速排序
有沒有既不浪費空間又可以快一點的排序演算法呢？那就是“快速排序”啦！光聽這個名字是不是就覺得很高端呢，
假設我們現在對“6 1 2 7 9 3 4 5 10 8”這個10個數進行排序，首先在這個序列中隨便找一個數作為基準數（不要被這個名詞嚇到了，就是一個用來參照的數，待會你就知道它用來做啥的了），為了方便，就讓第一個數6作為基準數吧，接下來，需要將這個序列中所有比基準數大的數放在6的右邊，比基準數小的數放在6的左邊，類似下面這種排列：
3 1 2 5 4 6 9 7 10 8
在初始狀態下，數字6在序列的第1位，我們的目標是將6挪到序列中間的某個位置，假設這個位置是k，現在就需要尋找這個k，并且以第k位為分界點，左邊的數都小于等于6，右邊的數都大于等于6，想一想，你有辦法可以做到這點嗎？
方法其實很簡單：分別從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”，先從右往左找一個小于6的數，再從左往右找一個大于6的數，然后交換他們，這里可以用兩個變數i和j，分別指向序列最左邊和最右邊，我們為這兩個變數起個好聽的名字“哨兵i”和“哨兵j”，剛開始的時候讓哨兵i指向序列的最左邊（即i=1），指向數字6，讓哨兵j指向序列的最右邊（即=10），指向數字，
首先哨兵j開始出動，因為此處設定的基準數是最左邊的數，所以需要讓哨兵j先出動，這一點非常重要（請自己想一想為什么），哨兵j一步一步地向左挪動（即j–），直到找到一個小于6的數停下來，接下來哨兵i再一步一步向右挪動（即i++），直到找到一個數大于6的數停下來，最后哨兵j停在了數字5面前，哨兵i停在了數字7面前，
現在交換哨兵i和哨兵j所指向的元素的值，交換之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交換結束，接下來開始哨兵j繼續向左挪動（再友情提醒，每次必須是哨兵j先出發），他發現了4（比基準數6要小，滿足要求）之后停了下來，哨兵i也繼續向右挪動的，他發現了9（比基準數6要大，滿足要求）之后停了下來，此時再次進行交換，交換之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交換結束，“探測”繼續，哨兵j繼續向左挪動，他發現了3（比基準數6要小，滿足要求）之后又停了下來，哨兵i繼續向右移動，糟啦！此時哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前，說明此時“探測”結束，我們將基準數6和3進行交換，交換之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一輪“探測”真正結束，此時以基準數6為分界點，6左邊的數都小于等于6，6右邊的數都大于等于6，回顧一下剛才的程序，其實哨兵j的使命就是要找小于基準數的數，而哨兵i的使命就是要找大于基準數的數，直到i和j碰頭為止，
OK，解釋完畢，現在基準數6已經歸位，它正好處在序列的第6位，此時我們已經將原來的序列，以6為分界點拆分成了兩個序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”，接下來還需要分別處理這兩個序列，因為6左邊和右邊的序列目前都還是很混亂的，不過不要緊，我們已經掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可，現在先來處理6左邊的序列現吧，
左邊的序列是“3 1 2 5 4”，請將這個序列以3為基準數進行調整，使得3左邊的數都小于等于3，3右邊的數都大于等于3，好了開始動筆吧
如果你模擬的沒有錯，調整完畢之后的序列的順序應該是：
2 1 3 5 4
OK，現在3已經歸位，接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”，對序列“2 1”以2為基準數進行調整，處理完畢之后的序列為“1 2”，到此2已經歸位，序列“1”只有一個數，也不需要進行任何處理，至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”，序列“5 4”的處理也仿照此方法，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
對于序列“9 7 10 8”也模擬剛才的程序，直到不可拆分出新的子序列為止，最終將會得到這樣的序列，如下
1 2 3 4 5 6 7 8 9 10
到此，排序完全結束，細心的同學可能已經發現，快速排序的每一輪處理其實就是將這一輪的基準數歸位，直到所有的數都歸位為止，排序就結束了，下面上個霸氣的圖來描述下整個演算法的處理程序，
這是為什么呢？
快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的，每次排序的時候設定一個基準點，將小于等于基準點的數全部放到基準點的左邊，將大于等于基準點的數全部放到基準點的右邊，這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了，因此總的比較和交換次數就少了，速度自然就提高了，當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換，因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2)，它的平均時間復雜度為O(NlogN)，其實快速排序是基于一種叫做“二分”的思想，我們后面還會遇到“二分”思想，到時候再聊，先上代碼，如下
public class test4 { public static void quickSort(int[] arr,int low,int high){ int i,j,temp,t; if(low>high){ return; } i=low; j=high; //temp就是基準位 temp = arr[low]; while (i<j) { //先看右邊，依次往左遞減 while (temp<=arr[j]&&i<j) { j--; } //再看左邊，依次往右遞增 while (temp>=arr[i]&&i<j) { i++; } //如果滿足條件則交換 if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后將基準為與i和j相等位置的數字交換 arr[low] = arr[i]; arr[i] = temp; //遞回呼叫左半陣列 quickSort(arr, low, j-1); //遞回呼叫右半陣列 quickSort(arr, j+1, high); } public static void main(String[] args){ int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; quickSort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }
四、選擇類排序
選擇類排序的基本思想是，每一趟會在n個元素中比較n-1次，選擇出最大或者最小的一個元素放在整個序列的端點處，選擇類排序有基于樹的也有基于線性表的，有關樹結構的各種排序演算法，我們將在后續文章中進行描述，此處我們實作簡單的選擇排序演算法，
public class test4 { public static void ChooseSort(int[] array){ for (int i=0;i<array.length;i++){ for (int j=i+1;j<array.length;j++){ if(array[i]>array[j]){ //發現比自己小的元素，則交換位置 int temp = array[j]; array[j]=array[i]; array[i] = temp; } } } //輸出排序后的陣列內容 for (int key : array){ System.out.print(key+","); } } public static void main(String[] args){ int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; ChooseSort(arr); } }
五、歸并類排序演算法
這里的歸并類排序演算法指的就是歸并排序，歸并排序的核心思想是，對于一個初始的序列不斷遞回，直到子序列中的元素足夠少時，對他們進行直接排序，然后遞回回傳繼續對兩個分別有序的序列進行直接排序，最終遞回結束的時候，整個序列必然是有序的，
對于一個初始序列，我們遞回拆分的結果如上圖，最小的子序列只有兩個元素，我們可以輕易的對他們進行直接的排序，簡單的排序結果如下：
然后我們遞回回傳：
初看起來和我們的希爾排序的基本思想有點像，希爾排序通過對初始序列的稀疏化，使得每個子序列在內部上都是有序的，最終在對整個序列進行排序的時候，序列的內部基本有序，總體上能提高效率，但是我們的歸并排序的和核心思想是，通過不斷的遞回，直到子序列元素足夠少，在內部對他們進行直接的排序操作，當遞回回傳的時候，對回傳的兩個子表再次進行歸并排序，使得合成的新序列是有序的，一直到遞回回傳呼叫結束時候，整個序列就是有序的，
import java.util.Arrays; public class test4 { //歸并排序 /*歸并排序采用遞回實作 * 分階段可以理解為就是遞回拆分子序列的程序、 * 治階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]， * */ public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ int []temp = new int[arr.length];//在排序前，先建好一個長度等于原陣列長度的臨時陣列，避免遞回中頻繁開辟空間 sort(arr,0,arr.length-1,temp); } private static void sort(int[] arr,int left,int right,int []temp){ if(left<right){ int mid = (left+right)/2; sort(arr,left,mid,temp);//左邊歸并排序，使得左子序列有序 sort(arr,mid+1,right,temp);//右邊歸并排序，使得右子序列有序 merge(arr,left,mid,right,temp);//將兩個有序子陣列合并操作 } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left;//左序列指標 int j = mid+1;//右序列指標 int t = 0;//臨時陣列指標 while (i<=mid && j<=right){ if(arr[i]<=arr[j]){ temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } while(i<=mid){//將左邊剩余元素填充進temp中 temp[t++] = arr[i++]; } while(j<=right){//將右序列剩余元素填充進temp中 temp[t++] = arr[j++]; } t = 0; //將temp中的元素全部拷貝到原陣列中 while(left <= right){ arr[left++] = temp[t++]; } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2260.html
標籤：其他