做排序的方法(幾種排序方法)

1.幾種排序方法

這兩天復(fù)習(xí)了一下排序方面的知識(shí)，現(xiàn)將目前比較常見的整理一下。

選擇排序選擇排序的思想是首先先找到序列中最大元素并將它與序列中最后一個(gè)元素交換，然后找下一個(gè)最大元素并與倒數(shù)第二個(gè)元素交換，依次類推。此排序很簡(jiǎn)單，這不做多說，代碼實(shí)現(xiàn)如下：View Code插入排序算法流程： 1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

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

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置

4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

5. 將新元素插入到下一位置中

6. 重復(fù)步驟2View Code冒泡排序依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。

View Code合并排序 在介紹合并排序之前，首先介紹下遞歸設(shè)計(jì)的技術(shù)，稱為分治法。分治法的核心思想是：當(dāng)問題比較小時(shí)，直接解決。當(dāng)問題比較大時(shí)，將問題分為兩個(gè)較小的子問題，每個(gè)子問題約為原來的一半。使用遞歸調(diào)用解決每個(gè)子問題。遞歸調(diào)用結(jié)束后，常常需要額外的處理，將較小的問題的結(jié)果合并，得到較大的問題的答案。

合并排序算法在接近數(shù)組中間的位置劃分?jǐn)?shù)組，然后使用遞歸運(yùn)算對(duì)兩個(gè)一半元素構(gòu)成的數(shù)組進(jìn)行排序，最后將兩個(gè)子數(shù)組進(jìn)行合并，形成一個(gè)新的已排好序的數(shù)組。

代碼如下：View Code快速排序 快速排序與合并排序有著很多相似性。將要排序的數(shù)組分成兩個(gè)子數(shù)組，通過兩次遞歸調(diào)用分別對(duì)兩個(gè)數(shù)組進(jìn)行排序，再將已經(jīng)排好序的兩個(gè)數(shù)組合并成一個(gè)獨(dú)立的有序數(shù)組。但是，將數(shù)組一分為二的做法比合并排序中使用的簡(jiǎn)單方法復(fù)雜的多。它需要將所有小于或者等于基準(zhǔn)元素的元素放置到基準(zhǔn)元素前面的位置，將大于基準(zhǔn)的元素放置到基準(zhǔn)后面的位置。

2.排序方法都有哪幾種,比如1、2、3

排序方法一般都就那幾種。像冒泡排序，直接插入排序，快速排序，簡(jiǎn)單選擇排序，希爾排序，堆排序。其排序介紹自己看吧。

1、冒泡排序?qū)儆诜€(wěn)定排序，是一種借助“交換”進(jìn)行排序的方法。首先要將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄與第三個(gè)記錄的關(guān)鍵字，以此類推，直至第n-1個(gè)記錄與第n個(gè)記錄的關(guān)鍵字進(jìn)行比較為止，這一過程稱為第一趟冒泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄的位置上；然后進(jìn)行第二趟冒泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作；以此類推，直到在一趟排序過程中沒有進(jìn)行過交換記錄的操作為止。

2、直接插入排序?qū)儆诜€(wěn)定的排序，每次從無序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，依次進(jìn)行下去，進(jìn)行了（n-1）趟掃描以后就完成了整個(gè)排序過程，結(jié)束該次循環(huán)。

3、快速排序?qū)儆诓环€(wěn)定排序，是對(duì)起泡排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。假設(shè)待排序的序列為{R.[s],R.[s+1]，…….，R.[t]}，首先任意選取一個(gè)記錄，然后按下述原則從新排序記錄：將關(guān)鍵字較他小的記錄都安置在他的位置之前，將所有關(guān)鍵字較他大的記錄都安置在他的位置后面。由此可以該“樞軸”記錄最后所落的位置i作為分界線，將序列{R[s],R[s+1]…….R[t]}分割成兩個(gè)子序列{R[s],R[s+1]…..R[i-1]}和{R[i+1]……R[t]}，這個(gè)過程稱作一趟快速排序。一趟快速排序的具體做法是：附設(shè)兩個(gè)指針low和high，它們的初值分別指向數(shù)組第一個(gè)數(shù)據(jù)和最后一個(gè)數(shù)據(jù)，將樞軸記錄暫存在R[0]的位置上排序過程中只作R[low]或R[high]的單向移動(dòng)，直至一趟排序結(jié)束后再將樞軸記錄移至正確位置上。

4、簡(jiǎn)單選擇排序?qū)儆诓环€(wěn)定排序，基本思想是，每一趟在n-i+1(i=1,2，…n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。第i趟簡(jiǎn)單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行n-1趟比較，直到所有記錄排序完成為止。例如：進(jìn)行第i趟選擇時(shí)，從當(dāng)前候選記錄中選出關(guān)鍵字最小的k號(hào)記錄，并和第i個(gè)記錄進(jìn)行交換。

5、希爾排序?qū)儆诓环€(wěn)定排序，也是一種屬插入排序類，它的基本思想是：先將整個(gè)待排記錄序列分割稱為若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的一個(gè)特點(diǎn)是：子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。

6、堆排序?qū)儆诓环€(wěn)定排序，它的基本思想是，先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無序區(qū)，再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key；由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆，然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n- 2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。直到無序區(qū)只有一個(gè)元素為止

3.常用的排序算法都有哪些

排序算法 所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

分類 在計(jì)算機(jī)科學(xué)所使用的排序算法通常被分類為： 計(jì)算的復(fù)雜度（最差、平均、和最好表現(xiàn)），依據(jù)串列（list）的大?。╪）。一般而言，好的表現(xiàn)是O。

(n log n)，且壞的行為是Ω（n2）。對(duì)於一個(gè)排序理想的表現(xiàn)是O(n)。

僅使用一個(gè)抽象關(guān)鍵比較運(yùn)算的排序算法總平均上總是至少需要Ω（n log n）。 記憶體使用量（以及其他電腦資源的使用） 穩(wěn)定度：穩(wěn)定排序算法會(huì)依照相等的關(guān)鍵（換言之就是值）維持紀(jì)錄的相對(duì)次序。

也就是一個(gè)排序算法是穩(wěn)定的，就是當(dāng)有兩個(gè)有相等關(guān)鍵的紀(jì)錄R和S，且在原本的串列中R出現(xiàn)在S之前，在排序過的串列中R也將會(huì)是在S之前。 一般的方法：插入、交換、選擇、合并等等。

交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。

當(dāng)相等的元素是無法分辨的，比如像是整數(shù)，穩(wěn)定度并不是一個(gè)問題。然而，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來排序。

（4, 1） (3, 1) (3, 7) (5, 6) 在這個(gè)狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個(gè)是依照相等的鍵值維持相對(duì)的次序，而另外一個(gè)則沒有： （3, 1） (3, 7) (4, 1) (5, 6) （維持次序） （3, 7） (3, 1) (4, 1) (5, 6) （次序被改變） 不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序，但是穩(wěn)定排序算法從來不會(huì)如此。不穩(wěn)定排序算法可以被特別地時(shí)作為穩(wěn)定。

作這件事情的一個(gè)方式是人工擴(kuò)充鍵值的比較，如此在其他方面相同鍵值的兩個(gè)物件間之比較，就會(huì)被決定使用在原先資料次序中的條目，當(dāng)作一個(gè)同分決賽。然而，要記住這種次序通常牽涉到額外的空間負(fù)擔(dān)。

排列算法列表 在這個(gè)表格中，n是要被排序的紀(jì)錄數(shù)量以及k是不同鍵值的數(shù)量。 穩(wěn)定的 冒泡排序（bubble sort） — O(n2) 雞尾酒排序 （Cocktail sort， 雙向的冒泡排序） — O(n2) 插入排序 （insertion sort）— O(n2) 桶排序 （bucket sort）— O(n)； 需要 O(k) 額外 記憶體 計(jì)數(shù)排序 （counting sort） — O(n+k)； 需要 O(n+k) 額外 記憶體 歸并排序 （merge sort）— O(n log n)； 需要 O(n) 額外記憶體 原地歸并排序 — O(n2) 二叉樹排序 （Binary tree sort） — O(n log n)； 需要 O(n) 額外記憶體 鴿巢排序 （Pigeonhole sort） — O(n+k)； 需要 O(k) 額外記憶體 基數(shù)排序 （radix sort）— O(n·k)； 需要 O(n) 額外記憶體 Gnome sort — O(n2) Library sort — O(n log n) with high probability， 需要 （1+ε）n 額外記憶體 不穩(wěn)定 選擇排序 （selection sort）— O(n2) 希爾排序 （shell sort）— O(n log n) 如果使用最佳的現(xiàn)在版本 Comb sort — O(n log n) 堆排序 （heapsort）— O(n log n) Smoothsort — O(n log n) 快速排序 （quicksort）— O(n log n) 期望時(shí)間， O(n2) 最壞情況； 對(duì)於大的、亂數(shù)串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情況時(shí)間， 需要 額外的 O(n + k) 空間， 也需要找到最長(zhǎng)的遞增子序列（longest increasing subsequence） 不實(shí)用的排序算法 Bogo排序 — O(n * n！) 期望時(shí)間， 無窮的最壞情況。

Stupid sort — O(n3)； 遞回版本需要 O(n2) 額外記憶體 Bead sort — O(n) or O（√n）， 但需要特別的硬體 Pancake sorting — O(n)， 但需要特別的硬體 排序的算法 排序的算法有很多，對(duì)空間的要求及其時(shí)間效率也不盡相同。下面列出了一些常見的排序算法。

這里面插入排序和冒泡排序又被稱作簡(jiǎn)單排序，他們對(duì)空間的要求不高，但是時(shí)間效率卻不穩(wěn)定；而后面三種排序相對(duì)于簡(jiǎn)單排序?qū)臻g的要求稍高一點(diǎn)，但時(shí)間效率卻能穩(wěn)定在很高的水平?；鶖?shù)排序是針對(duì)關(guān)鍵字在一個(gè)較小范圍內(nèi)的排序算法。

插入排序 冒泡排序 選擇排序 快速排序 堆排序 歸并排序 基數(shù)排序 希爾排序 插入排序 插入排序是這樣實(shí)現(xiàn)的： 首先新建一個(gè)空列表，用于保存已排序的有序數(shù)列（我們稱之為"有序列表"）。 從原數(shù)列中取出一個(gè)數(shù)，將其插入"有序列表"中，使其仍舊保持有序狀態(tài)。

重復(fù)2號(hào)步驟，直至原數(shù)列為空。 插入排序的平均時(shí)間復(fù)雜度為平方級(jí)的，效率不高，但是容易實(shí)現(xiàn)。

它借助了"逐步擴(kuò)大成果"的思想，使有序列表的長(zhǎng)度逐漸增加，直至其長(zhǎng)度等于原列表的長(zhǎng)度。 冒泡排序 冒泡排序是這樣實(shí)現(xiàn)的： 首先將所有待排序的數(shù)字放入工作列表中。

從列表的第一個(gè)數(shù)字到倒數(shù)第二個(gè)數(shù)字，逐個(gè)檢查：若某一位上的數(shù)字大于他的下一位，則將它與它的下一位交換。 重復(fù)2號(hào)步驟，直至再也不能交換。

冒泡排序的平均時(shí)間復(fù)雜度與插入排序相同，也是平方級(jí)的，但也是非常容易實(shí)現(xiàn)的算法。 選擇排序 選擇排序是這樣實(shí)現(xiàn)的： 設(shè)數(shù)組內(nèi)存放了n個(gè)待排數(shù)字，數(shù)組下標(biāo)從1開始，到n結(jié)束。

i=1 從數(shù)組的第i個(gè)元素開始到第n個(gè)元素，尋找最小的元素。 將上一步找到的最小元素和第i位元素交換。

如果i=n-1算法結(jié)束，否則回到第3步 選擇排序的平均時(shí)間復(fù)雜度也是O(n2)的。 快速排序 現(xiàn)在開始，我們要接觸高效排序算法了。

實(shí)踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半部分。

4.排序法都有哪些

一、插入排序（Insertion Sort）1. 基本思想：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。

2. 排序過程： 【示例】：[初始關(guān)鍵字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1. Procedure InsertSort(Var R : FileType);2. //對(duì)R[1..N]按遞增序進(jìn)行插入排序， R[0]是監(jiān)視哨//3. Begin4. for I := 2 To N Do //依次插入R[2],。,R[n]//5. begin6. R[0] := R; J := I - 1;7. While R[0] < R[J] Do //查找R的插入位置//8. begin9. R[J+1] := R[J]； //將大于R的元素后移//10. J := J - 111. end12. R[J + 1] := R[0] ； //插入R //13. end14. End; //InsertSort //復(fù)制代碼二、選擇排序1. 基本思想： 每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2. 排序過程：【示例】：初始關(guān)鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 [38 65 97 76 49 27 49] 第二趟排序后 13 27 [65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 1. Procedure SelectSort(Var R : FileType)； //對(duì)R[1..N]進(jìn)行直接選擇排序 //2. Begin3. for I := 1 To N - 1 Do //做N - 1趟選擇排序//4. begin5. K := I;6. For J := I + 1 To N Do //在當(dāng)前無序區(qū)R[I..N]中選最小的元素R[K]//7. begin8. If R[J] < R[K] Then K := J9. end;10. If K I Then //交換R和R[K] //11. begin Temp := R; R := R[K]; R[K] := Temp; end;12. end13. End; //SelectSort //復(fù)制代碼三、冒泡排序（BubbleSort）1. 基本思想： 兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2. 排序過程： 設(shè)想被排序的數(shù)組R[1..N]垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。

【示例】：49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 1. Procedure BubbleSort(Var R : FileType) //從下往上掃描的起泡排序//2. Begin3. For I := 1 To N-1 Do //做N-1趟排序//4. begin5. NoSwap := True； //置未排序的標(biāo)志//6. For J := N - 1 DownTo 1 Do //從底部往上掃描//7. begin8. If R[J+1]= X) And (I < J) Do7. begin8. J := J - 1 //從右向左掃描，查找第1個(gè)小于 X的元素//9. If I < J Then //已找到R[J] 〈X//10. begin11. R := R[J]； //相當(dāng)于交換R和R[J]//12. I := I + 113. end;14. While (R <= X) And (I < J) Do15. I := I + 1 //從左向右掃描，查找第1個(gè)大于 X的元素///16. end;17. If I X //18. begin R[J] := R； //相當(dāng)于交換R和R[J]//19. J := J - 120. end21. Until I = J;22. R := X //基準(zhǔn)X已被最終定位//23. End; //Parttion //復(fù)制代碼1. Procedure 。

5.數(shù)據(jù)結(jié)構(gòu)的排序方法有哪些

冒泡排序，快速排序，堆排序。

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。

它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名“冒泡排序”。

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

堆排序（Heapsort）是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。

6.數(shù)據(jù)排序的一般方法有什么

數(shù)據(jù)排序方法

好的排序方法可以有效提高排序速度，提高排序效果。

在計(jì)算機(jī)領(lǐng)域主要使用數(shù)據(jù)排序方法根據(jù)占用內(nèi)存的方式不同分為2大類：內(nèi)部排序方法與外部排序方法。

內(nèi)部排序方法

若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。

內(nèi)排序的方法有許多種，按所用策略不同，可歸納為五類：插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。

其中，插入排序主要包括直接插入排序和希爾排序兩種；選擇排序主要包括直接選擇排序和堆排序；交換排序主要包括氣（冒）泡排序和快速排序。

外部排序方法

外部排序基本上由兩個(gè)相互獨(dú)立的階段組成。首先，按可用內(nèi)存大小，將外存上含n個(gè)記錄的文件分成若干長(zhǎng)度為k的子文件或段（segment），依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序，并將排序后得到的有序子文件重新寫入外存。通常稱這些有序子文件為歸并段或順串；然后，對(duì)這些歸并段進(jìn)行逐趟歸并，使歸并段（有序子文件）逐漸由小到大，直至得到整個(gè)有序文件為止。

7.四種排序方法及公式

1 選擇排序 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。

首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[1]與a[3]的值，若a[1]大于a[3]則交換兩者的值，否則不變。

再比較a[1]與a[4]，以此類推，最后比較a[1]與a[n]的值。這樣處理一輪后，a[1]的值一定是這組數(shù)據(jù)中最小的。

再將a[2]與a[3]~a[n]以相同方法比較一輪，則a[2]的值一定是a[2]~a[n]中最小的。再將a[3]與a[4]~a[n]以相同方法比較一輪，以此類推。

共處理n-1輪后a[1]、a[2]、……a[n]就以升序排列了。 優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)與冒泡排序一樣； 缺點(diǎn)：相對(duì)之下還是慢。

2 插入排序 已知一組升序排列數(shù)據(jù)a[1]、a[2]、……a[n]，一組無序數(shù)據(jù)b[1]、b[2]、……b[m]，需將二者合并成一個(gè)升序數(shù)列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大于a[2]，則繼續(xù)跳過，直到b[1]小于a數(shù)組中某一數(shù)據(jù)a[x]，則將a[x]~a[n]分別向后移動(dòng)一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。

b[2]~b[m]用相同方法插入。（若無數(shù)組a，可將b[1]當(dāng)作n=1的數(shù)組a） 優(yōu)點(diǎn)：穩(wěn)定，快； 缺點(diǎn)：比較次數(shù)不一定，比較次數(shù)越少，插入點(diǎn)后的數(shù)據(jù)移動(dòng)越多，特別是當(dāng)數(shù)據(jù)總量龐大的時(shí)候，但用鏈表可以解決這個(gè)問題。

3 歸并排序 由希爾在1959年提出，又稱希爾排序（shell排序）。 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。

發(fā)現(xiàn)當(dāng)n不大時(shí)，插入排序的效果很好。首先取一增量d(da[x]，然后采用分治的策略分別對(duì)a[1]~a[k-1]和a[k+1]~a[n]兩組數(shù)據(jù)進(jìn)行快速排序。

優(yōu)點(diǎn)：極快，數(shù)據(jù)移動(dòng)少； 缺點(diǎn)：不穩(wěn)定。

8.數(shù)據(jù)結(jié)構(gòu)中排序方法有多少種

1、插入排序（直接插入排序和希爾排序）

2、選擇排序（直接選擇排序和堆排序）

3、交換排序（冒泡排序和快速排序）

4、歸并排序

5、基數(shù)排序

直接插入排序：逐個(gè)將后一個(gè)數(shù)加到前面的排好的序中。在直接插入排序過程中，對(duì)其中一個(gè)記錄的插入排序稱為一次排序；直接插入排序是從第二個(gè)記錄開始進(jìn)行的，因此，長(zhǎng)度為n的記錄序列需要進(jìn)行n-1次排序才能完成整個(gè)序列的排序。時(shí)間復(fù)雜度為O(n2)。

希爾排序：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最后一次排序時(shí)的增量必須為1，最簡(jiǎn)單可取di+1=di/2（取?。r(shí)間復(fù)雜度為O(n(log2n)2)。

直接選擇排序

說明：每次將后面的最小的找出來插入前面的已排好的序中。同理，具有n個(gè)記錄的序列要做n-1次排序。

時(shí)間復(fù)雜度為O(n2)。

冒泡排序：兩個(gè)兩個(gè)比較，將大的往后移。通過第一次冒泡排序，使得待排序的n個(gè)記錄中關(guān)鍵字最大的記錄排到了序列的最后一個(gè)位置上。然后對(duì)序列中前n-1個(gè)記錄進(jìn)行第二次冒泡排序。。。對(duì)于n個(gè)記錄的序列，共需進(jìn)行n次冒泡排序。時(shí)間復(fù)雜度為O(n2)。

快速排序：又叫分區(qū)交換排序，是對(duì)冒泡排序方法的一種改進(jìn)。時(shí)間復(fù)雜度為O(nlog2n)。

歸并排序：將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列合并成一個(gè)有序數(shù)據(jù)序列的過程。時(shí)間復(fù)雜度為O(nlog2n)。

9.排序有幾種方法

一. 冒泡排序冒泡排序是是一種簡(jiǎn)單的排序算法。

它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把它們交換過來。遍歷數(shù)列的工作是重復(fù)的進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端1.冒泡排序算法的運(yùn)作如下：（1）比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序），就交換他們兩個(gè)（2）對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。

這步做完后，最后的元素還是最大的數(shù)（3）針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)二. 選擇排序 選擇排序是一種簡(jiǎn)單直觀的排序算法。他的工作原理如下： 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢茫┪参恢茫?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。

以此類推，直到所有元素均排序完畢 選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。

選擇排序每次交換一對(duì)元素，他們當(dāng)中至少有一個(gè)將被移到最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng) 元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N三. 插入排序 插入排序是一種簡(jiǎn)單直觀的排序算法。

它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在從后向前掃描的過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間四. 快速排序 快速排序，又稱劃分交換排序。

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列五 希爾排序過程希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。六. 歸并排序歸并排序是采用分治法（把復(fù)雜問題分解為相對(duì)簡(jiǎn)單的子問題，分別求解，最后通過組合起子問題的解的方式得到原問題的解）的一個(gè)非常典型的應(yīng)用。

歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組將數(shù)組分解最小之后，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，水小九先取誰，取了后相應(yīng)的指針就往后移一位。然后比較，直至一個(gè)數(shù)組為空，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可。