以下是圖排序演算法的有

A. 數據結構的排序演算法中，哪些排序是穩定的，哪些排序是不穩定的

一、穩定排序演算法

1、冒泡排序

2、雞尾酒排序

3、插入排序

4、桶排序

5、計數排序

6、合並排序

7、基數排序

8、二叉排序樹排序

二、不穩定排序演算法

1、選擇排序

2、希爾排序

3、組合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。

做這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

(1)以下是圖排序演算法的有擴展閱讀：

排序演算法的分類：

1、通過時間復雜度分類

計算的復雜度（最差、平均、和最好性能），依據列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且壞的性能是 O(n^2)。對於一個排序理想的性能是 O(n)。

而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要 O(nlogn)。

2、通過空間復雜度分類

存儲器使用量（空間復雜度）（以及其他電腦資源的使用）

3、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。

B. 數學排列組合的演算法、如圖兩個、有什麼區別、求演算法謝謝

給你解釋下 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)
不知道我這樣說你能不能聽明白

C. O（n2）排序演算法的總結

最近在慕課網上學習了O（n2）時間復雜度的相關演算法，總算是對這些演算法的優缺點有了詳細的特點。其實對於任何的演算法，沒有優點和缺點，而是有相應的特點。所以我們應該結合不同的排序環境來選擇不同的排序演算法，從而達到在實現時間和執行效率上的平衡。這是因為，越是簡單的排序演算法，實現起來肯定是越容易，而且出現BUG的概率也不會太大。相反，復雜演算法可能效率更高，但是出現問題的可能性也會更大。下面，我就結合O（n2）時間復雜度的四個經典排序演算法，為您詳細講解這四個演算法的特點。

定義：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

圖示說明：

源碼實現：

分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進行兩次循環，而且最關鍵的是內層循環在每一次執行時都是全部執行完的。那我們有沒有辦法讓內層循環不用每次都執行完呢？方法肯定是有的，這就是冒泡排序。

定義：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。

圖示說明：

源碼實現：

分析：從圖示和源碼可以看出來，從執行次數上來說，冒泡排序是比選擇排序的循環次數更少的。那是不是就可以說，如果待排序的數組中元素比較合適，冒泡排序在時間復雜度上是不是會比選擇排序更好呢？真的是這樣的嗎？

其實不是的，經過多次測試驗證，冒泡排序基本上是比選擇排序的時間復雜度要差的，這是為什麼呢？從源碼中我們可以很明顯的看出來，雖然冒泡排序是比選擇排序執行次數少了，但是交換的次數明顯增多了，而如果你對計算機程序指令的實現原理只要有一個基本的認識，就應該知道交換動作比賦值動作是需要更多指令操作的。所以說，最終冒泡排序大部分情況下，比選擇排序的時間復雜度都要高。

既然交換動作這么消耗資源，那有沒有一種方法，即能夠減少內層循環的執行次數，又可以減少甚至是無需交換操作呢？這就要請出插入排序了。

定義：插入排序（Insertion Sort）的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，即每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

圖示說明：

源碼實現：

分析：從圖示和源碼可以看出來，插入排序（優化後的）是沒有交換操作的，而且對於內層循環來說，如果待排序的元素是比較大的值，那內層循環執行的次數會非常的少。因此，如果原始數據基本上是有序的，那使用插入排序的效率會非常的高。在O（n2）級別的排序演算法還可以再優化嗎？如果可以從哪裡優化呢？下面我們來介紹希爾排序，正是這個排序演算法的提出，使得排序演算法打破了O（n2）時間復雜度的禁錮。

定義：希爾排序(Shell's Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。該演算法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，排序演算法便終止。

對於希爾排序來說，最關鍵的就是增量該如何選取。這個增量該怎麼確定，這還真是個數學難題，至今沒有解答。但是通過大量的實驗，還是有個經驗值的。我們的例子給出的增量選取公式是：h = 3 * h + 1，下面請看圖示說明。

圖示說明：

源碼實現：

分析：從插入排序中我們知道，插入排在待排序數組基本有序時，插入排序的演算法效率會非常高，所以我們可以這樣認為，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，在對全體進行一次直接插入排序。

而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當h值大的時候，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長。這是非常有效率的。而當h減小時，每一趟排序需要移動的元素的個數增多，但是此時數據項已經接近於它們排序後最終的位置，這對於插入排序可以更有效率。正是這兩種情況的結合才使希爾排序效率那麼高。

對於增量的選取，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2，簡單地把每一趟排序分成了兩半。但是，這被證明並不是最好的數列。盡管對於大多數的數據來說這個方法還是比插入排序效果好，但是這種方法有時會使運行時間降到O(N2)，這並不比插入排序的效率更高。間隔序列中的數字互質通常被認為很重要：也就是說，除了1之外它們沒有公約數。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果。希爾最初以N/2為間隔的低效性就是歸咎於它沒有遵守這個准則。

總結：上面就是四種經典O（n2）級別排序演算法的相關說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的，因為使用場景基本沒有。而對於插入排序和希爾排序來說，在待排序數據基本有序的情況下，使用場景還是有的，比如一些日誌文件中存儲的日誌，可能大部分的日誌記錄都是基於時間排序，只是在某些極端情況下導致一些日誌晚存儲了導致時間不一致。

我是徐建航， 這是我寫的第31篇文章，歡迎你加入007社群，七天寫一篇，一起寫七年，七年之後一起去南極。

D. 排序演算法總結

排序演算法是什麼?有多少種?排序演算法總結又是怎樣?以下是為您整理的排序演算法總結，供您參考!

【排序演算法總結】

排序演算法：一種能將一串數據依照特定的排序方式進行排列的一種演算法。

排序演算法性能：取決於時間和空間復雜度，其次還得考慮穩定性，及其適應的場景。

穩定性：讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序演算法是穩定的，當有倆個相等鍵值的記錄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)。

總結

以上排序演算法的時間、空間與穩定性的總結如下：

E. 常見排序演算法歸納

排序演算法一般分類：

比較兩個相鄰的元素，將值大的元素交換至右端。

依次比較兩個相鄰的數，將小數放到前面，大數放到後面

即在第一趟：首先比較第1個數和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此一直繼續下去，直到比較最後兩個數，將小數放前，大數放後。然後重復第一趟步驟，直到所有排序完成。

第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較。

第二趟完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較。

依次類推......

輸出結果：

冒泡排序的優點： 每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之後，排在最後的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最後一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數後面，第三趟比較的時候，只需要比較除了最後兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了演算法的量。

用時間復雜度來說：

從一個數組中隨機選出一個數N，通過一趟排序將數組分割成三個部分，1、小於N的區域 2、等於N的區域 3、大於N的區域，然後再按照此方法對小於區的和大於區分別遞歸進行，從而達到整個數據變成有序數組。

如下圖：

假設最開始的基準數據為數組的第一個元素23，則首先用一個臨時變數去存儲基準數據，即 tmp=23 ，然後分別從數組的兩端掃描數組，設兩個指示標志： low 指向起始位置， high 指向末尾。

首先從後半部分開始，如果 掃描到的值大於基準數據 就讓 high-1 ，如果發現有元素比該基準數據的值小，比如上面的 18 <= tmp ，就讓 high位置的值賦值給low位置 ，結果如下：

然後開始從前往後掃描，如果掃描到的值小於基準數據就讓 low+1 ，如果發現有元素大於基準數據的值，比如上圖 46 >= tmp ，就再將 low 位置的值賦值給 high 位置的值，指針移動並且數據交換後的結果如下：

然後再開始從前往後遍歷，直到 low=high 結束循環，此時low或者high的下標就是 基準數據23在該數組中的正確索引位置 ，如下圖所示：

這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數據小的都放到基準數的左邊，比基準數大的數都放到基準數的右邊，這樣就找到了該數據在數組中的正確位置。

然後採用遞歸的方式分別對前半部分和後半部分排序，最終結果就是自然有序的了。

輸出結果：

最好情況下快排每次能恰好均分序列，那麼時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。

將一個數據插入到 已經排好序的有序數據 中

第一趟排序：

用數組的第二個數與第一個數( 看成是已有序的數據 )比較

第二趟排序：

用數組的第三個數與已是有序的數據 {2,3} (剛才在第一趟排的)比較

在第二步中：

...

後面依此類推

輸出結果：

選擇排序是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

舉例：數組 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始數據： 5 2 8 4 9 1

最小數據1，把1放在首位，也就是1和5互換位置，

排序結果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的數據 {2 8 4 9 5} 進行比較，2最小，

排序結果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的數據 {8 4 9 5} 進行比較，4最小，8和4交換

排序結果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他數據 {8 9 5} 進行比較，5最小，8和5交換

排序結果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他數據 {9 8} 進行比較，8最小，8和9交換

排序結果： 1 2 4 5 8 9

輸出結果：

歸並排序（merge sort）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

比如我們對 [8,4,5,7,1,3,6,2] 這個數組進行歸並排序，我們首先利用分治思想的「分」將數組拆分。

輸出結果：