【算法】八大經(jīng)典排序算法詳解
我記得上大學(xué)的時(shí)候，老師一直跟我們強(qiáng)調(diào)：“算法才是編程的靈魂”，找工作面試的時(shí)候，算法和數(shù)據(jù)結(jié)構(gòu)也是絕對(duì)不可避免的，面試官可能一言不合就讓你手寫一個(gè)排序算法。
我把最經(jīng)典的八大排序算法原理和代碼也都整理出來了，內(nèi)容如下，希望對(duì)大家能有所幫助。
插入排序
?基本思想：每步將一個(gè)待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。?算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。?代碼：
public static void insertionSort(int[] array){int tmp;for(int i=1;i<array.length;i++){tmp = array[i]; //將當(dāng)前位置的數(shù)給tmpint j = i;for(;j>0&&array[j-1]>tmp;j--){/*往右移，騰出左邊的位置,array[j-1]>tmp:大于號(hào)是升序排列，小于號(hào)是降序排列*/array[j] = array[j-1];}//將當(dāng)前位置的數(shù)插入到合適的位置array[j] = tmp;}}
冒泡排序
?基本思想：持續(xù)比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。直到?jīng)]有任何一對(duì)數(shù)字需要比較。?冒泡排序最好的時(shí)間復(fù)雜度為O(n)。冒泡排序的最壞時(shí)間復(fù)雜度為O(n^2)。因此冒泡排序總的平均時(shí)間復(fù)雜度為O(n^2)。?算法適用于少量數(shù)據(jù)的排序，是穩(wěn)定的排序方法。?代碼：
public static void bubbleSort(int[] array){int tmp;boolean flag = false; //設(shè)置是否發(fā)生交換的標(biāo)志for(int i = array.length-1;i >= 0;i--){for(int j=0;j<i;j++){ //每一輪都找到一個(gè)最大的數(shù)放在右邊if(array[j]>array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = true; //發(fā)生了交換}}if(!flag) break; //這一輪循環(huán)沒有發(fā)生交換，說明排序已經(jīng)完成，退出循環(huán)}}
選擇排序
?基本思想：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。?選擇排序是不穩(wěn)定的排序方法。時(shí)間復(fù)雜度 O(n^2)。?代碼：
public static void selectSort(int[] array){for(int i = 0;i<array.length-1;i++){int min = array[i];int minindex = i;for(int j = i;j<array.length;j++){if(array[j]<min){ //選擇當(dāng)前最小的數(shù)min = array[j];minindex = j;}}if(i != minindex){ //若i不是當(dāng)前元素最小的，則和找到的那個(gè)元素交換array[minindex] = array[i];array[i] = min;}}}
希爾排序
?基本思想：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2
?希爾排序不穩(wěn)定，時(shí)間復(fù)雜度 平均時(shí)間 O(nlogn) 最差時(shí)間O(n^2)?代碼：
public static void shellSort(int[] array){int j;for(int gap = array.length/2; gap>0; gap /= 2){//定義一個(gè)增長(zhǎng)序列，即分割數(shù)組的增量,d1=N/2 dk=(d(k-1))/2for(int i = gap; i<array.length;i++){int tmp = array[i];for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){//將相距為Dk的元素進(jìn)行排序array[j] = array[j-gap];}array[j] = tmp;}}}
堆排序
?預(yù)備知識(shí)：
二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。大根堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值；小根堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值。二叉堆一般用數(shù)組來表示。例如，根節(jié)點(diǎn)在數(shù)組中的位置是0，第n個(gè)位置的子節(jié)點(diǎn)分別在2n+1和 2n+2。因此，第0個(gè)位置的子節(jié)點(diǎn)在1和2，1的子節(jié)點(diǎn)在3和4。以此類推。這種存儲(chǔ)方式便於尋找父節(jié)點(diǎn)和子節(jié)點(diǎn)。例如初始要排序的數(shù)組為：49, 38, 65, 97, 76, 13, 27, 49 構(gòu)造成大根堆之后的數(shù)組為：97 76 65 49 49 13 27 38 實(shí)際樹形結(jié)構(gòu)如圖（最大堆）：
?堆排序基本思想：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系【參見二叉樹的順序存儲(chǔ)結(jié)構(gòu)】，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。?堆排序是一種選擇排序,其時(shí)間復(fù)雜度為O(nlogn)。堆排序是不穩(wěn)定的?代碼：
```/** 堆排序* 調(diào)整最大堆，交換根元素和最后一個(gè)元素。* 參數(shù)說明：* a -- 待排序的數(shù)組*/public static void heapSort(int[] a) {int n = a.length;int i,tmp;// 從(n/2-1) --> 0逐次遍歷。遍歷之后，得到的數(shù)組實(shí)際上是一個(gè)(最大)二叉堆。for (i = n / 2 - 1; i >= 0; i--)maxHeapDown(a, i, n-1);// 從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個(gè)元素for (i = n - 1; i > 0; i--) {// 交換a[0]和a[i]。交換后，a[i]是a[0...i]中最大的。tmp = a[0];a[0] = a[i];a[i] = tmp;// 調(diào)整a[0...i-1]，使得a[0...i-1]仍然是一個(gè)最大堆。// 即，保證a[i-1]是a[0...i-1]中的最大值。maxHeapDown(a, 0, i-1);}}/** 注：數(shù)組實(shí)現(xiàn)的堆中，第N個(gè)節(jié)點(diǎn)的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。* 其中，N為數(shù)組下標(biāo)索引值，如數(shù)組中第1個(gè)數(shù)對(duì)應(yīng)的N為0。** 參數(shù)說明：* a -- 待排序的數(shù)組* start -- 被下調(diào)節(jié)點(diǎn)的起始位置(一般為0，表示從第1個(gè)開始)* end -- 截至范圍(一般為數(shù)組中最后一個(gè)元素的索引)*/public static void maxHeapDown(int[] a, int start, int end) {int c = start; // 當(dāng)前(current)節(jié)點(diǎn)的位置int l = 2*c + 1; // 左(left)孩子的位置int tmp = a[c]; // 當(dāng)前(current)節(jié)點(diǎn)的大小for (; l <= end; c=l,l=2*l+1) {// "l"是左孩子，"l+1"是右孩子if ( l < end && a[l] < a[l+1])l++; // 左右兩孩子中選擇較大者，即m_heap[l+1]if (tmp >= a[l])break; // 調(diào)整結(jié)束else { // 交換值a[c] = a[l];a[l]= tmp;}}}```
歸并排序
?歸并排序的原理?將待排序的數(shù)組分成前后兩個(gè)部分，再遞歸的將前半部分?jǐn)?shù)據(jù)和后半部分的數(shù)據(jù)各自歸并排序，得到的兩部分?jǐn)?shù)據(jù)，然后使用merge合并算法（算法見代碼）將兩部分算法合并到一起。例如：如果N=1；那么只有一個(gè)數(shù)據(jù)要排序，N=2，只需要調(diào)用merge函數(shù)將前后合并，N=4，........... 也就是將一個(gè)很多數(shù)據(jù)的數(shù)組分成前后兩部分，然后不斷遞歸歸并排序，再合并，最后返回有序的數(shù)組。?歸并排序的時(shí)間復(fù)雜度?歸并排序的最好、最壞和平均時(shí)間復(fù)雜度都是O(nlogn)，而空間復(fù)雜度是O(n)，比較次數(shù)介于(nlogn)/2和(nlogn)-n+1，賦值操作的次數(shù)是(2nlogn)。因此可以看出，歸并排序算法比較占用內(nèi)存，但卻是效率高且穩(wěn)定的排序算法。?代碼：
public class MergeSort {private static void mergeSort(int[] array,int[] tmp,int left,int right){if(left<right){int center = ( left + right ) / 2;//取數(shù)組的中點(diǎn)mergeSort(array,tmp,left,center);//歸并排序數(shù)組的前半部分mergeSort(array,tmp,center+1,right);//歸并排序數(shù)組的后半部分merge(array,tmp,left,center+1,right);//將數(shù)組的前后半部分合并}}/** 超簡(jiǎn)單的合并函數(shù)*/private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {// TODO Auto-generated method stubint leftEnd = rightPos - 1;int tmpPos = leftPos;int numElements = rightEnd - leftPos + 1;while(leftPos <= leftEnd && rightPos <= rightEnd){if(array[leftPos]<=array[rightPos]){tmp[tmpPos++] = array[leftPos++];}else{tmp[tmpPos++] = array[rightPos++];}}while(leftPos <= leftEnd){tmp[tmpPos++] = array[leftPos++];}while(rightPos <= rightEnd){tmp[tmpPos++] = array[rightPos++];}for(int i=0;i<numElements;i++,rightEnd--){array[rightEnd] = tmp[rightEnd];}}public static void mergeSort(int[] array){int[] tmp = new int[array.length];//聲明一個(gè)用來合并的數(shù)組mergeSort(array,tmp,0,array.length-1);//調(diào)用排序函數(shù)，傳入數(shù)字的起點(diǎn)和終點(diǎn)}}
快速排序
?快速排序原理：1.如果數(shù)組S中元素是0或者1，則返回；2.區(qū)數(shù)組S中任一元素v，稱之為樞紐元；3.將S-{v}（S中剩余的元素）劃分成連個(gè)不相交的集合：S1={S-{v}|x<=v}和S2={S-{v}|x>=v};4.返回{quicksort(s1)}后跟v，繼而返回{quicksort(S2)}。?選取樞紐元（三數(shù)中值分割法）?一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為基元。分割策略：在分割階段吧所有小元素移到數(shù)組的左邊，大元素移到數(shù)組右邊。，大小是相對(duì)于樞紐元素而言的。當(dāng)i在j的左邊時(shí)，將i右移，移過哪些小于樞紐元的元素，并將j左移，已過那些大于樞紐元的元素，當(dāng)i和j停止時(shí)，i指向一個(gè)大元素，而j指向一個(gè)小元素，如果i在j的左邊，那么將這兩個(gè)元素交換，其效果是把一個(gè)大元素推向右邊，而把小元素推向左邊。效果如圖：
?快速排序平均時(shí)間復(fù)雜度為O(nlogn)，最壞情況為O(n^2)，n越大，速度越快。不是穩(wěn)定的排序算法。?代碼：
/** 快速排序* 兩個(gè)方向，左邊的i下標(biāo)一直往右走，當(dāng)a[i] <= a[center_index]，* 其中center_index是中樞元素的數(shù)組下標(biāo)，而右邊的j下標(biāo)一直往左走，當(dāng)a[j] > a[center_index]* 如果i和j都走不動(dòng)了，i <= j, 交換a[i]和a[j],重復(fù)上面的過程，直到i>j* 交換a[j]和a[center_index]，完成一趟快速排序* 樞軸采用三數(shù)中值分割法可以優(yōu)化*///遞歸快速排序public static void quickSort(int a[]){qSort(a, 0, a.length - 1);}//遞歸排序，利用兩路劃分public static void qSort(int a[],int low,int high){int pivot = 0;if(low < high){//將數(shù)組一分為二pivot = partition(a,low,high);//對(duì)第一部分進(jìn)行遞歸排序qSort(a,low,pivot);//對(duì)第二部分進(jìn)行遞歸排序qSort(a,pivot + 1,high);}}//partition函數(shù)，實(shí)現(xiàn)三數(shù)中值分割法public static int partition(int a[],int low,int high){int pivotkey = a[low]; //選取第一個(gè)元素為樞軸記錄while(low < high){//將比樞軸記錄小的交換到低端while(low < high && a[high] >= pivotkey){high--;}//采用替換而不是交換的方式操作a[low] = a[high];//將比樞軸記錄大的交換到高端while(low < high && a[low] <= pivotkey){low++;}a[high] = a[low];}//樞紐所在位置賦值a[low] = pivotkey;//返回樞紐所在的位置return low;}
桶式排序
?桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個(gè)特征：待排序列所有的值處于一個(gè)可枚舉的范圍之類；待排序列所在的這個(gè)可枚舉的范圍不應(yīng)該太大，否則排序開銷太大。?排序的具體步驟如下：(1)對(duì)于這個(gè)可枚舉范圍構(gòu)建一個(gè)buckets數(shù)組，用于記錄“落入”每個(gè)桶中元素的個(gè)數(shù)；(2)將（1）中得到的buckets數(shù)組重新進(jìn)行計(jì)算，按如下公式重新計(jì)算：
buckets[i] = buckets[i] +buckets[i-1] (其中1<=i<buckets.length);?桶式排序是一種非常優(yōu)秀的排序算法，時(shí)間效率極高，它只要通過2輪遍歷：第1輪遍歷待排數(shù)據(jù)，統(tǒng)計(jì)每個(gè)待排數(shù)據(jù)“落入”各桶中的個(gè)數(shù)，第2輪遍歷buckets用于重新計(jì)算buckets中元素的值，2輪遍歷后就可以得到每個(gè)待排數(shù)據(jù)在有序序列中的位置，然后將各個(gè)數(shù)據(jù)項(xiàng)依次放入指定位置即可。?桶式排序的空間開銷較大，它需要兩個(gè)數(shù)組，第1個(gè)buckets數(shù)組用于記錄“落入”各桶中元素的個(gè)數(shù)，進(jìn)而保存各元素在有序序列中的位置，第2個(gè)數(shù)組用于緩存待排數(shù)據(jù).?桶式排序是穩(wěn)定的。如果待排序數(shù)據(jù)的范圍在0~k之間，那么它的時(shí)間復(fù)雜度是O(k+n)的.?但是它的限制多，比如它只能排整形數(shù)組。而且當(dāng)k較大，而數(shù)組長(zhǎng)度n較小，即k>>n時(shí)，輔助數(shù)組C[k+1]的空間消耗較大。當(dāng)數(shù)組為整形，且k和n接近時(shí), 可以用此方法排序。?代碼實(shí)現(xiàn)：
//min的值為0，max的值為待排序數(shù)組中最大值+1public static void bucketSort(int[] data, int min, int max) {// 緩存數(shù)組int[] tmp = new int[data.length];// buckets用于記錄待排序元素的信息// buckets數(shù)組定義了max-min個(gè)桶int[] buckets = new int[max - min];// 計(jì)算每個(gè)元素在序列出現(xiàn)的次數(shù)for (int i = 0; i < data.length; i++) {buckets[data[i] - min]++;}// 計(jì)算“落入”各桶內(nèi)的元素在有序序列中的位置for (int i = 1; i < max - min; i++) {buckets[i] = buckets[i] + buckets[i - 1];}// 將data中的元素完全復(fù)制到tmp數(shù)組中System.arraycopy(data, 0, tmp, 0, data.length);// 根據(jù)buckets數(shù)組中的信息將待排序列的各元素放入相應(yīng)位置for (int k = data.length - 1; k >= 0; k--) {data[--buckets[tmp[k] - min]] = tmp[k];}}
總結(jié)
?下面是一個(gè)總的表格，大致總結(jié)了我們常見的所有的排序算法的特點(diǎn)。
?性能測(cè)試
以上只是整理了8個(gè)經(jīng)典排序算法的內(nèi)容，想要跟深入學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)，推薦大家去看《圖解算法》這本書，內(nèi)容通俗易懂，看完絕對(duì)對(duì)你的算法有很大的幫助。
往期精彩回顧
獲取本站知識(shí)星球優(yōu)惠券，復(fù)制鏈接直接打開：
https://t.zsxq.com/qFiUFMV
本站qq群704220115。
加入微信群請(qǐng)掃碼：