關(guān)于加密算法中 排序的總結(jié)
ice ???? 加密過程中我們通常會(huì)講各種加密方法和算法，但是這樣的方法我們?cè)趹?yīng)用的過程中可能并不會(huì)完全說明白，其中排序算法經(jīng)過了很長時(shí)間的演變，產(chǎn)生了很多種不同的方法。對(duì)于初學(xué)者來說，對(duì)它們進(jìn)行整理便于理解記憶顯得很重要。每種算法都有它特定的使用場合，很難通用。因此，我們很有必要對(duì)所有常見的排序算法進(jìn)行歸納。
???? 我不喜歡死記硬背，我更偏向于弄清來龍去脈，理解性地記憶。比如下面這張圖，我們將圍繞這張圖來思考幾個(gè)問題。
???? 上面的這張圖來自一個(gè)PPT。它概括了數(shù)據(jù)結(jié)構(gòu)中的所有常見的排序算法。現(xiàn)在有以下幾個(gè)問題：
???? 1、每個(gè)算法的思想是什么？?
2、每個(gè)算法的穩(wěn)定性怎樣？時(shí)間復(fù)雜度是多少？?
3、在什么情況下，算法出現(xiàn)最好情況 or 最壞情況？?
4、每種算法的具體實(shí)現(xiàn)又是怎樣的？
???? 這個(gè)是排序算法里面最基本，也是最?？嫉膯栴}。下面是我的小結(jié)。
一、直接插入排序(插入排序)。
???? 1、算法的偽代碼(這樣便于理解)：????
???? INSERTION-SORT (A, n)???????????? A[1 . . n]?
for j ←2 to n?
do key ← A[ j]?
i ← j – 1?
while i > 0 and A[i] > key?
do A[i+1] ← A[i]?
i ← i – 1?
A[i+1] = key
???? 2、思想：如下圖所示，每次選擇一個(gè)元素K插入到之前已排好序的部分A[1…i]中，插入過程中K依次由后向前與A[1…i]中的元素進(jìn)行比較。若發(fā)現(xiàn)發(fā)現(xiàn)A[x]>=K,則將K插入到A[x]的后面，插入前需要移動(dòng)元素。
???? 3、算法時(shí)間復(fù)雜度。??
??????? 最好的情況下：正序有序(從小到大)，這樣只需要比較n次，不需要移動(dòng)。因此時(shí)間復(fù)雜度為O(n)??
最壞的情況下：逆序有序,這樣每一個(gè)元素就需要比較n次，共有n個(gè)元素，因此實(shí)際復(fù)雜度為O(n-2)??
平均情況下：O(n-2)
???? 4、穩(wěn)定性。??
???? 理解性記憶比死記硬背要好。因此，我們來分析下。穩(wěn)定性，就是有兩個(gè)相同的元素，排序先后的相對(duì)位置是否變化，主要用在排序時(shí)有多個(gè)排序規(guī)則的情況下。在插入排序中，K1是已排序部分中的元素，當(dāng)K2和K1比較時(shí)，直接插到K1的后面(沒有必要插到K1的前面，這樣做還需要移動(dòng)??！)，因此，插入排序是穩(wěn)定的。
?????5、代碼(c版) blog.csdn.com/whuslei?
??????????
二、希爾排序(插入排序)
???? 1、思想：希爾排序也是一種插入排序方法,實(shí)際上是一種分組插入方法。先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把表的全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中,在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂????
???? 例如：將 n 個(gè)記錄分成 d 個(gè)子序列：?
{ R[0]，?? R[d]，???? R[2d]，…，???? R[kd] }?
{ R[1]，?? R[1+d]， R[1+2d]，…，R[1+kd] }?
…?
{ R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
?????
?
說明：d=5 時(shí)，先從A[d]開始向前插入，判斷A[d-d]，然后A[d+1]與A[(d+1)-d]比較，如此類推，這一回合后將原序列分為d個(gè)組。<由后向前>
???? 2、時(shí)間復(fù)雜度。??
?????最好情況：由于希爾排序的好壞和步長d的選擇有很多關(guān)系，因此，目前還沒有得出最好的步長如何選擇(現(xiàn)在有些比較好的選擇了，但不確定是否是最好的)。所以，不知道最好的情況下的算法時(shí)間復(fù)雜度。??
?最壞情況下：O(N*logN)，最壞的情況下和平均情況下差不多。??
?平均情況下：O(N*logN)
???? 3、穩(wěn)定性。??
由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。(有個(gè)猜測，方便記憶：一般來說，若存在不相鄰元素間交換，則很可能是不穩(wěn)定的排序。)
???? 4、代碼(c版) blog.csdn.com/whuslei?
??????????
?
三、冒泡排序(交換排序)
?????? 1、基本思想：通過無序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換,使關(guān)鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。?
?????
????? 2、時(shí)間復(fù)雜度??
最好情況下：正序有序，則只需要比較n次。故，為O(n)??
?最壞情況下:??逆序有序，則需要比較(n-1)+(n-2)+……+1，故，為O(N*N)
????? 3、穩(wěn)定性??
????? 排序過程中只交換相鄰兩個(gè)元素的位置。因此，當(dāng)兩個(gè)數(shù)相等時(shí)，是沒必要交換兩個(gè)數(shù)的位置的。所以，它們的相對(duì)位置并沒有改變，冒泡排序算法是穩(wěn)定的！
????? 4、代碼(c版) blog.csdn.com/whuslei?
??????????
四、快速排序(交換排序)
???? 1、思想：它是由冒泡排序改進(jìn)而來的。在待排序的n個(gè)記錄中任取一個(gè)記錄(通常取第一個(gè)記錄),把該記錄放入適當(dāng)位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個(gè)過程稱作一趟快速排序。
?????????? 說明：最核心的思想是將小的部分放在左邊，大的部分放到右邊，實(shí)現(xiàn)分割。?????????
2、算法復(fù)雜度??
??????最好的情況下：因?yàn)槊看味紝⑿蛄蟹譃閮蓚€(gè)部分(一般二分都復(fù)雜度都和logN相關(guān))，故為 O(N*logN)??
?最壞的情況下：基本有序時(shí)，退化為冒泡排序，幾乎要比較N*N次，故為O(N*N)
??????3、穩(wěn)定性??
????? 由于每次都需要和中軸元素交換，因此原來的順序就可能被打亂。如序列為 5 3 3 4 3 8 9 10 11會(huì)將3的順序打亂。所以說，快速排序是不穩(wěn)定的！
??????4、代碼(c版)?
???????????
五、直接選擇排序(選擇排序)
????? 1、思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。具體做法是：選擇最小的元素與未排序部分的首部交換，使得序列的前面為有序。??
????? 2、時(shí)間復(fù)雜度。?
??????最好情況下：交換0次，但是每次都要找到最小的元素，因此大約必須遍歷N*N次，因此為O(N*N)。減少了交換次數(shù)！?
?最壞情況下，平均情況下：O(N*N)
????? 3、穩(wěn)定性?
????? 由于每次都是選取未排序序列A中的最小元素x與A中的第一個(gè)元素交換，因此跨距離了，很可能破壞了元素間的相對(duì)位置，因此選擇排序是不穩(wěn)定的！
????? 4、代碼(c版)blog.csdn.com/whuslei?
??????????
六、堆排序
???? 1、思想：利用完全二叉樹中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或者最小)的記錄。也就是說，以最小堆為例，根節(jié)點(diǎn)為最小元素，較大的節(jié)點(diǎn)偏向于分布在堆底附近。?
????? 2、算法復(fù)雜度?
???????? 最壞情況下，接近于最差情況下：O(N*logN)，因此它是一種效果不錯(cuò)的排序算法。
????? 3、穩(wěn)定性?
???????? 堆排序需要不斷地調(diào)整堆，因此它是一種不穩(wěn)定的排序！
????? 4、代碼(c版，看代碼后更容易理解！)??????
?
七、歸并排序
????? 1、思想：多次將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。?
?????? 2、算法時(shí)間復(fù)雜度?
??????????最好的情況下：一趟歸并需要n次，總共需要logN次，因此為O(N*logN)?
?最壞的情況下，接近于平均情況下，為O(N*logN)?
?說明：對(duì)長度為n的文件，需進(jìn)行l(wèi)ogN 趟二路歸并，每趟歸并的時(shí)間為O(n)，故其時(shí)間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
????? 3、穩(wěn)定性?
???????? 歸并排序最大的特色就是它是一種穩(wěn)定的排序算法。歸并過程中是不會(huì)改變?cè)氐南鄬?duì)位置的。?
4、缺點(diǎn)是，它需要O(n)的額外空間。但是很適合于多鏈表排序。?
5、代碼(略)blog.csdn.com/whuslei
八、基數(shù)排序
??????1、思想：它是一種非比較排序。它是根據(jù)位的高低進(jìn)行排序的，也就是先按個(gè)位排序，然后依據(jù)十位排序……以此類推。示例如下：?
??????? 2、算法的時(shí)間復(fù)雜度?
?????? 分配需要O(n),收集為O(r),其中r為分配后鏈表的個(gè)數(shù)，以r=10為例，則有0～9這樣10個(gè)鏈表來將原來的序列分類。而d，也就是位數(shù)(如最大的數(shù)是1234，位數(shù)是4，則d=4)，即"分配-收集"的趟數(shù)。因此時(shí)間復(fù)雜度為O(d*(n+r))。
?????? 3、穩(wěn)定性?
????????? 基數(shù)排序過程中不改變?cè)氐南鄬?duì)位置，因此是穩(wěn)定的！
?????? 4、適用情況：如果有一個(gè)序列，知道數(shù)的范圍(比如1～1000)，用快速排序或者堆排序，需要O(N*logN)，但是如果采用基數(shù)排序，則可以達(dá)到O(4*(n+10))=O(n)的時(shí)間復(fù)雜度。算是這種情況下排序最快的?。?/span>
?????? 5、代碼(略)
???? 總結(jié)： 每種算法都要它適用的條件，本文也僅僅是回顧了下基礎(chǔ)。如有不懂的地方請(qǐng)參考課本。
