快速排序

Posted on | Post modified: | In
Words count in article: 365 | Reading time ≈ 1

-快速排序算法思想
-快速排序算法实现
-快速排序性能分析

算法介绍

快速排序是“交换”累的排序，通过多次划分操作实现排序。以升序为例，其执行流程可以概括下：每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前面，比枢轴打的移到枢轴后面；当本趟所有子序列都被枢轴以上述规则划分后会得到新的一组更短的子序列。

算法思想
选第一个为关键字，从右开始找小于他的交换，再从左找大于它的交换，完成一趟排序。依次类推，多趟排序后使序列有序。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void QuickSort(int R[],int low,int high){
//对从R[low]到R[r]的关键字排序
int temp;
int i=low,j=r;
if(low<high){
	temp=R[low];
	while(i!=j){
		while(j>i&&R[i]>=temp)
			--j;
		if(i<j){
			R[i]=R[j];
			++i;
		}
		while(i<j&&R[i]<temp)
			++i;
		
	if(i<j){
		R[j]=R[i];
		--j;
		}
	}
	R[i]=temp;
	QuickSort(R,low,i-1);
	QuickSort(R,i+1,high);
	}
}

时间复杂度
最好情况下，复杂度为O（nlog2n）
最坏情况下，复杂度为O（n2）
平均情况下，复杂度为O（nlog2n）

空间复杂度
快速排序是递归进行的，递归需要栈的辅助，算法的空间复杂度为O（log2n）

Thanks for your reward！