一 選擇排序

原理：選擇排序很簡(jiǎn)單，他的步驟如下：

從左至右遍歷，找到最小(大)的元素，然后與第一個(gè)元素交換。

從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后與第二個(gè)元素進(jìn)行交換。

以此類推，直到所有元素均排序完畢。

　之所以稱之為選擇排序，是因?yàn)槊恳淮伪闅v未排序的序列我們總是從中選擇出最小的元素。下面是選擇排序的動(dòng)畫演示：

?

public class Sort {//選擇排序public static void SelectionSort(int[] array) {int n = array.length;for (int i = 0; i < n; i++) {int min = i; // 從第i+1個(gè)元素開始，找最小值for (int j = i + 1; j < n; j++) {if (array[min] > array[j])min = j;}Swap(array, i, min);}}//插入排序public static void insertionSort(int[] array){int n = array.length;for (int i =1; i < n; i++) {for (int j = i; j >0; j--) {if (array[j] < array[j-1])Swap(array, j, j-1);elsebreak;} }}//冒泡排序public static void bubbleSort(int[] array){int n = array.length;for (int i =0; i < n; i++) {for (int j = n-1; j >i; j--) {if (array[j] < array[j-1])Swap(array, j, j-1);} }}//希爾排序public static void shellSort(int[] arr){int N=arr.length;int h=1;while(h<N/3){h=3*h+1;}while (h>=1) {for(int i =h; i <N; i++) {for (int j =i; j>=h&&(arr[j]<arr[j-h]); j-=h) {swap(arr, j, j-h); }}h=h/3;}}private static void Swap(int[] array, int i, int min) {int temp = array[i];array[i] = array[min];array[min] = temp;}private static void printArr(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 = new int[] { 1, 3, 1, 4, 2, 4, 2, 3, 2, 4, 7, 6, 6, 7, 5,5, 7, 7 };System.out.println("Before Sort:");printArr(array);//SelectionSort(array);//insertionSort(array); bubbleSort(array);System.out.println("After Sort:");printArr(array);} } View Code

　　下圖分析了選擇排序中每一次排序的過(guò)程，您可以對(duì)照?qǐng)D中右邊的柱狀圖來(lái)看。

(array);

　　分析：

　　選擇排序的在各種初始條件下的排序效果如下：

選擇排序需要花費(fèi) (N – 1) + (N – 2) + … + 1 + 0 =?N(N- 1) / 2 ~ N²/2次比較 和?N-1次交換操作。

對(duì)初始數(shù)據(jù)不敏感，不管初始的數(shù)據(jù)有沒(méi)有排好序，都需要經(jīng)歷N²/2次比較，這對(duì)于一些原本排好序，或者近似排好序的序列來(lái)說(shuō)并不具有優(yōu)勢(shì)。在最好的情況下，即所有的排好序，需要0次交換，最差的情況，倒序，需要N-1次交換。

數(shù)據(jù)交換的次數(shù)較少，如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。在最差情況下也只需要進(jìn)行N-1次數(shù)據(jù)交換，在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诒容^好的一種。

二 插入排序

原理：

　　插入排序也是一種比較直觀的排序方式?？梢砸晕覀兤匠４驌淇伺茷槔齺?lái)說(shuō)明，假設(shè)我們那在手上的牌都是排好序的，那么插入排序可以理解為我們每一次將摸到的牌，和手中的牌從左到右依次進(jìn)行對(duì)比，如果找到合適的位置則直接插入。具體的步驟為：

從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

如果該元素小于前面的元素，則依次與前面元素進(jìn)行比較如果小于則交換，直到找到大于該元素的就則停止；

如果該元素大于前面的元素（已排序），則重復(fù)步驟2

重復(fù)步驟2~4 直到所有元素都排好序 。

　　下面是插入排序的動(dòng)畫演示：

分析：

　　插入排序的在各種初始條件下的排序效果如下：

　　1. 插入排序平均需要N²/4次比較和N²/4 次交換。在最壞的情況下需要N²/2 次比較和交換；在最好的情況下只需要N-1次比較和0次交換。

　　先考慮最壞情況，那就是所有的元素逆序排列，那么第i個(gè)元素需要與前面的i-1個(gè)元素進(jìn)行i-1次比較和交換，所有的加起來(lái)大概等于N(N- 1) / 2 ~ N²?/ 2，在數(shù)組隨機(jī)排列的情況下，只需要和前面一半的元素進(jìn)行比較和交換，所以平均需要N²/4次比較和N²/4 次交換。

　　在最好的情況下，所有元素都排好序，只需要從第二個(gè)元素開始都和前面的元素比較一次即可，不需要交換，所以為N-1次比較和0次交換。

　　2. 插入排序中，元素交換的次數(shù)等于序列中逆序元素的對(duì)數(shù)。元素比較的次數(shù)最少為元素逆序元素的對(duì)數(shù)，最多為元素逆序的對(duì)數(shù) 加上數(shù)組的個(gè)數(shù)減1。

　　3.總體來(lái)說(shuō)，插入排序?qū)τ诓糠钟行蛐蛄幸约霸貍€(gè)數(shù)比較小的序列是一種比較有效的方式。

　　如上圖中，序列AEELMOTRXPS，中逆序的對(duì)數(shù)為T-R，T-P，T-S，R-P，X-S 6對(duì)。典型的部分有序隊(duì)列的特征有：

• 數(shù)組中每個(gè)元素離最終排好序后的位置不太遠(yuǎn)
• 小的未排序的數(shù)組添加到大的已排好序的數(shù)組后面
• 數(shù)組中只有個(gè)別元素未排好序

　　對(duì)于部分有序數(shù)組，插入排序是比較有效的。當(dāng)數(shù)組中逆元素的對(duì)數(shù)越低，插入排序要比其他排序方法要高效的多。

　　選擇排序和插入排序的比較：

　　上圖展示了插入排序和選擇排序的動(dòng)畫效果。圖中灰色的柱子是不用動(dòng)的，黑色的是需要參與到比較中的，紅色的是參與交換的。圖中可以看出：插入排序不會(huì)動(dòng)右邊的元素，選擇排序不會(huì)動(dòng)左邊的元素；由于插入排序涉及到的未觸及的元素要比插入的元素要少，涉及到的比較操作平均要比選擇排序少一半。

3.冒泡排序

　　冒泡排序也被稱為下沉排序，是一個(gè)簡(jiǎn)單的排序算法，通過(guò)多次重復(fù)比較每對(duì)相鄰的元素，并按規(guī)定的順序交換他們，最終把數(shù)列進(jìn)行排好序。一直重復(fù)下去，直到結(jié)束。該算法得名于較小元素“氣泡”會(huì)“浮到”列表頂部。由于只使用了比較操作，所以這是一個(gè)比較排序。冒泡排序算法的運(yùn)作如下：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

　　時(shí)間復(fù)雜度

　　若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù) C和記錄移動(dòng)次數(shù) M均達(dá)到最小值： Cmin=n-1，Mmin=0。所以，冒泡排序最好的時(shí)間復(fù)雜度為 O(n)。 ? 　　 　　若初始文件是反序的，需要進(jìn)行 n-1趟排序。每趟排序要進(jìn)行 n-i次關(guān)鍵字的比較(1≤i≤n-1)，且每次比較都必須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值： 　　冒泡排序的最壞時(shí)間復(fù)雜度為O(n*n)綜上，因此冒泡排序總的平均時(shí)間復(fù)雜度為O(n*n)。

　　算法穩(wěn)定性

　　冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會(huì)再無(wú)聊地把他們倆交換一下的；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法。

　　?

希爾排序

　　原理：希爾排序也稱之為遞減增量排序，它是對(duì)插入排序的改進(jìn)。在插入排序中，我們知道，插入排序?qū)τ诮埔雅藕眯虻男蛄衼?lái)說(shuō)，效率很高，可以達(dá)到線性排序的效率。但是插入排序效率也是比較低的，他 一次只能將數(shù)據(jù)向前移一位。比如如果一個(gè)長(zhǎng)度為N的序列，最小的元素如果恰巧在末尾，那么使用插入排序仍需一步一步的向前移動(dòng)和比較，要N-1次比較和交 換。希爾排序通過(guò)將待比較的元素劃分為幾個(gè)區(qū)域來(lái)提升插入排序的效率。這樣可以讓元素可以一次性的朝最終位置邁進(jìn)一大步，然后算法再取越來(lái)越小的步長(zhǎng)進(jìn)行排序，最后一步就是步長(zhǎng)為1的普通的插入排序的，但是這個(gè)時(shí)候，整個(gè)序列已經(jīng)是近似排好序的，所以效率高。

　　如下圖，我們對(duì)下面數(shù)組進(jìn)行 排序的時(shí)候，首先以4為步長(zhǎng)，這是元素分為了LMPT，EHSS，ELOX，AELR幾個(gè)序列，我們對(duì)這幾個(gè)獨(dú)立的序列 進(jìn)行插入排序，排序完成之后，我們減小步長(zhǎng)繼續(xù)排序，最后直到步長(zhǎng)為1，步長(zhǎng)為1即為一般的插入排序，他保證了元素一定會(huì)被排序。

　　希爾排序的增量遞減算法可以隨意指定，可以以N/2遞減，只要保證最后的步長(zhǎng)為1即可。

實(shí)現(xiàn)：

public static void shellSort(int[] arr){int N=arr.length;int h=1;while(h<N/3){h=3*h+1;}while (h>=1) {for(int i =h; i <N; i++) {for (int j =i; j>=h; j-=h) {if(arr[j]<arr[j-h]){swap(arr, j, j-h);}else{break;}}}h=h/3;} }

　　可以看到，希爾排序的實(shí)現(xiàn)是在插入排序的基礎(chǔ)上改進(jìn)的，插入排序的步長(zhǎng)為1，每一次遞減1，希爾排序的步長(zhǎng)為我們定義的h，然后每一次和前面的-h位置上的元素進(jìn)行比較。算法中，我們首先獲取小于N/3 的最大的步長(zhǎng)，然后逐步長(zhǎng)遞減至步長(zhǎng)為1的一般的插入排序。

　　下面是希爾排序在各種情況下的排序動(dòng)畫：

分析：

1. 希爾排序的關(guān)鍵在于步長(zhǎng)遞減序列的確定，任何遞減至1步長(zhǎng)的序列都可以，目前已知的比較好的序列有：

• Shell’s 序列: N/2 , N/4 , …, 1 (重復(fù)除以2);
• Hibbard’s 序列: 1, 3, 7, …, 2^k?– 1 ;
• Knuth’s 序列: 1, 4, 13, …, (3^k?– 1) / 2 ;該序列是本文代碼中使用的序列。
• 已知最好的序列是 Sedgewick’s (Knuth的學(xué)生，Algorithems的作者)的序列: 1, 5, 19, 41, 109, ….

該序列由下面兩個(gè)表達(dá)式交互獲得:

• 1, 19, 109, 505, 2161,….., 9(4^k?– 2^k) + 1, k = 0, 1, 2, 3,…
• 5, 41, 209, 929, 3905,…..2^k+2?(2^k+2?– 3 ) + 1, k = 0, 1, 2, 3, …

　　“比較在希爾排序中是最主要的操作，而不是交換?！庇眠@樣步長(zhǎng)的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。

　　2. 希爾排序的分析比較復(fù)雜，使用Hibbard’s 遞減步長(zhǎng)序列的時(shí)間復(fù)雜度為O(N^3/2)，平均時(shí)間復(fù)雜度大約為O(N^5/4) ,具體的復(fù)雜度目前仍存在爭(zhēng)議。

　　3. 實(shí)驗(yàn)表明，對(duì)于中型的序列( 萬(wàn))，希爾排序的時(shí)間復(fù)雜度接近最快的排序算法的時(shí)間復(fù)雜度nlogn。

　　最后總結(jié)一下本文介紹的三種排序算法的最好最壞和平均時(shí)間復(fù)雜度。

名稱	最好	平均	最壞	內(nèi)存占用	穩(wěn)定排序
插入排序	n	n2	n2	1	是
選擇排序	n2	n2	n2	1	否
希爾排序	n	nlog2n 或 n3/2	依賴于增量遞減序列目前最好的是 nlog2n	1	否

轉(zhuǎn)載于:https://www.cnblogs.com/wxgblogs/p/5499569.html

總結(jié)

以上是生活随笔為你收集整理的基本排序算法一的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。