本文轉自公眾號 「程序員私房菜 」
一直有寫一篇關於排序演算法文章的打算,直到我看到了這一篇,我放棄了自己寫的打算,因為這篇寫的太經典了。這裡強烈推薦給大家。
之前的一篇 幾張動態圖清晰展示常用數據結構及其設計原理 發出來之後反響不錯,這次來個動圖排序演算法大全。數據結構與演算法,算是齊了!
本文將採取動態圖 + 文字描述 + Java代碼實現來講解以下十大排序演算法:
對一序列對象根據某個關鍵字進行排序。
0.2 術語說明
0.4 圖片名詞解釋:
常見的快速排序、歸併排序、堆排序、冒泡排序等屬於比較排序。在排序的最終結果裏,元素之間的次序依賴於它們之間的比較。每個數都必須和其他數進行比較,才能確定自己的位置。
在冒泡排序之類的排序中,問題規模為n,又因為需要比較n次,所以平均時間複雜度為O(n2)。在歸併排序、快速排序之類的排序中,問題規模通過分治法消減為logN次,所以時間複雜度平均O(nlogn)。
計數排序、基數排序、桶排序則屬於非比較排序。非比較排序是通過確定每個元素之前,應該有多少個元素來排序。針對數組arr,計算arr[i]之前有多少個元素,則唯一確定了arr[i]在排序後數組中的位置。
非比較排序時間複雜度底,但由於非比較排序需要佔用空間來確定唯一位置。所以對數據規模和數據分佈有一定的要求。
1、冒泡排序(Bubble Sort)
冒泡排序是一種簡單的排序演算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
1.2 動圖演示
1/** 2* 冒泡排序 3* 4* @param array 5* @return 6*/ 7public static int[] bubbleSort(int[] array) { 8 if (array.length == 0) 9 return array; 10 for (int i = 0; i < array.length; i++) 11 for (int j = 0; j < array.length - 1 - i; j++) 12 if (array[j + 1] < array[j]) { 13 int temp = array[j + 1]; 14 array[j + 1] = array[j]; 15 array[j] = temp; 16 } 17 return array; 18}
最佳情況:T(n) = O(n) 最差情況:T(n) = O(n2) 平均情況:T(n) = O(n2)
表現最穩定的排序演算法之一,因為無論什麼數據進去都是O(n2)的時間複雜度,所以用到它的時候,數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間了吧。理論上講,選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。
選擇排序(Selection-sort)是一種簡單直觀的排序演算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法描述如下:
2.3 代碼實現
1/** 2* 選擇排序 3* @param array 4* @return 5*/ 6public static int[] selectionSort(int[] array) { 7 if (array.length == 0) 8 return array; 9 for (int i = 0; i < array.length; i++) { 10 int minIndex = i; 11 for (int j = i; j < array.length; j++) { 12 if (array[j] < array[minIndex]) //找到最小的數 13 minIndex = j; //將最小數的索引保存 14 } 15 int temp = array[minIndex]; 16 array[minIndex] = array[i]; 17 array[i] = temp; 18 } 19 return array; 20}
最佳情況:T(n) = O(n2) 最差情況:T(n) = O(n2) 平均情況:T(n) = O(n2)
插入排序(Insertion-Sort)的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常採用in-place排序(即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。
一般來說,插入排序都採用in-place在數組上實現。具體演算法描述如下:
1
2.更直觀點
1/** 2* 插入排序 3* @param array 4* @return 5*/ 6public static int[] insertionSort(int[] array) { 7 if (array.length == 0) 8 return array; 9 int current; 10 for (int i = 0; i < array.length - 1; i++) { 11 current = array[i + 1]; 12 int preIndex = i; 13 while (preIndex >= 0 && current < array[preIndex]) { 14 array[preIndex + 1] = array[preIndex]; 15 preIndex--; 16 } 17 array[preIndex + 1] = current; 18 } 19 return array; 20}
3.4 演算法分析
最佳情況:T(n) = O(n) 最壞情況:T(n) = O(n2) 平均情況:T(n) = O(n2)
希爾排序是希爾(Donald Shell)於1959年提出的一種排序演算法。希爾排序也是一種插入排序,它是簡單插入排序經過改進之後的一個更高效的版本,也稱為縮小增量排序,同時該演算法是衝破O(n2)的第一批演算法之一。它與插入排序的不同之處在於,它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
希爾排序是把記錄按下表的一定增量分組,對每組使用直接插入排序演算法排序;隨著增量逐漸減少,每組包含的關鍵詞越來越多,當增量減至1時,整個文件恰被分成一組,演算法便終止。
我們來看下希爾排序的基本步驟,在此我們選擇增量gap=length/2,縮小增量繼續以gap = gap/2的方式,這種增量選擇我們可以用一個序列來表示,{n/2,(n/2)/2…1},稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題,我們選擇的這個增量序列是比較常用的,也是希爾建議的增量,稱為希爾增量,但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,具體演算法描述:
1/** 2* 希爾排序 3* 4* @param array 5* @return 6*/ 7public static int[] ShellSort(int[] array) { 8 int len = array.length; 9 int temp, gap = len / 2; 10 while (gap > 0) { 11 for (int i = gap; i < len; i++) { 12 temp = array[i]; 13 int preIndex = i - gap; 14 while (preIndex >= 0 && array[preIndex] > temp) { 15 array[preIndex + gap] = array[preIndex]; 16 preIndex -= gap; 17 } 18 array[preIndex + gap] = temp; 19 } 20 gap /= 2; 21 } 22 return array; 23}
**最佳情況:T(n) = O(nlog2 n) 最壞情況:T(n) = O(nlog2 n) 平均情況:T(n) =O(nlog2n) **
和選擇排序一樣,歸併排序的性能不受輸入數據的影響,但表現比選擇排序好的多,因為始終都是O(n log n)的時間複雜度。代價是需要額外的內存空間。
歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為2-路歸併。
2
1/** 2* 歸併排序 3* 4* @param array 5* @return 6*/ 7public static int[] MergeSort(int[] array) { 8 if (array.length < 2) return array; 9 int mid = array.length / 2; 10 int[] left = Arrays.copyOfRange(array, 0, mid); 11 int[] right = Arrays.copyOfRange(array, mid, array.length); 12 return merge(MergeSort(left), MergeSort(right)); 13} 14/** 15* 歸併排序——將兩段排序好的數組結合成一個排序數組 16* 17* @param left 18* @param right 19* @return 20*/ 21public static int[] merge(int[] left, int[] right) { 22 int[] result = new int[left.length + right.length]; 23 for (int index = 0, i = 0, j = 0; index < result.length; index++) { 24 if (i >= left.length) 25 result[index] = right[j++]; 26 else if (j >= right.length) 27 result[index] = left[i++]; 28 else if (left[i] > right[j]) 29 result[index] = right[j++]; 30 else 31 result[index] = left[i++]; 32 } 33 return result; 34}
最佳情況:T(n) = O(n) 最差情況:T(n) = O(nlogn) 平均情況:T(n) = O(nlogn)
快速排序的基本思想:通過一趟排序將待排記錄分隔成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序。
快速排序使用分治法來把一個串(list)分為兩個子串(sub-lists)。具體演算法描述如下:
1 歡快點的
2 正經點的
1/** 2* 快速排序方法 3* @param array 4* @param start 5* @param end 6* @return 7*/ 8public static int[] QuickSort(int[] array, int start, int end) { 9 if (array.length < 1 || start < 0 || end >= array.length || start > end) return null; 10 int smallIndex = partition(array, start, end); 11 if (smallIndex > start) 12 QuickSort(array, start, smallIndex - 1); 13 if (smallIndex < end) 14 QuickSort(array, smallIndex + 1, end); 15 return array; 16} 17/** 18* 快速排序演算法——partition 19* @param array 20* @param start 21* @param end 22* @return 23*/ 24public static int partition(int[] array, int start, int end) { 25 int pivot = (int) (start + Math.random() * (end - start + 1)); 26 int smallIndex = start - 1; 27 swap(array, pivot, end); 28 for (int i = start; i <= end; i++) 29 if (array[i] <= array[end]) { 30 smallIndex++; 31 if (i > smallIndex) 32 swap(array, i, smallIndex); 33 } 34 return smallIndex; 35} 36 37/** 38* 交換數組內兩個元素 39* @param array 40* @param i 41* @param j 42*/ 43public static void swap(int[] array, int i, int j) { 44 int temp = array[i]; 45 array[i] = array[j]; 46 array[j] = temp; 47}
**最佳情況:T(n) = O(nlogn) 最差情況:T(n) = O(n2) 平均情況:T(n) = O(nlogn) **
堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或者大於)它的父節點。
1 歡樂點的
注意:這裡用到了完全二叉樹的部分性質。
1//聲明全局變數,用於記錄數組array的長度; 2static int len; 3/** 4* 堆排序演算法 5* 6* @param array 7* @return 8*/ 9public static int[] HeapSort(int[] array) { 10 len = array.length; 11 if (len < 1) return array; 12 //1.構建一個最大堆 13 buildMaxHeap(array); 14 //2.循環將堆首位(最大值)與末位交換,然後在重新調整最大堆 15 while (len > 0) { 16 swap(array, 0, len - 1); 17 len--; 18 adjustHeap(array, 0); 19 } 20 return array; 21} 22/** 23* 建立最大堆 24* 25* @param array 26*/ 27public static void buildMaxHeap(int[] array) { 28 //從最後一個非葉子節點開始向上構造最大堆 29 for (int i = (len - 1) / 2; i >= 0; i--) { 30 adjustHeap(array, i); 31 } 32} 33/** 34* 調整使之成為最大堆 35* 36* @param array 37* @param i 38*/ 39public static void adjustHeap(int[] array, int i) { 40 int maxIndex = i; 41 //如果有左子樹,且左子樹大於父節點,則將最大指針指向左子樹 42 if (i * 2 < len && array[i * 2] > array[maxIndex]) 43 maxIndex = i * 2; 44 //如果有右子樹,且右子樹大於父節點,則將最大指針指向右子樹 45 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) 46 maxIndex = i * 2 + 1; 47 //如果父節點不是最大值,則將父節點與最大值交換,並且遞歸調整與父節點交換的位置。 48 if (maxIndex != i) { 49 swap(array, maxIndex, i); 50 adjustHeap(array, maxIndex); 51 } 52}
最佳情況:T(n) = O(nlogn) 最差情況:T(n) = O(nlogn) 平均情況:T(n) = O(nlogn)
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序,計數排序要求輸入的數據必須是有確定範圍的整數。
計數排序(Counting sort)是一種穩定的排序演算法。計數排序使用一個額外的數組C,其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。
1/** 2* 計數排序 3* 4* @param array 5* @return 6*/ 7public static int[] CountingSort(int[] array) { 8 if (array.length == 0) return array; 9 int bias, min = array[0], max = array[0]; 10 for (int i = 1; i < array.length; i++) { 11 if (array[i] > max) 12 max = array[i]; 13 if (array[i] < min) 14 min = array[i]; 15 } 16 bias = 0 - min; 17 int[] bucket = new int[max - min + 1]; 18 Arrays.fill(bucket, 0); 19 for (int i = 0; i < array.length; i++) { 20 bucket[array[i] + bias]++; 21 } 22 int index = 0, i = 0; 23 while (index < array.length) { 24 if (bucket[i] != 0) { 25 array[index] = i - bias; 26 bucket[i]--; 27 index++; 28 } else 29 i++; 30 } 31 return array; 32}
當輸入的元素是n 個0到k之間的整數時,它的運行時間是 O(n + k)。計數排序不是比較排序,排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的範圍(等於待排序數組的最大值與最小值的差加上1),這使得計數排序對於數據範圍很大的數組,需要大量時間和內存。
最佳情況:T(n) = O(n+k) 最差情況:T(n) = O(n+k) 平均情況:T(n) = O(n+k)
桶排序是計數排序的升級版。它利用了函數的映射關係,高效與否的關鍵就在於這個映射函數的確定。
桶排序 (Bucket sort)的工作的原理:假設輸入數據服從均勻分佈,將數據分到有限數量的桶裏,每個桶再分別排序(有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排
注意,如果遞歸使用桶排序為各個桶排序,則當桶數量為1時要手動減小BucketSize增加下一循環桶的數量,否則會陷入死循環,導致內存溢出。
1/** 2* 桶排序 3* 4* @param array 5* @param bucketSize 6* @return 7*/ 8public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) { 9 if (array == null || array.size() < 2) 10 return array; 11 int max = array.get(0), min = array.get(0); 12 // 找到最大值最小值 13 for (int i = 0; i < array.size(); i++) { 14 if (array.get(i) > max) 15 max = array.get(i); 16 if (array.get(i) < min) 17 min = array.get(i); 18 } 19 int bucketCount = (max - min) / bucketSize + 1; 20 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); 21 ArrayList<Integer> resultArr = new ArrayList<>(); 22 for (int i = 0; i < bucketCount; i++) { 23 bucketArr.add(new ArrayList<Integer>()); 24 } 25 for (int i = 0; i < array.size(); i++) { 26 bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); 27 } 28 for (int i = 0; i < bucketCount; i++) { 29 if (bucketCount == 1) 30 bucketSize--; 31 ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize); 32 for (int j = 0; j < temp.size(); j++) 33 resultArr.add(temp.get(j)); 34 } 35 return resultArr; 36}
桶排序最好情況下使用線性時間O(n),桶排序的時間複雜度,取決與對各個桶之間數據進行排序的時間複雜度,因為其它部分的時間複雜度都為O(n)。很顯然,桶劃分的越小,各個桶之間的數據越少,排序所用的時間也會越少。但相應的空間消耗就會增大。
**最佳情況:T(n) = O(n+k) 最差情況:T(n) = O(n+k) 平均情況:T(n) = O(n2) **
基數排序也是非比較的排序演算法,對每一位進行排序,從最低位開始排序,複雜度為O(kn),為數組長度,k為數組中的數的最大的位數;
基數排序是按照低位先排序,然後收集;再按照高位排序,然後再收集;依次類推,直到最高位。有時候有些屬性是有優先順序順序的,先按低優先順序排序,再按高優先順序排序。最後的次序就是高優先順序高的在前,高優先順序相同的低優先順序高的在前。基數排序基於分別排序,分別收集,所以是穩定的。
1/** 2* 基數排序 3* @param array 4* @return 5*/ 6public static int[] RadixSort(int[] array) { 7 if (array == null || array.length < 2) 8 return array; 9 // 1.先算出最大數的位數; 10 int max = array[0]; 11 for (int i = 1; i < array.length; i++) { 12 max = Math.max(max, array[i]); 13 } 14 int maxDigit = 0; 15 while (max != 0) { 16 max /= 10; 17 maxDigit++; 18 } 19 int mod = 10, div = 1; 20 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); 21 for (int i = 0; i < 10; i++) 22 bucketList.add(new ArrayList<Integer>()); 23 for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { 24 for (int j = 0; j < array.length; j++) { 25 int num = (array[j] % mod) / div; 26 bucketList.get(num).add(array[j]); 27 } 28 int index = 0; 29 for (int j = 0; j < bucketList.size(); j++) { 30 for (int k = 0; k < bucketList.get(j).size(); k++) 31 array[index++] = bucketList.get(j).get(k); 32 bucketList.get(j).clear(); 33 } 34 } 35 return array; 36}
最佳情況:T(n) = O(n * k) 最差情況:T(n) = O(n * k) 平均情況:T(n) = O(n * k)
基數排序有兩種方法:
MSD 從高位開始進行排序 LSD 從低位開始進行排序
基數排序 vs 計數排序 vs 桶排序
這三種排序演算法都利用了桶的概念,但對桶的使用方法上有明顯差異:
本文參考自:
http://www.cnblogs.com/guoyaohua/p/8600214.html
http://www.cricode.com/3212.html
歡迎關注公眾號:「努力給自己看」