一、什么是快速排序？
快速排序（英文名：Quicksort，有时候也叫做划分交换排序）是一个高效的排序算法，由Tony Hoare在1959年发明（1961年公布）。当情况良好时，它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这是一个分治算法，而且它就在原地排序。即不需要额外开辟空间，仅仅是在原数组上操作就可以完成排序。快速排序算法有三个不同的版本，今天就来学习一下快排的第一个版本：hoare版本。
二、快速排序hoare版本
hoare版本是快速排序最原始的版本，是hoare大佬最先提出的一种快排的方法。
其基本思想为：先选取数组左边的第一个数作为key，定义一个左下标left指向最左边的数，定义一个右下标right指向最右边的数，然后让right先往左遍历寻找一个比key小的数字，找到后停下来；再让left向右遍历寻找一个比key大的数字，找到后停下来(简单理解为左边找比key大的，右边找比key小的)，然后把找到的这两个数交换，然后right再向左找小，left向右找大，再交换，以此类推，直到left和right相遇，再把这个相遇的位置的数字和key交换就完成了一趟快速排序。经过了一趟快速排序之后，key的值就来到了key最终有序是该出现的位置，因为左边是比它小的，右边是比它大的，它的位置就是正确的。然后再把key的左边和右边作为一个局部的数组重复上面的步骤，直到每一个局部区间都是有序的，那么这个数组也就是有序的了。
切记：左边做key，必须要让右边先走，这样才能保证相遇位置的左边的数比key小，右边的数比key大，证明如下：
情况一、
情况二、
情况三、
left和right相遇的地方有以上三种情况，可以看到，（左边做key，让右边先走），无论是哪一种情况都能保证相遇的位置的数一定是小于等于key的，所以和key交换就一定能保证key的左边比key小(或者等于)，右边比key大。
但是如果左边做key，左边先走呢？我们也来看一看下图。
所以左边做key，让右边先走是必然的；相反，右边做key，让左边先走也是必然的。
上面的演示都是只进行了一趟快排，要想完成整个数组的排序还需要以key的位置为分界点，左边的子数组和右边的子数组也分别递归做同样的快速排序，直到区间内只剩下一个值(left==right)或者区间不存在(left>right)就停止，这样就能使每一个区间的子数组都是有序的，最终整个数组也就变成有序了。
但是这样每次都选左边做key的话，如果数组是有序的，假如是升序，那么在每一趟子数组的快排里，最左边的值就是最小的，那每一次从right开始向左找比key小的数都要找到最左边的和key相等的数，这样的话排序执行的次数就变成了n+ n-1 + n-2+…+3+2+1，那么时间复杂度就变成了O(N^2)了，这显然是不合理的，所以大佬又想出了两个优化的方法：
其一、随机选key。
生成一个属于数组内的随机下标，那么这个下标对应的数大概率不会是最大或者最小的数，因为这是随机生成的，然后用这个数和left下标(即最左边)的数进行交换，这样的话left对应的数就是一个趋近于这个数组中间的数了。那选这个数做key就能够更好地提高每一趟快速排序的效率了。
其二、 三数取中。
就是对比排序数组(可能是子数组)的最左边，中间，最右边的三个数，取不是最大也不是最小的一个的那一个数，使它和left位置的数交换之后做key，那么这个key就不可能出现极端(最大/最小)值的情况了，这比随机选key要更好那么一点，因为随机选key还是会取到最大值或者最小值做key的。
参考代码如下：
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } //三数取中 int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) { return mid; } //来到这里证明a[mid]最小，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } else//a[left]<=a[mid] { if (a[mid] < a[right]) { return mid; } //来到这里证明a[mid]最大，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } } //小区间优化需要用到直接插入排序 void InsertSort(int* a, int n) { assert(a); int i = 0; int end = 0; int tmp = 0; for (i = 0; i < n - 1; i++) { end = i; tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } } // 快速排序hoare版本 //给定一个数组和数组的左右下标进行快速排序 int PartSort1(int* a, int left, int right) { //随机选key //int randi= left + (rand() % (right - left)); //Swap(&a[left], &a[randi]); //三数取中 int mid = GetMidNumi(a, left, right); //如果left就是取到的数，那么也就没有必要交换了 if (mid != left) { Swap(&a[left], &a[mid]); } //三数取中只是调整最左边值的大小， //三数取中交换之后依然是选左边作为 //keyi，但是此时这个key就不会是 //数组中的最大值或者最小值了，为了 //优化有序数组的情况 int keyi = left; while (left < right) { //右边找小 while (left < right && a[right] >= a[keyi]) { --right; } //左边找大 while (left < right && a[left] <= a[keyi]) { ++left; } //用左边大的和右边小的进行交换，使小的数翻到前面 //大的数翻到后面 Swap(&a[left], &a[right]); } //最后把key和相遇的位置的数交换(这里写a[left]和a[right]都是一样的，因为相遇地方left==right) Swap(&a[keyi], &a[left]); keyi = left; return keyi; } void QuickSort(int* a, int left,int right) { assert(a); //区间只有一个值或者区间不存在就不用再递归下去了 if (left >= right) { return; } //这里进行一个小区间优化，当一个区间<=10个元素的时候 //快排已经不再适合，因为快排是数据越多并且越乱的时候 //才是越快的，但是数据量小的时候，快排是没有很大的优势 // 的如果这个是一个大数组经过多次递归下来的小区间，证明 // 这个区间接近于有序的，此时换成直接插入排序会更加的高效 if (right - left + 1 < 10) { InsertSort(a + left, right + 1 - left); } else { //每一趟快排之后都返回keyi的位置，把区间分成 //[left,keyi-1][keyi][keyi+1,right]三个部分 //再对子区间的数组进行快排，直到不满足递归条件再返回 int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }
三、快速排序的时间复杂度是多少？
快速排序的时间复杂度为O(N*logN)。
证明如下：
最后来上一张完整演示的动图：
