各種排序算法的實現(xiàn)以及思考

本文格式為Word版，下載可任意編輯——各種排序算法的實現(xiàn)以及思考冒泡排序（Bubblesort）

原理

冒泡排序是一種簡單的排序算法。它重復(fù)訪問要排序的數(shù)列，每一次比較兩個元素，假使前一個大于后一個元素，則交換數(shù)據(jù)。那么在一次全部訪問過程中，最大的元素就’浮’動到數(shù)列的最終。然后重復(fù)進行方法，知道再沒有數(shù)據(jù)交換，也就是數(shù)列已經(jīng)排序完成。步驟

1.比較相鄰的元素。假使第一個比其次個大，就交換他們兩個。

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

3.針對所有的元素重復(fù)以上的步驟，除了最終一個。

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

實現(xiàn)

voidBubbleSort(intarr[],intn){inti,j;i=n;

boolflag=true;while(flag){flag=false;

for(j=1;jarr[j]){swap(arr[j-1],arr[j]);flag=true;}

}i--;}}

在上面的代碼中參與了一個flag來標(biāo)記是否有數(shù)據(jù)交換，假使在排序過程中沒發(fā)生數(shù)據(jù)交換，則表示已經(jīng)排列好了，后面就不需要在遍歷了。

冒泡排序算是最簡單的排序算法了，但終究是一種效率低下的排序算法，再數(shù)據(jù)量不大的狀況下可以使用。

插入排序（Insertionsort）

原理

插入排序是一種直觀的排序算法。它通過構(gòu)建有序數(shù)列，對未排序的數(shù)據(jù)，在已排序的數(shù)列中從后往前掃描，找到相應(yīng)的位置插入。在排序的實現(xiàn)上，從后向前的掃描過程中，需要反復(fù)把已排序的元素逐步向后移動，為要插入的元素留空間。步驟

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

2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描3.假使該元素（已排序）大于新元素，將該元素移到下一位置4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置5.將新元素插入到該位置后6.重復(fù)步驟2~5

實現(xiàn)

voidInsertSort(intarr[],intn){inti,j;

for(i=1;i=0j--){arr[j+1]=arr[j];}

arr[j+1]=temp;}}}

插入排序不適合對于數(shù)據(jù)了比較大的排序應(yīng)用。但是，假使排序數(shù)據(jù)了很小，譬如一千左右，那插入排序是一個不錯的選擇。

選擇排序（Selectionsort）

原理

選擇排序與插入排序很像，插入排序是將一個數(shù)插入已經(jīng)排好的序列，而選擇排序是在未排序的序列中找到最小(大)元素，放在排序序列的起始位置。然后，再從剩下的未排序的序列中再次尋覓最小(大)元素，放在已排序序列的末尾，反復(fù)重復(fù)，知道所有元素排序完成。步驟

1.初始時，數(shù)組全為無序區(qū)為a[0..n-1]。令i=0

2.在無序區(qū)a[i…n-1]中選取一個最小的元素，將其與a[i]交換。交換之后a[0…i]就形成了一個有序區(qū)。

3.i++并重復(fù)其次步直到i==n-1。排序完成。

實現(xiàn)

voidSelectSort(intarr[],intn){inti,j,minIndex;for(i=0;iarr[j]){minIndex=j;}}

if(minIndex!=i){

Swap(arr[i],arr[minIndex]);}}}

選擇排序中，假使某個元素位于正確的最終位置，則不會被移動。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移動到最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆谑趾玫囊环N。

希爾排序（Shellsort）

原理

希爾排序,也稱作遞減增量排序算法，是插入排序的一種更高效版本。它以一定的增量將序列分為若干個組，然后每一組進行插入排序，然后減少增量反復(fù)分組進行插入排序。直到增量為1時，就為普通的插入排序，但是此時序列已經(jīng)基本排列完成，只需要進行少量的移動即可完成。步驟

將數(shù)組列在一個表中并對列排序（用插入排序）。重復(fù)這過程，不過每次用更長的列來進行。最終整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身僅僅對原數(shù)組進行排序（通過增加索引的步長，例如是用i+=step_size而不是i++）

例如，假設(shè)有這樣一組數(shù)[13149433822559946523452773253910]，假使我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)當(dāng)看起來是這樣：

13149433822559946523452773253910

然后我們對每列進行排序：

10147325231327943339255994658245

將上述四行數(shù)字，依序接在一起時我們得到：[10147325231327943339255994658245].這時10已經(jīng)移至正確位置了，然后再以3為步長進行排序：

10147325231327943339255994658245

排序之后變?yōu)椋?/p>

10141325233327255939657345948294

最終以1步長進行排序（此時就是簡單的插入排序了）。實現(xiàn)

voidShellSort(intarr[],intn){inti,j,gep;

for(gep=n/2;gep>0;gep/=2){for(i=gep;i=0j-=gep){arr[j+gep]=arr[j];}

arr[j+gep]=temp;}}}

希爾排序步長的選擇十分靈活，只要最終步場為1的任何步長序列都可以工作。以上的代碼從n/2開始，每一次減半，最終步長為1，算法變?yōu)椴迦肱判?，就保證了數(shù)據(jù)一定會被排序。

歸并排序（Mergesort）

原理

歸并排序是創(chuàng)立在歸并操作上的一種有效的排序算法，基本思想是分治法。它時將兩個已經(jīng)排序的序列合并成一個序列的操作。步驟歸并操作

1.申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列

2.設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置

3.比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4.重復(fù)步驟3直到某一指針到達序列尾

5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾

歸并排序

1.將序列每相鄰兩個數(shù)字進行歸并操作，形成floor(n/2)個序列，排序后每個序列包含兩個元素

2.將上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素3.重復(fù)步驟2，直到所有元素排序完畢

實現(xiàn)

//歸并操作