快速排序演算法代碼

❶ 快速排序c++代碼

隨機生成N個整數顯示，經過快速排序後輸出排序後的結果。
程序代碼如下所示，僅供參考：（已通過編譯運行，正確無誤！）
# include "stdio.h"
# include "time.h"
# include "stdlib.h"
# define N 10
int partition(int a[],int low,int high){//快速排序中的一趟
int pivotkey;//作為樞軸來使用
pivotkey=a[low];
while(low<high){
while(low<high&&a[high]>=pivotkey)
--high;
a[low]=a[high];
while(low<high&&a[low]<=pivotkey)
++low;
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
void qsort(int a[],int low,int high){//快速排序的遞歸形式
int pivotloc;
if(low<high){
pivotloc=partition(a,low,high);//一趟排序結果的調用
qsort(a,low,pivotloc-1);
qsort(a,pivotloc+1,high);
}
}
void init(int a[]){//隨機生成N個整數並
int i;
srand ( ( unsigned int ) time ( NULL ) );
for(i=0;i<N;i++)
a[i]=rand()%99+1;
}

void main(){
int a[N],i;
init(a);
printf("排序前的數值內容\n");
for(i=1;i<=N;i++){//輸出排序前的數組內容
printf("%d ",a[i-1]);
if(i%10==0)
printf("\n\n");
}
qsort(a,0,N);
printf("排序後的結果\n");
for(i=1;i<=N;i++){//輸出排序後的數組內容
printf("%d ",a[i-1]);
if(i%10==0)
printf("\n\n");
}

printf("\n\n");
}
程序中已經做了必要的注釋，相信你可以很容易理解的，呵呵
祝你的問題早日解決！

❷ 誰能給份快速排序的代碼

public class QuickSort
{
public static void main(String[] args)
{
int []array={3,1,2};
quickSort(array,0,2);
for(int i:array)
System.out.println(i);
}
public static void quickSort(int[] arr, int l, int r) // 分劃交換排序,快速排序
{
if (l >= r) // 遞歸出口
return;
int i, j, k;
int t;
k = arr[l];
i = l;
j = r + 1;
while (i < j) // 找出k(最左邊的關鍵詞)的最終位置,此過程中,比k小的放(k最終位置)左邊,比k大的放(k最終位置)右邊
{
do
{
i++;
}
while (i<r && arr[i] < k);
do
{
j--;
}
while (j>=0 && arr[j] > k);
if (i < j)
{
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
t = arr[l]; // 最左邊的關鍵詞放到它最終的位置
arr[l] = arr[j];
arr[j] = t;
quickSort(arr, l, j - 1); // 遞歸排序左邊和右邊
quickSort(arr, j + 1, r);
}
}

❸ vb代碼求快速排序的遞歸演算法代碼

PublicSubQuickSort(ByRefaStrSort()AsString,ByVallngleftAsLong,ByVallngrightAsLong)
DimiAsLong
DimjAsLong
DimtempAsString
i=lngleft
j=lngright
temp=aStrSort(i)
NextStep:DoUntili>=j
While(aStrSort(j)>tempAndj>i)
j=j-1
EndWhile
Ifj>iThen
aStrSort(i)=aStrSort(j)
aStrSort(j)=temp
i=i+1
EndIf
While(aStrSort(i)<tempAndj>i)
i=i+1
EndWhile
Ifj>iThen
aStrSort(j)=aStrSort(i)
aStrSort(i)=temp
j=j-1
EndIf
Loop
Iflngleft<i-1ThenQuickSort(aStrSort,lngleft,i-1)
Iflngright>i+1ThenQuickSort(aStrSort,i+1,lngright)
EndSub

將數組的第10到20個元素用快速演算法遞歸排序
QuickSort(a,10,20)

❹ 用C語言編寫一個快速排序演算法 輸入10個數

1、「快速排序法」使用的是遞歸原理，下面一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是速度太慢。
2、快速排序代碼：

#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];

}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的結果*/
for(i=0;i<10;i++)
printf("%4d
",a[i]);
}

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

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

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

假設要排序的數組是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。

(5)快速排序演算法代碼擴展閱讀：

設要排序的數組是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語言，快速排序演算法

0和N-1表示的是數組下標。快排每一趟排序的目的是使值比設定的key值小的數都排到數組前部分，大的都排到後部分；然後對這兩部分用新的關鍵值key分別重復上一步的操作；遞歸，直到數組有序。
其中關鍵值key=a[low]。
用題目給定的數組模擬第一趟排序如下：
下標0123456789
值91647824661232551
low=0high=9
part_element=a[low]=9
進入for循環
進入第一個while
part_element<51，於是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不滿足，結束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
進入第二個while
part_element<16,不滿足，結束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一個循環結束，數組如下
316478246612162551
low=1,high=6
for第二個循環同上，結束時數組如下
344782476612162551
low=2,high=3
for第三個循環，第一個while中high--以後，low==high，直接break跳出for循環，此時
344782476612162551
low=2,high=2
結束for以後
a[high]=a[2]=part_element=9,得到
34982476612162551
split函數returnhigh=2

quicksort函數中middle=2;
下面兩句遞歸，仍然是調用split函數，對數組
0-2,3-9兩部分分別重復上述操作

最後直到數組數據有序

❼ 急！！！C++快速排序法的編碼

[編輯本段]C++中的快速排序源代碼
#include<iostream> using namespace std; void QuickSort(int *pData,int left,int right) { int i(left),j(right),middle(0),iTemp(0); middle=pData[(left+right)/2];//求中間值 middle=pData[(rand()%(right-left+1))+left]; //生成大於等於left小於等於right的隨機數 do{ while((pData[i]<middle)&&(i<right))//從左掃描大於中值的數 i++; while((pData[j]>middle) && (j>left))//從右掃描小於中值的數 j--; //找到了一對值,交換 if(i<=j){ iTemp=pData[j]; pData[j]=pData[i]; pData[i]=iTemp; i++; j--; } }while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次） //當左邊部分有值(left<j)，遞歸左半邊 if(left<j){ QuickSort(pData,left,j); } //當右邊部分有值(right>i)，遞歸右半邊 if(right>i){ QuickSort(pData,i,right); } } int main() { int data[]={10,9,8,7,6,5,4}; const int count(6); QuickSort(data,0,count); for(int i(0);i!=7;++i){ cout<<data[i]<<「 」<<flush; } cout<<endl; return 0; }
[編輯本段]VB中的快速排序源代碼
'快速排序演算法，對字元串數組進行排序 Private Sub quicksort(ByRef arrValue() As String, ByVal intLx As Integer, ByVal intRx As Integer) 'arrValue()是待排的數組，intLx,intRx為左右邊界 Dim strValue As String Dim I As Integer Dim j As Integer Dim intLoop As Integer I = intLx j = intRx Do While arrValue(I) <= arrValue(j) And I < j: I = I + 1: Wend If I < j Then strValue = arrValue(I) arrValue(I) = arrValue(j) arrValue(j) = strValue End If While arrValue(I) <= arrValue(j) And I < j: j = j - 1: Wend If I < j Then strValue = arrValue(I) arrValue(I) = arrValue(j) arrValue(j) = strValue End If Loop Until I = j I = I - 1: j = j + 1 If I > intLx Then Call quicksort(arrValue, intLx, I) End If If j < intRx Then Call quicksort(arrValue, j, intRx) End If End Sub Private Sub Form_Load() Dim arr(8) As String arr(0) = 「r&」 arr(1) = 「e」 arr(2) = 「a」 arr(3) = 「n」 arr(4) = 「b」 arr(5) = 「u」 arr(6) = 「c」 arr(7) = 「o」 arr(8) = 「f」 Call quicksort(arr, 0, UBound(arr)) End Sub

❽ 求C++快速排序、插入排序代碼。要超級詳細，每步每個函數都要注析

sort()//快速排序

STL庫algorithm庫

快速排序（升序）：

類似二分，找到任意點（一般是序列中點）

然後把小於中點的放到左邊，大於的放到右邊

之後，在以同樣方法排左右區間（遞歸）

代碼：

#include<iostream>
#include<cstring>
usingnamespacestd;
inta[501];
voidq_sort(ints,inte)
{
	intm=a[(s+e)/2],l=s,r=e;
	do
	{
		while(a[l]<m)l++;
		while(a[r]>m)r--;
		if(l<=r)
		{
			swap(a[l],a[r]);
			l++;
			r--;
		}
	}while(l<=r);
	if(l<e)
		q_sort(l,e);
	if(r>l)
		q_sort(l,r);
}
intmain()
{
	intn;
	cin>>n;
	for(inti=1;i<=n;i++)
		cin>>a[i];
	q_sort(1,n);
	for(inti=1;i<=n;i++)
		cout<<a[i]<<"";
	return0;
}

❾ 快速排序演算法的示例代碼

usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacetest{classQuickSort{staticvoidMain(string[]args){int[]array={49,38,65,97,76,13,27};sort(array,0,array.Length-1);Console.ReadLine();}/**一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。**@paramarray排序數組**@paramlow排序起始位置**@paramhigh排序結束位置**@return單元排序後的數組*/privatestaticintsortUnit(int[]array,intlow,inthigh){intkey=array[low];while(low<high){/*從後向前搜索比key小的值*/while(array[high]>=key&&high>low)--high;/*比key小的放左邊*/array[low]=array[high];/*從前向後搜索比key大的值，比key大的放右邊*/while(array[low]<=key&&high>low)++low;/*比key大的放右邊*/array[high]=array[low];}/*左邊都比key小，右邊都比key大。//將key放在游標當前位置。//此時low等於high*/array[low]=key;foreach(intiinarray){Console.Write({0} ,i);}Console.WriteLine();returnhigh;}/**快速排序*@paramarry*@return*/publicstaticvoidsort(int[]array,intlow,inthigh){if(low>=high)return;/*完成一次單元排序*/intindex=sortUnit(array,low,high);/*對左邊單元進行排序*/sort(array,low,index-1);/*對右邊單元進行排序*/sort(array,index+1,high);}}}運行結果：27 38 13 49 76 97 65
13 27 38 49 76 97 6513 27 38 49 65 76 97
快速排序就是遞歸調用此過程——在以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} 完成排序。圖示 快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精闢的總結：「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。 QUICKSORT(A，p，r)
1if p<r
2then q ←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
為排序一個完整的數組A，最初的調用是QUICKSORT(A，1，length[A]）。
快速排序演算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3for j←p to r-1
4do if A[j]≤x
5then i←i+1
6exchange A[i]←→A[j]
7exchange A[i+1]←→A[r]
8return i+1 對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：
（其中PARTITION過程同快速排序偽代碼（非隨機））
RANDOMIZED-PARTITION(A，p，r)
1i← RANDOM(p，r)
2exchange A[r]←→A[i]
3return PARTITION(A，p，r)
新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1if p<r
2then q← RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r) 這里為方便起見，我們假設演算法Quick_Sort的范圍閾值為1（即一直將線性表分解到只剩一個元素），這對該演算法復雜性的分析沒有本質的影響。
我們先分析函數partition的性能，該函數對於確定的輸入復雜性是確定的。觀察該函數，我們發現，對於有n個元素的確定輸入L[p..r]，該函數運行時間顯然為θ（n）。
最壞情況
無論適用哪一種方法來選擇pivot，由於我們不知道各個元素間的相對大小關系（若知道就已經排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。
我們從直覺上可以判斷出最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候（設輸入的表有n個元素）。下面我們暫時認為該猜測正確，在後文我們再詳細證明該猜測。
對於有n個元素的表L[p..r]，由於函數Partition的計算時間為θ（n），所以快速排序在序壞情況下的復雜性有遞歸式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)
用迭代法可以解出上式的解為T(n)=θ（n2）。
這個最壞情況運行時間與插入排序是一樣的。
下面我們來證明這種每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的情況就是最壞情況。
設T(n）是過程Quick_Sort作用於規模為n的輸入上的最壞情況的時間，則
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)
我們假設對於任何k<n，總有T(k）≤ck，其中c為常數；顯然當k=1時是成立的。
將歸納假設代入（2），得到：
T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)
因為在[1,n-1]上q2+(n-q)2關於q遞減，所以當q=1時q2+(n-q)2有最大值n2-2(n-1）。於是有：
T(n）≤cn2-2c(n-1)+θ（n）≤cn2
只要c足夠大，上面的第二個小於等於號就可以成立。於是對於所有的n都有T(n）≤cn。
這樣，排序演算法的最壞情況運行時間為θ（n2），且最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候。
時間復雜度為o（n2）。
最好情況
如果每次劃分過程產生的區間大小都為n/2，則快速排序法運行就快得多了。這時有：
T(n)=2T(n/2)+θ（n),T(1)=θ（1) (3)
解得：T(n)=θ（nlogn)
快速排序法最佳情況下執行過程的遞歸樹如下圖所示，圖中lgn表示以10為底的對數，而本文中用logn表示以2為底的對數.
由於快速排序法也是基於比較的排序法，其運行時間為Ω（nlogn)，所以如果每次劃分過程產生的區間大小都為n/2，則運行時間θ（nlogn）就是最好情況運行時間。
但是，是否一定要每次平均劃分才能達到最好情況呢？要理解這一點就必須理解對稱性是如何在描述運行時間的遞歸式中反映的。我們假設每次劃分過程都產生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：
T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1) (4)
請注意樹的每一層都有代價n，直到在深度log10n=θ（logn）處達到邊界條件，以後各層代價至多為n。遞歸於深度log10/9n=θ（logn）處結束。這樣，快速排序的總時間代價為T(n)=θ（nlogn），從漸進意義上看就和劃分是在中間進行的一樣。事實上，即使是99:1的劃分時間代價也為θ（nlogn）。其原因在於，任何一種按常數比例進行劃分所產生的遞歸樹的深度都為θ（nlogn），其中每一層的代價為O(n），因而不管常數比例是什麼，總的運行時間都為θ（nlogn），只不過其中隱含的常數因子有所不同。（關於演算法復雜性的漸進階，請參閱演算法的復雜性)
平均情況
快速排序的平均運行時間為θ(nlogn)。
我們對平均情況下的性能作直覺上的分析。
要想對快速排序的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設。通常都假設輸入數據的所有排列都是等可能的。後文中我們要討論這個假設。
當我們對一個隨機的輸入數組應用快速排序時，要想在每一層上都有同樣的劃分是不太可能的。我們所能期望的是某些劃分較對稱，另一些則很不對稱。事實上，我們可以證明，如果選擇L[p..r]的第一個元素作為支點元素，Partition所產生的劃分80%以上都比9:1更對稱，而另20%則比9:1差，這里證明從略。
平均情況下，Partition產生的劃分中既有「好的」，又有「差的」。這時，與Partition執行過程對應的遞歸樹中，好、差劃分是隨機地分布在樹的各層上的。為與我們的直覺相一致，假設好、差劃分交替出現在樹的各層上，且好的劃分是最佳情況劃分，而差的劃分是最壞情況下的劃分。在根節點處，劃分的代價為n，劃分出來的兩個子表的大小為n-1和1，即最壞情況。在根的下一層，大小為n-1的子表按最佳情況劃分成大小各為（n-1)/2的兩個子表。這兒我們假設含1個元素的子表的邊界條件代價為1。
在一個差的劃分後接一個好的劃分後，產生出三個子表，大小各為1，（n-1)/2和（n-1)/2，代價共為2n-1=θ（n）。一層劃分就產生出大小為（n-1)/2+1和（n-1)/2的兩個子表，代價為n=θ（n）。這種劃分差不多是完全對稱的，比9:1的劃分要好。從直覺上看，差的劃分的代價θ（n）可被吸收到好的劃分的代價θ（n）中去，結果是一個好的劃分。這樣，當好、差劃分交替分布劃分都是好的一樣：仍是θ（nlogn），但θ記號中隱含的常數因子要略大一些。關於平均情況的嚴格分析將在後文給出。
在前文從直覺上探討快速排序的平均性態過程中，我們已假定輸入數據的所有排列都是等可能的。如果輸入的分布滿足這個假設時，快速排序是對足夠大的輸入的理想選擇。但在實際應用中，這個假設就不會總是成立。
解決的方法是，利用隨機化策略，能夠克服分布的等可能性假設所帶來的問題。
一種隨機化策略是：與對輸入的分布作「假設」不同的是對輸入的分布作「規定」。具體地說，在排序輸入的線性表前，對其元素加以隨機排列，以強制的方法使每種排列滿足等可能性。事實上，我們可以找到一個能在O(n）時間內對含n個元素的數組加以隨機排列的演算法。這種修改不改變演算法的最壞情況運行時間，但它卻使得運行時間能夠獨立於輸入數據已排序的情況。
另一種隨機化策略是：利用前文介紹的選擇支點元素pivot的第四種方法，即隨機地在L[p..r]中選擇一個元素作為支點元素pivot。實際應用中通常採用這種方法。
快速排序的隨機化版本有一個和其他隨機化演算法一樣的有趣性質：沒有一個特別的輸入會導致最壞情況性態。這種演算法的最壞情況性態是由隨機數產生器決定的。你即使有意給出一個壞的輸入也沒用，因為隨機化排列會使得輸入數據的次序對演算法不產生影響。只有在隨機數產生器給出了一個很不巧的排列時，隨機化演算法的最壞情況性態才會出現。事實上可以證明幾乎所有的排列都可使快速排序接近平均情況性態，只有非常少的幾個排列才會導致演算法的近最壞情況性態。
一般來說，當一個演算法可按多條路子做下去，但又很難決定哪一條保證是好的選擇時，隨機化策略是很有用的。如果大部分選擇都是好的，則隨機地選一個就行了。通常，一個演算法在其執行過程中要做很多選擇。如果一個好的選擇的獲益大於壞的選擇的代價，那麼隨機地做一個選擇就能得到一個很有效的演算法。我們在前文已經了解到，對快速排序來說，一組好壞相雜的劃分仍能產生很好的運行時間 。因此我們可以認為該演算法的隨機化版本也能具有較好的性態。

❿ 求快速排序演算法的代碼

BOOL QuickSort(U16*p,int num)
{
int i;
int n_small=1,n_big=num-1;//升序
U16 m_key=p[0];
BOOL xiaokong=true;//小頭有空
int m_free = 0;

if(num<=1)return true;///遞歸終止條件
for(i=0;i<num-1;i++)
{
if(xiaokong)//小頭有空
{
if(p[n_big]<m_key)
{
p[m_free]=p[n_big];
m_free=n_big;
xiaokong=false;
}
n_big--;
}
else//大頭有空
{
if(p[n_small]>m_key)
{
p[m_free]=p[n_small];
m_free=n_small;
xiaokong=true;
}
n_small++;
}
}
if(m_free != 0)
{
p[m_free]=m_key;
}
//printf("num=%d[", num);
//for( i = 0; i< num; i++) printf("%d,", p[i]);
//printf("]key=%d, mid = %d, small=%d, big=%d, from %d num %d && from %d num %d\n",
// m_key, m_free, n_small, n_big, 0,m_free, m_free+1, num-(m_free+1) );
if(QuickSort(&p[0],m_free) && QuickSort(&p[m_free+1],num-(m_free+1) ) )
{
return true;
}
return false;
}

void QuickSortTest(void)
{
int i;
U16 sortTest[20] = {23,4,6,9,5,7,4,12,12,23,4,9999,89,1000,1000,4,2334,989,12,20};
U16 sortTest2[10] = {10,9,8,7,6,5,4,3,2,1};
U16 sortTest3[10] = {0,1,2,3,4,5,6,7,8,9};
for( i = 0; i<20; i++) printf("%d，",sortTest[i]); printf("\n");
QuickSort( sortTest, 20);
for( i = 0; i<20; i++) printf("%d，",sortTest[i]); printf("\n");

for( i = 0; i<10; i++) printf("%d，",sortTest2[i]); printf("\n");
QuickSort( sortTest2, 10);
for( i = 0; i<10; i++) printf("%d，",sortTest2[i]); printf("\n");

for( i = 0; i<10; i++) printf("%d，",sortTest3[i]); printf("\n");
QuickSort( sortTest3, 10);
for( i = 0; i<10; i++) printf("%d，",sortTest3[i]); printf("\n");
}