算法导论 - QuickSort 快速排序 C++实现

算法导论的快速排序还和一般书上的快速排序是有点不一样的。

当然书习题也给出了一般快速排序的方法，其分区函数学名叫Hoare partition。

书本介绍的排序可以用图看的很清晰：

然后配合C++程序，就不需要废话就能明白了：

//C++'s array range should be [low, up], the same as [low, up+1)
int partition(vector<int> &vi, int low, int up)
{
	int pivot = vi[up];
	int i = low-1;
	for (int j = low; j < up; j++)
	{
		if(vi[j] <= pivot)
		{
			i++;
			swap(vi[i], vi[j]);
		}
	}
	swap(vi[i+1], vi[up]);
	return i+1;
}

他的quick sort程序也很明了，值得注意到的地方就是，mid是已经到了最终排序位置的了，所以，不需要递归考虑这个位置了。

//C++'s array range should be [low, up], the same as [low, up+1)
void quickSort(vector<int> &vi, int low, int up)
{
	if(low < up)
	{
		int mid = partition(vi, low, up);
		//Watch out! The mid position is on the place, so we don't need to consider it again.
		//That's why below is mid-1, not mid! Otherwise it will occur overflow error!!!
		quickSort(vi, low, mid-1);
		quickSort(vi, mid+1, up);
	}
}

增加一个adaptor功能函数：

void qSort(vector<int> &vi)
{
	quickSort(vi, 0, vi.size()-1);
}

最后是测试主函数：

int main()
{
	int a[] = {3,5,7,9,2,3,1,0,7,5,4};
	vector<int> va(a, a+11);

	cout<<"Before quicksort:\n";
	for(auto x:va)
		cout<<x<<" ";
	cout<<endl;

	qSort(va);

	cout<<"After quicksort:\n";
	for(auto x:va)
		cout<<x<<" ";
	cout<<endl;
	system("pause");
	return 0;
}

结果：