数据结构和算法学习之路—快速排序(C++版)

The best preparation for tomorrow is doing your best today. 对明天做好的准备就是今天做到最好！

快速排序——这个名字听起来就很高大上对不对，没错，在接下来的内容里，我将和大家一起探讨这项技术的原理，代码实现，以及效率方面的分析

1.快速排序的原理

快速排序的核心思想是分治，我们先举一个例子 对于下面这个数组:

int a[10] = {6,7,2,1,8,9,4,3,5,10};

如何高效率地将它们按从小到大(当然，也可以反过来) 排序？ 我们可以这样做：选定一个分界点，该点以左全是比这个值小的子数列，该点以右全是比这个值大的子数列，那么这样一来，我们需要排序的部分被划分成了以这个分界点为分界的左右两个子数列 我们应该可以理解，对一个比较短的数列排序所需要的时间一般来说（不排除特殊情况）比排列一个较长的数列所需要的时间少，所以，对于左右两个子数列，我们又可以继续按照刚刚讲的方法，再把这个子数列划分成更小的子数列，直到排序完成 以上就是快速排序的基本思想，我们可以看看下面的例子更好的理解：

我们就以上面那个数组为例进行快速排序 首先，为了简单，我们可以选择第一个数做为分界点，那么现在的首要任务就是找到这个分界点应该在哪个位置

为此，我们可以设置两个方向的"扫描器"i 和 j ,分别以 自左向右 和 自右向左 的方向扫描 那么扫描来干嘛呢？？？因为我们刚刚说到，分界点以左全是比这个值小的子数列，分界点以右全是比这个值大的子数列，所以 j 扫描器负责从右向左搜索比分界点值小的数，扫描器 i 负责从左向右搜索比分界点值大的数 好的，现在我们开始演示一遍：(我们设分界点的"代号"为temp） 我写了第一次分组的流程图，之后也就是递归操作了，思路和下面这个图一样 我们可以看到，当i 和 j 分别发现了目标时就停下来，开始把双方的值交换，有一点需要注意的，那就是，我们得让j先动，然后才是 i ,当i和j重合时，i的位置就是temp,也就是分界点应该在位置 第一个分界点确定了，接下来就是对左右两个数组继续进行上述操作啦

2. 快速排序的代码实现

int a[10]; void quick_sort(int left, int rght) //left和right是需要排序的数组边界 { if(i > j) { return; } int i, j, t,temp; temp = a[left]; i = left; j = right; while(i != j) { while(a[j] >= temp && i < j) { j--; //实现向左搜索 } while(a[i] <= temp && i < j) { i++; //实现向右搜索 } if(i < j) //交换 { t = a[i]; a[i] = a[j]; a[j] = t; } } //边界值归位 t = a[left]; a[left] = a[i]; a[i] = t; quicksort(left, i-1); //对左半数组递归快速排序 quicksort(i+1, right); //对右半数组递归快速排序 }

3.快速排序的效率

快速排序的平均时间复杂度为O(nlogn) 快速排序在平均情况下，只比最优情况多执行39%的比较操作，而且它的内循环效率非常高，因此快速排序确实厉害！！ 其实呢，对快速排序还是可以继续优化的:

随机快速排序三平均划分法…