算法修炼之道：快速排序的C++实现算法导论版

MIT的课程，今天实现了个快速排序，开始的时候理解错了，晕死

这个代码写起来挺快的，而且速度也是排序里面算是很快很快的了，所以叫做快速排序么：

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

 

#include <iostream>
using namespace std;
int a[10] = {32, 21, 67, 11, 5, 43, 99, 18, 22, 87};

void quickSort(int p, int q)
{
	if(p < q)
	{
		int x = a[p];
		int i = p;
		for(int j = p+1; j < q; j++)
		{
			if(a[j] < x)
			{
				i++;
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		int temp = a[p];
		a[p] = a[i];
		a[i] = temp;
		quickSort(p, i);
		quickSort(i+1, q);
	}
}

int main()
{
	quickSort(0, 10);
	for(int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

 个人感觉网上的代码没有我写的那么容易理解吧，嘿嘿，得到大师真传，自信一下~~

评论

2 楼 bbsunchen 2010-07-13  

回归蔚蓝 写道

!-_- 快吗?

时间复杂度，平均情况O(nlgn)，最好情况O(nlgn)，最坏情况O(n^2)，最坏情况出现在序列已经排好或者序列完全逆序的时候，这种情况可以通过随机选取切割位点来避免，不快么？
同时，其空间复杂度O(n)，不占用多余内存
另外，这应该是平均时间复杂度为O(nlgn)的算法中，代码量最少的算法了吧？

1 楼 回归蔚蓝 2010-07-13  

!-_- 快吗?