目录

一、快速排序的原理

二、快速排序的过程

三、代码的实现

四、代码的优化

总结

---

一、快速排序的原理

快速排序的思想是分治法，将一个大问题分割成几个小问题解决，首先选择一个数作为分水岭，然后让比该数大的都在它的右边，比它小的都在它左边，将一个大问题分割成了两个问题，用同样的方法对两边分别操作，最后呈现出来的就是排好序的整体。（以升序为例）

二、快速排序的过程（以升序为例）

我定义一个数组a[6]来演示，让low指向低下标，high指向高下标

一般让第一个数作为分水岭split=a[0]，然后将split和a[5]进行比较，a[5]>split，不用操作，接着high减一，

然后比较split和a[4]，split<a[4]，任然不用操作，high再减一，

然后将split和a[3]进行比较，split>a[3],将a[3]放到a[0]的位置，然后high减一，由于此时的low任然是0，但是a[0]是刚刚赋的值，已经比较过了，下一次无需再比较，所以移动之后low加一，

然后比较split和a[1]，split<a[1]，将a[1]的值放到a[3]中去，并且low加一，由于a[3]是刚刚赋的值，已经比较过了，下次无需再比较，所以还要high减一，

然后比较split和a[2]，split>a[2]，将a[2]放到a[1]中，并且low加一，high减一， 

当low不小于high的时候，将split放回数组中，放到a[low]的位置，（数组中元素的个数为奇数时，low=high结束，为偶数时，low大于high结束，总之只有low<high才进行比较）

此时第一次分割已经完成，split左边的值都比它小，右边的值都比它大，但是很明显，整个数组并没有排序好，但是后面只需对左边和右边进行相同的操作即可，问题的本质没有改变，经过多次分割整个数组就被排好序了。 （使用递归实现）

左右分别操作的时候，左边的high变成了split的下标减一，右边的low变成了split的下标加一，把左右当成新数组处理即可。

注意：如果split的初始值是a[0]，就要从high开始比较，如果是最后一位数，就要从low开始比较，并且比较一定是左右交替的！！！

三、代码的实现

//分割操作
int findsplit(int ints[], int low, int high)
{
	int split = ints[low];
	while (low < high)
	{
		while (low < high)
		{
			if (ints[high] < split)
			{
				ints[low] = ints[high];
				low++;//由于会产生一次多余的比较，所以low++规避，减少比较次数
				break;
			}
			high--;
		}
		while (low < high)
		{
			if (ints[low] > split)
			{
				ints[high] = ints[low];
				high--;//同上
				break;
			}
			low++;
		}
	}
	ints[low] = split;
	return low;
}

//递归排序
void rapidselect(int ints[], int low, int high)
{
    //递归函数退出的条件
	if (low >= high)
	{
		return;
	}
	int splitindex;
	splitindex = findsplit(ints, low, high);
	//split左侧排序
	rapidselect(ints, low, splitindex - 1);
	//split右侧排序
	rapidselect(ints, splitindex + 1, high);
}

四、代码的优化

上面的代码存在一点缺陷，如果a[0]是数组中的极值，那么整个过程并没有达到我们想要的效果，因为所有的数据任然在一边，运行速度受到影响。那么可以写一个函数求一下数组的大致中位数，尽量将数组平均分成两部分。代码如下：

int getmid(int a[], int low, int high)
{
	int mid = (low + high) / 2;
	//比较三者的关系
	if (a[low] < a[mid])
	{
		if (a[high] > a[mid])
			return mid;
		else if (a[low] < a[high])
			return high;
		else
			return low;
	}
	else
	{
		if (a[mid] > a[high])
			return mid;
		else if (a[high] > a[low])
			return low;
		else
			return high;
	}
}

将split初始化为这个大致的中位数即可做到尽量将数组均分。 

总结

根据计算，快速排序的排序次数log2（n），n为数组的元素个数，比如一个拥有16个元素的数组，使用冒泡排序需要排序15次（n-1次），而快速排序只需要四次（以2为底，16的对数），速度大大提高，弥补了冒泡排序循环次数多的缺点。

本节就到这里了，不懂的可以私信我，代码有不对的地方，也欢迎大家为我斧正。祝大家天天进步！