快速排序（C）

快速排序算法是基于分治策略的一种算法，其基本思想是取一个基准值，分别从序列的两端扫描数据，将初始序列划分成两份，比基准大的分到右边，小于等于基准的分到左边；然后对左右两边的区间再次独立划分，采用递归的方式，重复划分排序，直到划分区间里只剩一个数。

算法描述

假设：对于集合 N【len】进行快速排序，起始位置 low = 0，末尾 high = len - 1
第一次排序：从N中取基准值 temp = N【起始位置】保存，然后从首尾两端扫描数据，值与temp作比较，大于基准移到temp右边，小于等于基准移到temp左边

左右分区排序：执行第二次排序时，数值 6 左右分区分别排序，重复第一次的排序过程，结果如下

递归实现：如上面两个步骤，可以使用递归来实现整个序列的排序，递归调用第一次排序的过程，取基准、划分，直到所有子分区首尾相遇，完成排序。

代码实现

void quick_Sort(int N[], int start, int end)
{
	int i = start;
	int j = end;
	int temp;
	if (i < j) {
		temp = N[i];  // 保存基准值
		/* 进行一次快排 */
		while (i != j) {
			while (i < j && N[j] >= temp) {
				j--;
			}
			N[i] = N[j];  // N[j]比temp小的放到temp前面
			while (i < j && N[i] <= temp) {
				i++;
			}
			N[j] = N[i]; / N[i]比temp大的放到temp后面
		}
		N[i] = temp;  // 当 i == j 时，基准归位到 i 位置，一轮快排结束
		/* 开始递归快排基准左右的序列 */
		quick_Sort(N, start, i);
		quick_Sort(N, i + 1, end); 
	}
	return;
}

执行结果

输入数据 N = {6，3， 5， 7， 2， 0，1， 9， 4， 8}，执行过程如下：
快速排序
如图所示，对于 10 个元素，一共比较划分了 9 次，完成排序；即：对于n个元素，快排需要比较划分 n - 1 次。

算法复杂度

时间复杂度

最好情况：每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为 n/2 的区域，
其 T（n）= O（nlogn）
最坏情况：每次划分的基准是当前区域中最大（或最小）的元素，每次划分为 n - 1 和 1 个元素区域，即第 i 次划分的长度为 n - i + 1，比较次数 n - i，其 T（n） = O（n^2）
平均情况：T（n） = O（nlog2n）

空间复杂度：O（log2n），主要是递归算法对于栈空间的消耗

基准取值