數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)概要

1、數(shù)據(jù)結(jié)構(gòu)與算法一一排序相關(guān)區(qū)間排序 ShortSort (Oracle) TopK算法(Knuth) TopMN算法(P.Linux)數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)冒泡排序它重復(fù)地訪問要排序的數(shù)列，一次比較兩 個元素，如果他們的順序錯誤就把他們交 換過來。訪問數(shù)列的工作是重復(fù)地進(jìn)行直 到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng) 排序完成。 FOR I = ITO N-l DO FOR J = 1+1 TO N DO IF (AiAj) THEN swap(Ai,Aj); END FOR END FOR數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)冒泡排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(n2)最優(yōu)時(shí)間復(fù)雜度：O何一一因?yàn)榭梢酝ㄟ^判

2、 斷一輪比較后是否有交換來判定排序是否 完成平均時(shí)間復(fù)雜度：O(n2)最差空間復(fù)雜度：O(n)total, 0(1) auxiliary數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān) 冒泡排序數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)選擇排序首先在未排序序列中找到最小元素，存放 到排序序列的起始位置，然后，再從剩余 未排序元素中繼續(xù)尋找最小元素，然后放 到排序序列末尾。以此類推，直到所有元 素均排序完畢。 FOR I = 1 TO N DO Ai = FindMin(bN); END FOR數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)選擇排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(n2)最優(yōu)時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(n2)最差空間復(fù)雜度:OG丿to

3、tal, Oauxiliary數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)選擇排序數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)插入排序它的工作原理是通過構(gòu)建有序序列，對于 未排序數(shù)據(jù)，在已排序序列中從后向前掃 描，找到相應(yīng)位置并插入。 FOR I = 2 TO N DO J = FindPos(lJ-l,x); 在有序的序列中找X的位置 MoveNext(JJ); /將需要占用位置的元素后移 AJ = x; /空出的位置放入X END FOR數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)插入排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(n2)最優(yōu)時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(n2)最差空間復(fù)雜度：OG丿total, Oauxiliary數(shù)據(jù)結(jié)構(gòu)與算法排序相

4、關(guān)快速排序從數(shù)列中挑出一個元素，稱為”基準(zhǔn)”，重 新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放 在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在 基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。 這個稱為分割操作。遞歸地(recursive)把 小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元 素的子數(shù)列排序。數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)快速排序數(shù)據(jù)結(jié)構(gòu)：Varies最差時(shí)間復(fù)雜度：0(n2)最優(yōu)時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：0(nlogn)comparisons最差空間復(fù)雜度根據(jù)實(shí)現(xiàn)的方式不同而不 同數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)快速排序數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)歸并排序元素首先分組，每組元素進(jìn)行比較。然后 每組元素看成一個元素，再分組比

5、較。遞 歸此過程直到只有一組元素的時(shí)候排序完 成。 void merge_sort(int arrf, int first, int last) intmid = 0; if(firstlast) mid = (first+last)/2; /分成兩組分別排序 merge_sort(airay,first, mid);/對一個分組排序 merge_sort(array/ mid+ljast);/X個分組排用 mergefarrafirstmidjast);/ 歸并兩組排序 數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)歸并排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(nlogn)最優(yōu)時(shí)間復(fù)雜度:0(n)平均時(shí)間復(fù)雜度：0(n

6、logn)最差空間復(fù)雜度：0(n)數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)歸并排序數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)堆排序堆積樹是一個近似完全二叉樹的結(jié)構(gòu)，并 同吋滿足堆的屬性：即子結(jié)點(diǎn)的鍵值或索 引總是小于（或者大于）它的父結(jié)點(diǎn)。 WHILE （堆不為空） Ai+ = GetRootFromHeap; / 取出堆根 ShiftHeap;/ 調(diào)堆 數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)樹排序首先按照搜索二叉樹對數(shù)據(jù)建樹，然后中序遍歷搜索樹，即可得到有序數(shù)列。普通二叉搜索樹，AVL平衡二叉樹等。數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)樹排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：平衡樹O(nlogn)非平衡樹O(nA2)最優(yōu)時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：

7、G(nlogn)最差空間復(fù)雜度：O(n) total, 0(1) auxiliary數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)桶排序不基于比較，為每個元素設(shè)一個計(jì)數(shù)器， 記錄每個元素出現(xiàn)多少次。 FOR I = 1 TO N DO CAi+; /將兀素丟入相中 END FOR FOR I = 1 TO MAX DO 輸出Ci個I; /講元素依次倒岀桶 END FOR數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)桶排序數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：0(n)最優(yōu)時(shí)間復(fù)雜度：0(n)平均時(shí)間復(fù)雜度：0(n)最差空間復(fù)雜度：O(MAX)total數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)基數(shù)排序?qū)⑺写容^數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長度 ，數(shù)位較短的數(shù)前面補(bǔ)零

8、.然后,從最低位開始，依 次進(jìn)行一次排序這樣從最低位排序一直到最高位 排序完成以后，數(shù)列就變成一個有序序列.基數(shù)排序的方式町以采用LSD (Least significant digital)或MSD (Most significant digital) , LSD的 排序方式由鍵值的最右邊開始，而MSD則相反， 由鍵值的最左邊開始。數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)希爾排序?qū)τ衝個元素的可比較資料，先取一個小于n的整 數(shù)dl作為第一個增量，把文件的全部記錄分成dl 個組。所有距離為dl的倍數(shù)的記錄放在同一個組 中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第 二個增量d2vdl重復(fù)上述的分紐和排序，直至所取

9、的增量dt=l(dtdt-l.d2 H0) H0 = Ai; /替換堆根 ShiftHeap(); 調(diào)堆 END FOR數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)ShortSort數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(n+nlogk)最優(yōu)時(shí)間復(fù)雜度：O(n+klogk)平均時(shí)間復(fù)雜度：G(n+xlogn) k x K) 如果左堆元素多于K個則繼續(xù)二分 LeftGroupl-now = Split(LeftGroupnow); Sort(LeftGroupl-now ); /在左堆中排序數(shù)據(jù)結(jié)構(gòu)與算法排序相關(guān)TopK數(shù)據(jù)結(jié)構(gòu)：數(shù)組最差時(shí)間復(fù)雜度：O(n+k)log(n/k)+k/ogk)最優(yōu)時(shí)間復(fù)雜度：O(n+k)log(n/k)+k/ogk)平均時(shí)間復(fù)雜度：O(n+k)log(n/k)+k/ogk)最差空間復(fù)雜度根據(jù)實(shí)現(xiàn)的方式不同而不 同優(yōu)勢：利用隨機(jī)的基準(zhǔn)，可以有效避免全排序數(shù)據(jù)結(jié)構(gòu)與算法一一排序相關(guān)TopMN排序M.N位的元素，則需要拋棄l.M-l,N+l.MAX兩部分的元素。利用二分思想，每次對元素分成 左大右小兩堆，分別處理。左堆繼續(xù)二分分出前 M1個元素，右堆繼續(xù)二分分出N+1個之后的元素 o排除無效元素后的元素集，再進(jìn)行排序。 H = Split(A); /元素分成兩堆利用TopK的思想將前個元素排到一組。利用TopK的思想將N+1位后的元素排到一組。 Sort(A,M,N).備注：可