快速排序

发表于

思路

1、先从数列中取出一个数作为基数
2、根据该基数进行分区，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。（升序）
3、再对左右两个部分重复前面两个步骤，直至区间中元素个数为1.

图示（参考链接）

image

代码实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>

int Partition(int *a, int low, int high)
{
	/* 这里的基数我们取的第一个数 */
	int temp = a[low];  
	while (low < high)
	{
		while (low < high &&a[high] >= temp) --high;
		a[low] = a[high];
		while ( low < high && a[low] <= temp) ++low;
		a[high] = a[low];
	}
	a[low] = temp;
	return low;
}


void Q_sort(int * a, int low, int high)
{
	if (low < high)
	{
		/* 根据函数Partition，对数列进行分去，并且返回基数最后存放的位置 */
		int position = Partition(a, low, high);
		/* 递归 */
		Q_sort(a, low, position - 1);
		Q_sort(a, position + 1, high);
	}
}

int main()
{
	int a[] = { 84, 83, 88, 87, 61, 50, 70, 60, 80, 99 };
	Q_sort(a, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d,", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

算法分析

算法的平均时间复杂为：O（n * log N）;

最坏的情况：
对n个元素的区间进行划分时，得到的两个子区间含有的元素分别为：0个和n-1个。假设算法每一次递归调用过程中都出现了这种不对称划分。那么划分的代价为O（n），因此可以估计其时间复杂度为：O(n^2)。

其实快速排序的最坏的情况是对有序或基本有序的数列进行排序时出现的，此时其本质已经退化为冒泡排序了。另外，快速排序还有很多改进版，如随机选择基数，区间内数据较少时直接用另外的方法排序以减小递归深度等。