演算法劃分圖示
如圖，以首元素27為基準，定義i和j，i向右遍歷，j向左遍歷，首先由j開始進行遍歷，直到遇到小于27的元素時停下，此時i開始進行遍歷，直到遇到大于27的元素時停下，此時交換i和j所指向的元素，然后j和i開始第二次的遍歷… …直到最后i遍歷遇到了j，令27與j所指向的元素16進行交換，至此第一次對陣列的排序結束，
演算法思想
- 以首元素A[0]作為劃分的標準，將這組元素劃分成不超過A[0]的元素構成的陣列AL,和大于A[0]的元素組成的陣列AR，AL和AR分別位于A[0]的左右兩邊，
- 遞回的呼叫此演算法，分別對AL和AR繼續進行排序，
代碼實作
#include<iostream>
#include<algorithm>
using namespace std;
void QuickSort(int *arr,int p,int r) //p:陣列首元素 r:陣列尾元素
{
if(p<r)
{
int i=p,j=r+1;
int x=arr[p]; //首元素賦值給x
while(true)
{
while(arr[++i]<x&&i<r); //從第二個元素開始遍歷，判斷是否小于x
while(arr[--j]>x); //從最后一個元素開始遍歷，判斷是否大于x
if(i>=j) //跳出while回圈
break;
swap(arr[i],arr[j]); //當i尋到大于x的元素，j尋到小于x的元素時，進行交換
}
arr[p]=arr[j];
arr[j]=x;
QuickSort(arr,p,i-1); //遞回的對小于x的元素繼續進行排序
QuickSort(arr,j+1,r); //遞回的對大于x的元素繼續進行排序
}
}
int main()
{
/*int n;
cin>>n;
int num[n];
for(int i=0;i<n;i++)
{
cin>>num[i];
}*/
int num[12]={19,35,23,87,45,23,56,78,10,45,26,64};
int n=12;
QuickSort(num,0,n-1); //以陣列的第一個元素作為基準元素
cout<<"排序后的陣列為："<<endl;
for(int i=0;i<n;i++)
cout<<num[i] << ' ';
cout<<endl;
return 0;
}
時間復雜度
最壞情況
最壞情況發生在劃分之后所產生的左右兩個區域的元素數量分別為n-1和1個的時候，因為QuickSort函式執行一次的時間復雜度為O(n)，所以假設每次遞回的執行QuickSort函式時都會出現這種極端情況，則其時間復雜度滿足：
W(n)=W(n-1)+n-1
W(1)=0
解的
W(n)=n(n-1)/2
其時間復雜度為O(n2），
最好情況
最好情況發生在每次遞回執行QuickSort函式后，其劃分所產生的左右兩個區域的元素數量均等，兩邊元素數量都為n/2，此時其時間復雜度滿足：
W(n)=2W(n/2)+n-1
W(1)=0
解的
W(n)=θ(n log n)
其時間復雜度為O(n log n)，平均情況下的時間復雜度也為O(n log n)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/204890.html
標籤：其他