演算法快速排序方法

⑴ 以下哪種排序演算法對進行的排序最快

1.選擇排序：不穩定，時間復雜度
O(n^2)
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
2.插入排序：穩定，時間復雜度
O(n^2)
插入排序的基本思想是，經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]
又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤
L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j]
≤L[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
3.冒泡排序：穩定，時間復雜度
O(n^2)
冒泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的「氣泡」，較小的元素比較輕，從而要往上浮。在冒泡排序演算法中我們要對這個「氣泡」序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即「輕」的元素在下面，就交換它們的位置。顯然，處理一遍之後，「最輕」的元素就浮到了最高位置；處理二遍之後，「次輕」的元素就浮到了次高位置。在作第二遍處理時，由於最高位置上的元素已是「最輕」元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
4.堆排序：不穩定，時間復雜度
O(nlog
n)
堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
5.歸並排序：穩定，時間復雜度
O(nlog
n)
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸並為一個有序數列，並存儲在A[l..h]。
6.快速排序：不穩定，時間復雜度
最理想
O(nlogn)
最差時間O(n^2)
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。
幾種排序的時間復雜度，可以參考一下

⑵ 在各類演算法中那種演算法排序是最快的

說句實話，沒有最快這一說。

1. 如果不在乎浪費空間，應該是桶排序最快

2. 如果整體基本有序，插入排序最快

3. 如果考慮綜合情況，快速排序更加實用常見（希爾排序、堆排序等各種排序也各有優劣）

4. 一般情況下，冒泡這種排序僅僅是名字起的有趣罷了，不太好用

⑶ 寫出快速排序的演算法

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

⑷ 快速排序法

快速排序（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。

⑸ 排序演算法有哪些，簡述快速排序的核心

簡單的: 冒泡,選擇排序,插入排序,桶排序,

復雜點的: 堆排序,歸並排序,快速排序,

還有基數排序,計數排序(這兩個我還沒接觸到,不懂)

快速排序核心:

每次排序的時候設置一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣只能在相鄰的數之間進行交換，交換的距離就大得多了。因此總的比較和交換次數就少了，速度自然就提高了。

圖片及快速排序簡述來源於<啊哈演算法>

⑹ 快速排序的演算法實現

#include<iostream>
using namespace std;
const int n=10;
void input(int a[],int n)
{
for(int i=0;i<n;++i)
a[i]=rand()%100;
}
void print(int a[],int n)
{
for(int i=0;i<n;++i)
cout<<a[i]<<'\t';
cout<<endl;
}
int p(int a[],int l,int r)
{
int i=l,j=r; //初始化
while(i<j)
{
while(i<j&&a[i]<a[j]) j--; //右側掃描
if(i<j)
{
swap(a[i],a[j]);//將較小記錄交換到前面
i++;
}
while(i<j&&a[i]<a[j]) i++;//左側掃描
if(i<j)
{
swap(a[j],a[i]);//將較大記錄交換到後面
j--;
}
}
return i; // i位軸值記錄的最終位置
}
void quicksort(int a[],int l,int r)
{
if(l<r)
{
int pivot=p(a,l,r); //一次劃分
quicksort(a,l,pivot-1);//遞歸對左側子序列快排
quicksort(a,pivot+1,r);//遞歸對右側子序列快排
}
}

int main()
{
int a[n];
input(a, n);
print(a, n);
quicksort(a, 0,n-1);
print(a, n);

return 0;
}

⑺ 快速排序演算法（free pascal)詳解，不要源程序，時間復雜度n（logn）；謝了//

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

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5）、重復第3、4步，直到I>j；

詳細過程舉例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61

快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procere qsort(l,r:longint);{r，l表示集合的左右邊界，即把第r到第l個數進行排序}
var i,j,m:longint;
begin
m:=a[l];{標准數}
i:=l; {I，J為指針}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一個數則進入下一層遞歸，l，J為新邊界}
if i<rthen qsort(i,r); {如果集合中不止一個數則進入下一層遞歸，i，r為新邊界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.

⑻ 快速排序演算法原理與實現

快速排序的原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2、以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5、重復第3、4步，直到I=J。

(8)演算法快速排序方法擴展閱讀：

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。

值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。

一趟快速排序的演算法是：

1、設置兩個變數i、j，排序開始的時候：i=0，j=N-1；

2、以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3、從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]的值賦給A[i]；

4、從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]的值賦給A[j]；

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指針位置不變。

⑼ C語言的快速排序的演算法是什麼啊

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 演算法過程設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。 一趟快速排序的演算法是： 1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1； 2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]； 3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與key交換； 4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與key交換； 5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後另循環結束。) 例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。 A[0] A[1] A[2] A[3] A[4] A[5] A[6]： 49 38 65 97 76 13 27 進行第一次交換後：27 38 65 97 76 13 49 ( 按照演算法的第三步從後面開始找) 進行第二次交換後：27 38 49 97 76 13 65 ( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 ) 進行第三次交換後：27 38 13 97 76 49 65 ( 按照演算法的第五步將又一次執行演算法的第三步從後開始找 進行第四次交換後：27 38 13 49 76 97 65 ( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 ) 此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所有大於49的數全部在49的後面，所有小於49的數全部在49的前面。 快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示： 初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。 {76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。

⑽ 快速排序

快速排序（Quicksort），計算機科學詞彙，適用領域Pascal，c++等語言，是對冒泡排序演算法的一種改進。

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

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

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

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

排序演示

假設一開始序列{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=3，j=7，從第3位往後找，第一個比5大的數是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此時，i=4，j=7，從第7位往前找，第一個比5小的數是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此時，i=4，j=6，從第4位往後找，直到第6位才有比5大的數，這時，i=j=6，ref成為一條分界線，它之前的數都比它小，之後的數都比它大，對於前後兩部分數，可以採用同樣的方法來排序。