快速排序分析与实现

快速排序

快速排序的基本思想是在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分，然后对子序列分别重复上述过程，直到每个子序列内只有一个元素或为空为止。

代码实现

using namespace std;
//输出a中所有元素
void display(int a[],int n){
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
}
//划分
int Partition(int a[], int s, int t){
	int i = s, j = t;             
	int tem = a[s];					//用序列的第1个记录作为基准
	while (i != j){					//从序列两端交替向中间扫描，直到 i=j 为止
		while (j>i&&a[j] >= tem){
			j--;					//从右向左扫描，找到第一个关键字小于tem的a[j]
		}							
		a[i] = a[j];				//将a[j]前移到a[i]的位置
		while (i < j&&a[i] <= tem){
			i++;					//从左向右扫描，找到第一个关键字大于tem的a[i]
		}
		a[j] = a[i];				//将a[i]后移到a[j]的位置
	}
	a[i] = tem;						//将基准插到中间
	return i;
}
void QuickSort(int a[], int s, int t){ //对 a[s···t]元素序列进行递增排序
	if (s < t){
		int i = Partition(a, s, t);	  //基准的位置
		QuickSort(a, s, i - 1);	      //对基准左边的序列递归排序
		QuickSort(a, i+1, t);		  //对基准右边的序列递归排序
	}
}
int main(){
	int n = 10;
	int a[] = { 2, 5, 1, 7, 10, 6, 9, 4, 3, 8 };
	cout << "排序前：";
	display(a,n);
	cout << endl;
	cout << "排序后：";
	QuickSort(a, 0, n - 1);
	display(a, n);
}