㈠ 排序演算法總結
排序演算法是什麼?有多少種?排序演算法總結又是怎樣?以下是為您整理的排序演算法總結，供您參考!
排序演算法：一種能將一串數據依照特定的排序方式進行排列的一種演算法。
排序演算法性能：取決於時間和空間復雜度，其次還得考慮穩定性，及其適應的場景。
穩定性：讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序演算法是穩定的，當有倆個相等鍵值的記錄R和S，且原本的序列中R在S前，那麼排序後的列表中R應該也在S之前。
以下來總結常用的排序演算法，加深對排序的理解。
冒泡排序
原理
倆倆比較相鄰記錄的排序碼，若發生逆序，則交旅派配換;有倆種方式進行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到後邊。
性能
時間復雜度為O(N^2)，空間復雜度為O(1)。排序是穩定的，排序比較次數與初始序列無關，但交換次數與初始序列有關。
優化
若初始序列就是排序好的，對於冒泡排序仍然還要比較O(N^2)次，但無交換次數。可根據這個進行優化，設置一個flag，當在一趟序列中沒有發生交換，則該序列已排序好，但優化後排序的時間復雜度沒有發生量級的改變。
代碼
插入排序
原理
依次選擇一個待排序的數據，插入到前邊已排好序的序列中。
性能
時間復雜度為O(N^2)，空間復雜度為O(1)。演算法是穩定的，比較次數和交換次數都與初始序列有關。
優化
直接插入排序每次往前插入時，是按順序依次往前找，可在這里進行優化，往前找合適的插入位置時採用二分查找的方式，即折半插入。
折半插入排序相對直接插入排序而言：平均性能更快，時間復雜度降至O(NlogN)，排序是穩定的，但排序的比較次數與初始序列無關，總是需要foor(log(i))+1次排序比較。
使用場景
當數據基本有序時，採用插入排序可以明顯減少數據交換和數據移動次數，進而提升排序效率。
代碼
希爾排拆指序
原理
插入排序的改進版，是基於插入排序的以下倆點性質而提出的改進方法：
插入排序對幾乎已排好序的數據操作時，效率很高，可以達到線性排序的效率。
但插入排序在每次往前插入時只能將數據移動一位，效率比較低。
所以希爾排序的思想是：
先是取一個合適的gap
縮小間隔gap，例如去gap=ceil(gap/2)，重復上述子序列劃分和排序
直到，最後gap=1時，將所有元素放在同一個序列中進行插入排序為止。
性能
開始時，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點;其次，gap值逐漸變小後，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優點，能以近線性的速度排好序。
代碼
選擇排序
原理
每次從未排序的序列中找到最小值，記錄並最後存放到已排序序羨碰列的末尾
性能
時間復雜度為O(N^2)，空間復雜度為O(1)，排序是不穩定的(把最小值交換到已排序的末尾導致的)，每次都能確定一個元素所在的最終位置，比較次數與初始序列無關。
代碼
快速排序
原理
分而治之思想：
Divide：找到基準元素pivot，將數組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1…q]，左邊的元素都比基準小，右邊的元素都比基準大;
Conquer：對倆個劃分的數組進行遞歸排序;
Combine：因為基準的作用，使得倆個子數組就地有序，無需合並操作。
性能
快排的平均時間復雜度為O(NlogN)，空間復雜度為O(logN)，但最壞情況下，時間復雜度為O(N^2)，空間復雜度為O(N);且排序是不穩定的，但每次都能確定一個元素所在序列中的最終位置，復雜度與初始序列有關。
優化
當初始序列是非遞減序列時，快排性能下降到最壞情況，主要因為基準每次都是從最左邊取得，這時每次只能排好一個元素。
所以快排的優化思路如下：
優化基準，不每次都從左邊取，可以進行三路劃分，分別取最左邊，中間和最右邊的中間值，再交換到最左邊進行排序;或者進行隨機取得待排序數組中的某一個元素，再交換到最左邊，進行排序。
在規模較小情況下，採用直接插入排序
代碼
歸並排序
原理
分而治之思想：
Divide：將n個元素平均劃分為各含n/2個元素的子序列;
Conquer：遞歸的解決倆個規模為n/2的子問題;
Combine：合並倆個已排序的子序列。
性能
時間復雜度總是為O(NlogN)，空間復雜度也總為為O(N)，演算法與初始序列無關，排序是穩定的。
優化
優化思路：
在規模較小時，合並排序可採用直接插入;
在寫法上，可以在生成輔助數組時，倆頭小，中間大，這時不需要再在後邊加倆個while循環進行判斷，只需一次比完。
代碼
堆排序
原理
堆的性質：
是一棵完全二叉樹
每個節點的值都大於或等於其子節點的值，為最大堆;反之為最小堆。
堆排序思想：
將待排序的序列構造成一個最大堆，此時序列的最大值為根節點
依次將根節點與待排序序列的最後一個元素交換
再維護從根節點到該元素的前一個節點為最大堆，如此往復，最終得到一個遞增序列
性能
時間復雜度為O(NlogN)，空間復雜度為O(1)，因為利用的排序空間仍然是初始的序列，並未開辟新空間。演算法是不穩定的，與初始序列無關。
使用場景
想知道最大值或最小值時，比如優先順序隊列，作業調度等場景。
代碼
計數排序
原理
先把每個元素的出現次數算出來，然後算出該元素所在最終排好序列中的絕對位置(最終位置)，再依次把初始序列中的元素，根據該元素所在最終的絕對位置移到排序數組中。
性能
時間復雜度為O(N+K)，空間復雜度為O(N+K)，演算法是穩定的，與初始序列無關，不需要進行比較就能排好序的演算法。
使用場景
演算法只能使用在已知序列中的元素在0-k之間，且要求排序的復雜度在線性效率上。
代碼
桶排序
原理
根據待排序列元素的大小范圍，均勻獨立的劃分M個桶
將N個輸入元素分布到各個桶中去
再對各個桶中的元素進行排序
此時再按次序把各桶中的元素列出來即是已排序好的。
性能
時間復雜度為O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空間復雜度為O(N+M)，演算法是穩定的，且與初始序列無關。
使用場景
演算法思想和散列中的開散列法差不多，當沖突時放入同一個桶中;可應用於數據量分布比較均勻，或比較側重於區間數量時。
基數排序
原理
對於有d個關鍵字時，可以分別按關鍵字進行排序。有倆種方法：
MSD：先從高位開始進行排序，在每個關鍵字上，可採用計數排序
LSD：先從低位開始進行排序，在每個關鍵字上，可採用桶排序
性能
時間復雜度為O(d*(N+K))，空間復雜度為O(N+K)。
總結
以上排序演算法的時間、空間與穩定性的總結如下：
㈡ 各種排序演算法實現和比較
1、 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
注意：
①堆中任一子樹亦是堆。
②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序特點
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。
4、堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。
（3）堆排序的演算法：
void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
} //endfor
} //HeapSort
（4） BuildHeap和Heapify函數的實現
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。
① Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換後，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小於這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換後又可能使結點R[large]違反堆性質，同樣由於該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。
具體的演算法
②BuildHeap的實現
要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。
顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結點作為根的子樹都調整為堆即可。
具體演算法。
5、大根堆排序實例
對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。
6、 演算法分析
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。
㈢ 八大經典排序演算法原理及實現
該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。
冒泡排序演算法應該是大家第一個接觸的演算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：
按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析
空間復雜度就是在交換元素時那個臨時變數所佔的內存
給定一個整數序列{6,1,2,3,4},每完成一次外層循環的結果為：
我們發現第一次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麼優化？
冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序演算法是穩定性演算法
插入排序是對冒泡排序的一種改進
插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這里 ）
空間復雜度就是在交換元素時那個臨時變數所佔的內存
插入排序的優化，有兩種方案：
文章後面會給出這兩種排序演算法
由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化
其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面
空間復雜度就是在交換元素時那個臨時變數所佔的內存
選擇排序是不穩定的，比如 3 6 3 2 4，第一次外層循環中就會交換第一個元素3和第四個元素2，那麼就會導致原序列的兩個3的相對位置發生變化
希爾排序算是改良版的插入排序演算法，所以也稱為希爾插入排序演算法
其原理是將序列分割成若乾子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：
希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)
空間復雜度就是在交換元素時那個臨時變數所佔的內存
希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的
理解堆排序，就必須得先知道什麼是堆？
二叉樹的特點：
當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為一個二叉堆
一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)
怎麼將給定的數組序列按照堆的性質，調整為堆？
這里以建立最小堆為示例，
很明顯對於其葉子結點來說，已經是一個合法的子堆，所以做堆調整時，子節點沒有必要進行，這里只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：
由於每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。
空間復雜度就是在交換元素時那個臨時變數所佔的內存
由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則演算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第一個5和第三個5的相對位置發生變化
歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
快速排序在應該是大家經常看到、聽到的演算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。
其原理就這么幾句話，但是現實起來並不是這么簡單，我們採取流行的一種方式 挖坑填數分治法
對於序列： 72 6 57 88 60 42 83 73 48 85
數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：
數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了
空間復雜度，主要是遞歸造成的棧空間的使用:
快速排序的優化主要在於基準數的選取
快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定
前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，採用二分查找演算法進行插入位置的確定
具體步驟，設數組為a[0…n]：
二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：
二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的
白話經典演算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序
㈣ 數學排列組合的演算法、如圖兩個、有什麼區別、求演算法謝謝
給你解釋下 A(4，6)的意思 A(4，6)的意思是對6個數中的4個做組合的情況個數
首先，第一個數的位置有多少種情況？是6種，在這之後第二個數呢，因為第一個數占據了一個位置所以是5種 以此類推後面是4、3種 那為什麼是6*5*4*3呢 而不是6+5+4+3呢 因為這四個事件不是互斥的
C(4,6) = A(4，6) / (4 * 3 * 2 * 1) 為什麼要除以4 * 3 * 2 * 1呢 C(4,6)的意思是從6個數中取出4個數 但是不要求排序 這點是和A是有區別的 因為A(4，6)不僅取出了4個數而且對4個數進行了排序 也就是說在C(4,6)中每次從6個數中取出4個數的情況數是1 而在A(4,6)中的情況數卻是A(4,4) 所以這個比例關系是 1：A(4,4)的關系 所以要除以A(4,4) 也就是C(4,6) = A(4，6) / A(4,4)
不知道我這樣說你能不能聽明白