數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計排序的概念排序的分類排序的基本操作7.1排序的概念排序整理文件中的記錄，使它們按關(guān)鍵字遞增(或遞減)次序重新排列關(guān)鍵字?jǐn)?shù)據(jù)元素中的一個數(shù)據(jù)項，可以標(biāo)識數(shù)據(jù)元素主關(guān)鍵字，次關(guān)鍵字7.1排序的概念按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問排序的分類按排序后相同關(guān)鍵字所處的相對位置穩(wěn)定排序：若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則稱該排序方法是穩(wěn)定的。不穩(wěn)定排序：若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生改變，則稱該排序方法是不穩(wěn)定的。排序的分類按排序的策略插入排序：直接插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序排序的分類關(guān)鍵操作比較兩個關(guān)鍵字大小將記錄從一個位置移動到另一個位置不同存儲方式的排序過程以順序表作為存儲結(jié)構(gòu)對記錄本身進行物理重排以鏈表作為存儲結(jié)構(gòu)無須移動記錄，僅需修改指針排序的基本操作小結(jié)7.1排序的概念排序的概念排序的分類排序的基本操作數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計直接插入排序希爾排序7.2插入排序直接插入排序直接插入排序是一種簡單的排序算法，其基本操作是將需要排序的元素插入已排好的有序序列，并將這一過程重復(fù)多次，從而得到一個完整的有序序列。直接插入排序直接插入排序算法由兩重循環(huán)組成，時間復(fù)雜度O(n2)直接插入排序在初態(tài)為正序時所需時間最少初態(tài)為基本有序時所需的比較和移動次數(shù)均較少只需要一條記錄的輔助空間用來作為待插入記錄的暫存空間，空間復(fù)雜度為O(1)直接插入排序是一種穩(wěn)定的排序方法直接插入排序分析基本思想：先將整個待排序元素序列分割成若干個子序列（由相隔某個“增量d”的元素組成)分別進行直接插入排序，然后依次縮減增量進行排序，待整個序列中的元素基本有序（增量足夠小)時，再對全體元素進行一次直接插入排序。希爾排序?qū)τ赿，最初的方案是d1=n/2，di+1=di/2，直到dt=1。di+1=di/3+1。

其它方案有都取奇數(shù)di互質(zhì)希爾排序算法分析希爾排序的復(fù)雜度很難分析，在特定情況下可以準(zhǔn)確地估算關(guān)鍵字的比較和記錄移動次數(shù)，但是考慮到與增量之間的依賴關(guān)系，無法給出精確的數(shù)學(xué)分析。希爾排序的時間復(fù)雜度在O(nlog2n)和O(n2)之間，但不能精確估計。希爾排序算法分析特點每一趟以不同的增量進行插入排序當(dāng)d較大時，被移動的記錄是跳躍式進行的最后一趟排序時，d=1，許多記錄已經(jīng)有序，不需要多少移動，所以能提高排序的速度希爾排序是不穩(wěn)定的排序方法希爾排序算法分析小結(jié)7.2插入排序直接插入排序希爾排序數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計冒泡排序快速排序7.3交換排序在待排序序列中每次選取兩條記錄進行比較，若這兩條記錄不滿足排序的要求，則交換位置，直到序列中所有記錄兩兩比較都滿足排序的要求為止。交換排序在每一趟排序中，都比較相鄰兩個數(shù)的大小。若需要按照由小到大的順序進行排序，一旦逆序則交換它們的位置，每趟排序都會使當(dāng)前“最大”的數(shù)“沉到”序列末尾，小的數(shù)逐步“上升”。冒泡排序冒泡排序示例初始數(shù)據(jù)

45，37，63，91，26，13，58，2第1趟 37，45，63，26，13，58，2，91第2趟 37，45，26，13，58，2，63，91第3趟 37，26，13，45，2，58，63，91第4趟 26，13，37，2，45，58，63，91第5趟 13，26，2，37，45，58，63，91第6趟 13，2，26，37，45，58，63，91第7趟 2，13，26，37，45，58，63，91

冒泡排序算法分析快速排序在每一輪挑選一個基準(zhǔn)元素，并讓其他比它大的元素移動到數(shù)列一邊，比它小的元素移動到數(shù)列的另一邊，從而把數(shù)列拆解成了兩個部分。然后再按照此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列?？焖倥判蚧舅枷耄簭臄?shù)列中挑出一個元素（默認序列第一個記錄），稱為"基準(zhǔn)"元素進行排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。然后遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序?？焖倥判蚩焖倥判蚴纠跏紨?shù)據(jù) 45，37，63，91，26，13，58，2453763912613582第1趟[2，37，13，26]，45，[91，58，63]第2趟

2，[37，13，26]，45，[63，58]，91第3趟2，[26，13]，37，45，[58]，63，91第4趟2，[13]，26，37，45，58，63，91第1趟快速排序算法在分治法的思想下，原數(shù)列在每一輪被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，直到不可再分為止，平均情況下需要log2n輪，因此快速排序算法的平均時間復(fù)雜度是O(nlog2n)在最壞情況下，快速排序算法每一輪只能確定基準(zhǔn)元素一個位置，時間復(fù)雜度為O(n2)快速排序空間復(fù)雜度為O(1)快速排序是一種不穩(wěn)定排序算法快速排序算法分析小結(jié)7.3交換排序冒泡排序快速排序數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計簡單選擇排序堆排序7.4選擇排序首先在待排序序列中找到最?。ù螅┰?，存放到已排序列的起始位置。然后，再從剩余待排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。選擇排序基本思想：在要排序的一數(shù)列中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，以此類推，直至第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較排序完成為止。簡單選擇排序簡單選擇排序示例簡單選擇排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)。進行比較操作的時間復(fù)雜度為O(n2)，進行移動操作的時間復(fù)雜度為O(n)。簡單選擇排序是不穩(wěn)定排序。簡單選擇排序算法分析堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，是簡單選擇排序的改進。堆是具有以下性質(zhì)的完全二叉樹：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序堆排序示例待排序的序列為堆結(jié)構(gòu)，關(guān)鍵字為：{2,26,13,37,45,63,58,91}，用堆排序的方式將序列從大到小進行排序堆排序示例堆排序示例堆排序示例堆排序?qū)τ涗洈?shù)較大的序列效率較高，其運行時間主要耗費在初始建堆和重建堆時進行的反復(fù)篩選上堆排序的時間復(fù)雜度為O(nlog2?n)堆排序是不穩(wěn)定排序堆排序算法分析小結(jié)7.4選擇排序簡單選擇排序堆排序數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計7.5歸并排序?qū)⒁延行虻淖有蛄兄鸺壓喜?，得到完全有序的序列；若每次將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序二路歸并排序示例待排序的序列關(guān)鍵字為{45,37,63,91,26,13,58,2}，采用二路歸并算法進行排序每趟歸并的時間復(fù)雜度為O(n)，共需進行l(wèi)og2?n趟。二路歸并排序的時間復(fù)雜度等于歸并趟數(shù)與每一趟時間復(fù)雜度的乘積，其時間復(fù)雜度為O(nlog2n)二路歸并排序時使用了n個臨時內(nèi)存單元存放數(shù)據(jù)元素，所以二路歸并排序算法的空間復(fù)雜度為O(n)。二路歸并排序是穩(wěn)定排序二路歸并排序算法分析小結(jié)7.5歸并排序數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計7.6排序方法比較各種排序方法，其時間性能和空間性能如下排序方法最好情況最壞情況平均時間輔助存儲直接插入排序O(n)O(n2)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(nlog2n)~O(n2)O(1)冒泡排序O(n)O(n2)O(n2)O(1)快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)簡單選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)直接插入排序、直接選擇排序和冒泡排序的算法比較簡單，時間復(fù)雜度平均為O(n2)堆排序、快速排序和歸并排序算法比較復(fù)雜，時間復(fù)雜度為O(log2n)希爾排序時間復(fù)雜度介于O(log2n)~