快速排序_排序算法

     快速排序算法是基于分治政策的一種排序算法。其基本思想是，對于輸入的子數組a[s:e],按照如下的三個步驟進行排序：

    （1）分解：以a[q]為基準元素将a[s:e]劃分成3段a[s:q-1],a[p]及a[q+1:e],使得a[s:q-1]中的任何一個元素都不大于a[q],使得a[q+1:e]中的任何一個元素都不小于a[q],下标q在劃分過程中确定；

    （2）遞歸求解：通過遞歸調用快速排序算法分别對a[s:q-1]和a[q+1:e]進行排序。

    （3）合并：由于對a[s:q-1]和a[q+1:e]的排序是就地進行的，是以a[s:q-1]和a[q+1:e]都已排序好，不需要執行任何計算，a[s:e]就以排序好。

//QuickSort.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
void outputArray(int *a,int len){	
	
	printf("數組為：");
	for (int i=0;i<len;i++)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
}

void swap(int &x,int &y){
	int tmp=x;
	x=y;
	y=tmp;
}
int partition(int *a,int s,int e){
	int i=s,j=e+1;
	int x=a[s];
	while (true)
	{
		while (a[++i]<x&&i<e);
		while (a[--j]>x);
		if(i>=j)
			break;
		swap(a[i],a[j]);
	}
	a[s]=a[j];
	a[j]=x;
	return j;
}
void quickSort(int *a,int s,int e){
	
	if(s<e){
		int q=partition(a,s,e);
		quickSort(a,s,q-1);
		quickSort(a,q+1,e);
	}

}
int _tmain(int argc, _TCHAR* argv[])
{
	int a[6]={3,6,2,5,3,1};
	outputArray(a,6);
	quickSort(a,0,5);
	outputArray(a,6);
	getchar();
	return 0;
}

           

    快速排序的最壞情況下的時間複雜度為:O(n^2),平均為O(nlogn);快速排序算法的性能取決劃分的對稱性。通過修改函數partition，可以設計随機選取政策的快速排序算法。在快速排序算法的每一步中，當數組還沒有被劃分時，可以在a[s:e]中随機選擇一個元素作為劃分基準，這樣的可以使得劃分基準的選擇是随機的，進而可以期望劃分是較對稱的。随機劃分的算法是實作如下：

//QuickSort.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include <time.h>
#include <stdlib.h>
void outputArray(int *a,int len){	

	printf("數組為：");
	for (int i=0;i<len;i++)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
}

void swap(int &x,int &y){
	int tmp=x;
	x=y;
	y=tmp;
}
/************************************************************************/
/* 劃分，左右每部分的排序就地進行                                                                     */
/************************************************************************/
int partition(int *a,int s,int e){
	int i=s,j=e+1;
	int x=a[s];
	while (true)
	{
		while (a[++i]<x&&i<e);
		while (a[--j]>x);
		if(i>=j)
			break;
		swap(a[i],a[j]);
	}
	a[s]=a[j];
	a[j]=x;
	return j;
}
/************************************************************************/
/* 産生随機劃分                                                                     */
/************************************************************************/
int randomPartition(int *a,int s,int e){
	srand((unsigned )time(NULL));
	int i=s+rand()%(e-s);
	swap(a[s],a[i]);
	return partition(a,s,e);
}
/************************************************************************/
/* 對左右不分遞歸進行排序                                                                     */
/************************************************************************/
void randomQuickSort(int *a,int s,int e){

	if(s<e){
		int q=randomPartition(a,s,e);
		randomQuickSort(a,s,q-1);
		randomQuickSort(a,q+1,e);
	}

}
int _tmain(int argc, _TCHAR* argv[])
{
	int a[6]={3,6,2,5,3,1};
	outputArray(a,6);
	randomQuickSort(a,0,5);
	outputArray(a,6);
	getchar();
	return 0;
}