寫出快速排序方法

❶ 快速排序法

快速排序（Quicksort）是對冒泡排序的一種改進。[1]

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。[1]

中文名
快速排序演算法
外文名
quick sort
別名
快速排序
提出者
C. A. R. Hoare
提出時間
1960年
快速
導航
排序步驟

程序調用舉例

示例代碼

性能分析
排序流程
快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：[2]
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。[2]
(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。[2]
(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。[2]
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。[2]
排序步驟
原理
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選

快排圖
用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。[1]
一趟快速排序的演算法是：[1]
1）設置兩個變數i、j，排序開始的時候：i=0，j=N-1；[1]
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；[1]
3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]的值交換；[1]
4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]的值交換；[1]
5）重復第3、4步，直到i==j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。[1]
排序演示
假設一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此時，ref=5，i=1，j=11，從後往前找，第一個比5小的數是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。
此時i=1，j=8，從前往後找，第一個比5大的數是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。
此時，i=3，j=8，從第8位往前找，第一個比5小的數是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

❷ 怎樣快速排序

❸ 排序方法有哪幾種

排序方法有：

一、直接插入排序

原理：從待排序的數中選出一個來，插入到前面的合適位置。

二、選擇排序

與直接插入排序正好辯搭悶相反，選擇排序是從待排序的數中選出最小的放在已經排好的後面，這個演算法選數耗時。

三、快速排序

快速排序簡稱快排，是一種比較快的排序，適合基本無序的數據，為什麼這么說呢？下面我說下快排的思路：設置兩個指針：i和j，分別指向第一攜彎個和最後一個，i像後移動，j向前移動，選第一個數為標准（一般這樣做，當然快排的關鍵就是這個「標准」的選取），從後面開始。

找到第一個比標准小的數，互換位置，然後再從前面，找到第一個比標准大的數，互換位置，第一趟的結果就是標准左邊的都小於標准，右邊的都大於標准（但不一定有序），分成兩撥後，繼續遞歸的使用上述方法，最終有序！

四、枝核冒泡排序

冒泡排序是一種很簡單，不論是理解還是時間起來都比較容易的一種排序演算法，思路簡單：小的數一點一點向前起泡，最終有序。

五、歸並排序

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

首先考慮下如何將將二個有序數列合並。這個非常簡單，只要從比較二個數列的第一個數，誰小就先取誰，取了後就在對應數列中刪除這個數。然後再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。

❹ 數組排序有什麼好方法

數組排序有冒泡排序法、選擇排序法、插入排序法和快速排序法。

1、冒泡排序法。冒泡排序是一個比較簡笑含單的排序方法。在待排序的數列基本有序的情況下排序速度較快。

2、選擇排序法。選擇法的原理是先將拆冊第一個數與後面的每一個數依次比較，不斷將將小的賦給第一個數，從而找出最小的值。

旅升宏3、插入排序法。插入排序對少量元素的排序較為有效。

4、快速排序法。快速排序法的原理是通過一次排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。