快速排序（分治政策）

算法劃分圖示

如圖，以首元素27為基準，定義i和j，i向右周遊，j向左周遊。首先由j開始進行周遊，直到遇到小于27的元素時停下。此時i開始進行周遊，直到遇到大于27的元素時停下。此時交換i和j所指向的元素。然後j和i開始第二次的周遊… …直到最後i周遊遇到了j，令27與j所指向的元素16進行交換。至此第一次對數組的排序結束。

算法思想

1. 以首元素A[0]作為劃分的标準，将這組元素劃分成不超過A[0]的元素構成的數組AL,和大于A[0]的元素組成的數組AR。AL和AR分别位于A[0]的左右兩邊。
2. 遞歸的調用此算法，分别對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(n²）。

最好情況

最好情況發生在每次遞歸執行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)。