1.快速排序

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

需求：

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理：

1.首先設定一個分界值，通過該分界值將數組分成左右兩部分；

2.將大于或等于分界值的數據放到到數組右邊，小于分界值的數據放到數組的左邊。此時左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值；

3.然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

4.重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左側和右側兩個部分的數據排完序后，整個數組的排序也就完成了。

切分原理：

把一個數組切分成兩個子數組的基本思想：

1.找一個基準值，用兩個指針分別指向數組的頭部和尾部；

2.先從尾部向頭部開始搜索一個比基準值小的元素，搜索到即停止，并記錄指針的位置；

3.再從頭部向尾部開始搜索一個比基準值大的元素，搜索到即停止，并記錄指針的位置；

4.交換當前左邊指針位置和右邊指針位置的元素；

5.重復2,3,4步驟，直到左邊指針的值大于右邊指針的值停止。

快速排序和歸并排序的區別：

快速排序是另外一種分治的排序算法，它將一個數組分成兩個子數組，將兩部分獨立的排序。快速排序和歸并排序是互補的：歸并排序將數組分成兩個子數組分別排序，并將有序的子數組歸并從而將整個數組排序，而快速排序的方式則是當兩個數組都有序時，整個數組自然就有序了。在歸并排序中，一個數組被等分為兩半，歸并調用發生在處理整個數組之前，在快速排序中，切分數組的位置取決于數組的內容，遞歸調用發生在處理整個數組之后。

快速排序時間復雜度分析：

快速排序的一次切分從兩頭開始交替搜索，直到left和right重合，因此，一次切分算法的時間復雜度為O(n),但整個快速排序的時間復雜度和切分的次數相關。

最優情況：每一次切分選擇的基準數字剛好將當前序列等分。

如果我們把數組的切分看做是一個樹，那么上圖就是它的最優情況的圖示，共切分了logn次，所以，最優情況下快速排序的時間復雜度為O(nlogn);

最壞情況：每一次切分選擇的基準數字是當前序列中最大數或者最小數，這使得每次切分都會有一個子組，那么總共就得切分n次，所以，最壞情況下，快速排序的時間復雜度為O(n^2);

平均情況：每一次切分選擇的基準數字不是最大值和最小值，也不是中值，這種情況我們也可以用數學歸納法證明，快速排序的時間復雜度為O(nlogn),由于數學歸納法有很多數學相關的知識，容易使我們混亂，所以這里就不對平均情況的時間復雜度做證明了。

2. 排序的穩定性

穩定性的定義：

數組arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某種排序算法排序后，能夠保證A元素依然在B元素的前面，可以說這個該算法是穩定的。

穩定性的意義：

如果一組數據只需要一次排序，則穩定性一般是沒有意義的，如果一組數據需要多次排序，穩定性是有意義的。例如要排序的內容是一組商品對象，第一次排序按照價格由低到高排序，第二次排序按照銷量由高到低排序，如果第二次排序使用穩定性算法，就可以使得相同銷量的對象依舊保持著價格高低的順序展現，只有銷量不同的對象才需要重新排序。這樣既可以保持第一次排序的原有意義，而且可以減少系統開銷。

常見排序算法的穩定性：

冒泡排序：

只有當arr[i]>arr[i+1]的時候，才會交換元素的位置，而相等的時候并不交換位置，所以冒泡排序是一種穩定排序算法。

選擇排序:

選擇排序是給每個位置選擇當前元素最小的,例如有數據{5(1)，8 ，5(2)，?2，?9 },第一遍選擇到的最小元素為2，所以5(1)會和2進行交換位置，此時5(1)到了5(2)后面，破壞了穩定性，所以選擇排序是一種不穩定的排序算法。

插入排序：

比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

希爾排序：

希爾排序是按照不同步長對元素進行插入排序?,雖然一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以希爾排序是不穩定的。

歸并排序：

歸并排序在歸并的過程中，只有arr[i]的時候才會交換位置，如果兩個元素相等則不會交換位置，所以它并不會破壞穩定性，歸并排序是穩定的。

快速排序：

快速排序需要一個基準值，在基準值的右側找一個比基準值小的元素，在基準值的左側找一個比基準值大的元素，然后交換這兩個元素，此時會破壞穩定性，所以快速排序是一種不穩定的算法。

總結

以上是生活随笔為你收集整理的9个元素换6次达到排序序列_（算法四）高级排序（快速排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。