排序通常采用順序存儲，使用鏈表的的話很麻煩。下面介紹常見的八大排序：

插入排序，冒泡排序，快速排序，合并排序，選擇排序，堆排序，桶排序，基數(shù)排序。

內部排序就是可以在內存中完成的排序，數(shù)據(jù)量不大。

外部排序指的是大文件的排序，當待排序的文件很大時，無法將整個文件的所有記錄同時調入內存進行排序，只能將文件存放在外存，這種排稱為外部排序。

????1）直接插入排序：是最簡單的排序方法，每次將一個待排序的記錄，插入到已經排好的數(shù)據(jù)列中，得到一個新的長度增1的有序表。

? ? 算法步驟：

1）設待排序的記錄存儲在數(shù)組 r[1...n] 中，可以把第一個記錄 r[1] 看作一個有序系列。

2）依次將 r[i] (i = 2, ..., n) 插入到已經排好序列 r[1...r-1] 中，并保持有序性。

? ? 2）希爾排序：略

2.冒泡排序

冒泡排序是一種最簡單的交換排序算法，通過兩兩比較關鍵字，如果逆序就交換，使關鍵字大的記錄像泡泡一樣冒出來放在尾部。重復執(zhí)行若干次冒泡排序，最終得到有序序列。

算法步驟：

1）設待排序的記錄存儲在數(shù)組 r[1...n] 中，首先第一個記錄和第二個記錄關鍵字比較，如果逆序則交換；然后第二個記錄和第三個記錄關鍵字比較，... ，以此類推，直到第 n-1 個記錄和第n個記錄關鍵字比較完畢為止。第一趟排序結束，關鍵字最大的記錄在最后一個位置。

2）第二趟排序，對前 n-1 個元素進行冒泡排序，關鍵字大的記錄在n-1 位置。

3）重復上述過程，直到某一趟排序中沒有進行交換記錄為止，說明序列已經有序。

3.快速排序

快速排序（Quicksort）是比較快速的排序方法。快速排序由C.A.R.Hoare在1962年提出。它的基本思想是通過一組排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此使所有數(shù)據(jù)變成有序序列。

快速排序的基本思想是基于分治策略的，其算法思想如下。

1）分解：先從數(shù)列中取出一個元素作為基準元素。以基準元素為標準，將問題分解為兩個子序列，使小于或等于基準元素的子序列在左側，大于基準元素的子序列在右側。

2）治理：對兩個子序列進行快速排序。

3）合并：將排好序的兩個子序列合并在一起，得到原問題的解。

選取基準的一些方法：

*取第一個元素

*取最后一個元素

*取中間位置元素

*取第一個、最后一個、中間位置元素三者之中位數(shù)。

*取第一個和最后一個之間位置的隨機數(shù)k (low <= k <= high), 選R[k] 做基準元素。

算法步驟：

1）首先取數(shù)組的第一個元素作為基準元素 pivot= R[low] 。i = low, j = high。

2）從右向左掃描，找小于等于privot 的數(shù)，如果找到，R[i] 和 R[j] 交換，i++。

3）從左向右掃描，找大于 privot 的數(shù)，如果找到，R[i] 和 R[j] 交換， j--。

4）重復步驟2~步驟3，直到 i 和 j 指針重合，返回該位置 mid = i,該位置的數(shù)正好是 pivot元素。

5）至此完成一趟排序。此時以mid 為界，將原數(shù)據(jù)分為兩個子序列，左側子序列元素都比 pivot小，右側子序列元素都比pivot大，然后再分別對這兩個子序列進行快速排列。

????????首先對原序列執(zhí)行劃分，得到劃分的中間位置 mid, 然后以中間位置為界，分別對左半部分（low, mid-1）執(zhí)行快速排序，右半部分（mid+1,high）執(zhí)行快速排序。遞歸結束的條件是 low>=high。

快速排序的重點在于劃分。

4.合并排序

合并排序就是采用分治的策略，將一個大問題分解為很多個小問題，先解決小問題，再通過小問題解決大問題。由于排序問題給定的是一個無序的序列，可以把待排序元素分解成兩個規(guī)模大致相等的子序列。如果不易解決，再將得到的子序列繼續(xù)分解，直到子序列中包含的元素個數(shù)為1。因為單個元素的序列本身是有序的，此時便可以進行合并，從而得到一個完整的有序序列。

算法設計：

合并排序是采用分治的策略實現(xiàn)對n 個元素進行排序的算法，是分治法的一個典型應用和完美體現(xiàn)。它是一種平衡，簡單的二分分治策略，過程大致分為：

（1）分解——將待排序的元素分成大小大致相同的兩個子序列。

（2）治理——對兩個子序列進行合并排序。

（3）合并——將排好序的有序子序列進行合并，得到最終的有序序列。

合并排序的重點在于合并。

5.選擇排序

簡單選擇排序又稱為直接選擇排序，是一種最簡單的選擇排序算法，每次從待排序列中選擇一個最小的放在最前面。

算法步驟：

1）設待排的記錄存儲在數(shù)組 r[1...n] 中，首先從 r[1..n] 中選擇一個關鍵字最小的記錄 r[k], r[k] 與 r[1] 交換。

2）第二趟排序，從 r[2...n] 中選擇一個關鍵字最小的記錄 r[k], r[k] 與 r[2] 交換。

3）重復上述過程，經過 n-1 趟排序，得到有序序列。

注意：每次選擇一個最小的記錄和最前面記錄交換，其他元素沒動，和冒泡排序是不同的，冒泡排序是通過兩兩交換的方法將最大的記錄交換到最后面。

算法實現(xiàn)：

6.堆排序

????堆排序是一種樹形選擇排序算法，簡單選擇排序算法每次選擇一個關鍵字最下的記錄需要O(n) 的時間，而堆排序選擇一個關鍵字最小的記錄只需要O(logn)的時間。

????堆可以看作一顆完全二叉樹的順序存儲結構，在這棵完全二叉樹中，如果每一個結點的值都大于等于左右孩子的值，稱為最大值。如果每個結點的值都小于等于左右孩子的值，稱為最小堆。

????根據(jù)完全二叉樹的性質（是平衡二叉樹），如果一個結點的下標為 i, 其左孩子下標為 2i, 其右孩子下標為 2*i +1,其雙親的下標為 i/2 。且具有 n 個結點的完全二叉樹的深度為 [log2 n]+1。

????堆排序充分利用堆頂記錄最大（最?。┑男再|進行排序，每次將堆頂記錄交換到最后，剩余記錄調整為堆即可。

算法步驟：

1）構建初始堆。

2）堆頂和最后一個記錄交換，即 r[1] 和 r[n] 交換，將 r[1...n-1] 重新調整為堆。

3）堆頂和最后一個記錄交換，即 r[1] 和 r[n-1] 交換，將 r[1...n-1]重新調整為堆。

4）循環(huán) n-1次，得到一個有序序列。

因為構建初始堆需要反復調整為堆，所以先說明如何調整堆，然后講解如何構建初始堆，進行堆排序。

1.調整堆（下沉）

堆排序時首先堆頂和最后一個記錄交換。

交換后除了堆頂之外，其他結點都滿足最大堆的定義，只需要將堆頂執(zhí)行“下沉”操作，即可調整為堆。

“下沉”操作：堆頂與左右孩子比較，如果比孩子大，則已調整為堆；如果比孩子小，則與較大的孩子交換，交換到新的位置后，繼續(xù)向下比較，從根節(jié)點一直比較到葉子。

構建初始堆過程：首先按照完全二叉樹的順序構建一顆完全二叉樹，然后從最后一個分支結點 n/2 開始調整堆，依次將序號為 n/2-1, n/2-2, ..., 1 的結點執(zhí)行下沉操作調整為堆。

堆排序： 構建初始堆之后，開始進行堆排序。因為最大堆的堆頂是最大的記錄，可以將堆頂交換到最后一個元素的位置，然后堆頂執(zhí)行下沉操作，調整 r[1...n-1]為堆即可。重復此過程，直到剩余一個結點，得到有序序列。

7.桶排序

桶排序屬于分配排序。

分配排序不需要比較關鍵字的大小，根據(jù)關鍵字各位上的值，進行若干趟“分配” 和 “收集”實現(xiàn)排序。

桶排序將待排序序列劃分成若干個區(qū)間，每個區(qū)間形象的看作一個桶，如果桶中的記錄多于一個則使用較快的排序方法進行排序（例如：快速排序算法），把桶中的記錄收集起來，最終得到有序序列。

8.基數(shù)排序

基數(shù)排序（radix sort）可以看作桶排序的擴展，它是一種多關鍵字排序算法。如果記錄按照多個關鍵字排序，則依次按照這些關鍵字進行排序。例如撲克牌排序，撲克牌由數(shù)字面值和花色兩個關鍵字組成，可以先按照面值（2,3, .. ,10,J,Q,K,A）排序，再按照花色排序。如果記錄按照一個數(shù)值型的關鍵字排序，可以把該關鍵字看作是由 d 位組成的多關鍵字排序，每一位的值取值范圍位 [0, r), 其中 r 稱為基數(shù)。例如，十進制數(shù) 268 由3 位數(shù)組成，每一位的取值范圍為 [0,10),十進制數(shù)的基數(shù) r 為 10，同樣，二進制數(shù)的基數(shù)為 2，英文字母的基數(shù)為 26。

算法步驟：

1）求出待排序列中最大關鍵字的位數(shù) d, 然后從低位到高位進行基數(shù)排序；

2）按個位將關鍵字依次分配到桶中，然后將每個桶中的數(shù)據(jù)依次收集起來；

3）按十位將關鍵字依次分配到桶中，然后將每個桶中的數(shù)據(jù)依次收集起來；

4）依次下去，直到d 位處理完畢，得到一個有序的序列。

例如：

討論：分配和收集時為什么要“依次”放入和收集？

如果不是按順序依次進行分配和收集則無法實現(xiàn)排序結果的正確性。

如何保證依次分配和收集呢？

一個非常簡單的方法就是隊列，先進先出，依次進行。因此可以采用隊列保持桶中數(shù)據(jù)的進出順序，保證排序結果的正確性。也就是說，每一個桶內使用一個隊列存儲數(shù)據(jù)，可以使用順序隊列或者鏈式隊列。

桶中多個數(shù)據(jù)元素可以采用二維數(shù)組，鏈式存儲，也可以采用一維輔助數(shù)組進行處理。

?