C++学习记录算法篇—快速排序

C++学习记录算法篇—快速排序

一、快速排序的过程（从小到大排为例）：

首先，假设基准数为最左边的数。

然后，让两个“哨兵”从最左边和最右边向中间探测，从左边出发的哨兵找比基准数大的数，从右边出发的哨兵找比基准数小的数

注意，因为是从小到大排，所以右边的哨兵要先出发

两个哨兵都“停下”（即找到了符合要求的数），交换两个“哨兵”的值，接着继续探测，继续交换，直到两个哨兵相遇为止

两个哨兵相遇后，交换基准数与相遇时所指示的数。

此时，基准数左边都小于基准数，基准数右边都大于基准数，这也是为什么要右边哨兵先动的原因

至此，基准数归位，接着对基准数的两边再次进行快速排序，这是一个递归的过程。

可以看到，快速排序就是不断地把基准数归位的过程

下面是代码：

//快速排序函数
void quicksort(int l, int r)//接受最左边数字的下标left，和最右边数字的下标right
{
	int i, j, t, temp;
	if (l >= r) { return; }//此情况只有一个数，不用排

	temp = arr[l];//temp存储最左边的基准数
	i = l;
	j = r;

	while (i != j)//左右开始探测
	{
		//顺序很重要，从基准数的另一边开始找起
		while (arr[j] >= temp && j > i) { j--; }//如果所指数比基准数大且i，j不相遇，则不用交换，继续探测
		//再从基准数开始找起
		while (arr[i] <= temp && i < j) { i++; }

		//当i，j都停止且没相遇时，交换两数
		if (i < j)
		{
			t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}

	//当i=j时，上方探测停止，此时将基准数归位
	arr[l] = arr[i];
	arr[i] = temp;//temp在上面存储了基准数的值

	//至此，一轮探测真正结束，下面进行递归调用

	quicksort(l,i - 1);//基准数左边进行排序，这是一个递归的过程
	quicksort(i + 1, r);//基准数右边进行排序，这是一个递归的过程

	return;
}

快速排序的时间复杂度为O（nlog2n【以2为底，n的对数】），最坏情况为O（n^2）。

空间复杂度为O（log2n【以2为底，n的对数】）。

是不稳定的排序

快速排序还可以用sort（&arr[下标],&arr[下标]），默认是从小到大，从大到小要添加第三个参数greater<数据类型>()。要包含头文件。