面试准备之九种排序算法之快速排序

快排的时间复杂度为nlog(n)

实现方式如下：

首先定义一个交换函数swap，一个取两个下标中间下标并返回的函数findpivot。一个主函数用于划分数组，进行实际快排的函数，一个执行数组排序操作的函数。他们之间的关系是主函数首先判断输入起始下标和终点下标之间关系，如果前者大于等于后者则直接返回。否则我们开始下面的过程，调函数findpivot找到起始下标和终点下标的中间下标，将这个下标所指值和末尾下标所指值进行交换。之后将这个数组和起始下标-1以及终点下标和终点下标值传入实际执行数组排序的函数partition,在这个函数中，我们执行一个判断条件为l<r的循环判断（l和r对应起始值为传入参数），如果l < r 并且++l处的值小于pivot(传入数组的末尾下标对应的值)，一直while，退出循环后如果l < r并且--r处的值大于pivot,一直while，这样是为了找到左边大于pivot和右边小于pivot的值并进行交换，保证左边都是小于pivot的值，右边都是大于pivot的值，直到l==r。此时这个l也是>= pivot的第一个值。我们将这个值返回作为partition函数的返回值。

之后我们再将数组末尾值和partition函数返回的下标处的值进行交换，将pivot放到一个左边都是小于它，右边都是大于它的位置了。再以这个下标为划分点，左右两边分别递归调用这个主函数，但一个右边下标是该下标值-1，一个左边下标是该下标值+1，另外两个是数组起始和末尾节点，一直持续下去，最后就能得到排序好的数组了。

代码如下：

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

inline int findpivot(int i, int j) {
	return (i + j) / 2;
}

void swap(vector<int>& nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}

int partition(vector<int>& nums, int l, int r, int pivot) {
	while (l < r) {
		while (l < r && nums[++l] <= pivot);
		while (l < r && nums[--r] >= pivot);
		if (l < r) swap(nums, l, r);
		cout << l << r << endl;	
	} 
	return l;
}

void qsort(vector<int>& nums, int start, int end) {
	if (start >= end) return;
	int pivotpartition = findpivot(start, end);
	swap(nums, pivotpartition, end);
	int k = partition(nums, start - 1, end, nums[end]);
	swap(nums, k, end);
	qsort(nums, start, k - 1);
	qsort(nums, k + 1, end);
}

int main() {
	vector<int> nums;
	srand(time(0));
	for (int i = 0; i < 10; i++) 
		nums.push_back(rand() % 65535);
	for (int i =0; i <nums.size(); i++)
		cout << nums[i] << ' ';
	cout << endl;
	qsort(nums, 0, nums.size() - 1); 
	for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << ' ';
}