快速排序为什么快

        很多书上都说快速排序是实践中排序速度最快的排序。原因有很多，从计算机角度来说，快速排序中的循环体最简洁，只有数组指针的移动，双向扫描的指针仅仅是i++与j--操作以及数据（或引用）的交换，可以很好的利用缓存。相对的，堆排序中的指针移动就很没有规律。但是快速排序的平均复杂度是依赖随机的数据输入，如果数据趋于有序，快速排序的复杂度就会退化为O(n^2)。

快排常见的问题

快速排序的思想很简单，但是想正确的写出代码并不简单。

最保险的写法：单向扫描。

和大部分教科书上双向扫描不同，快速排序还有一个单向扫描的版本。这种写法很简洁，少了很多边界判断，不容易出错。这里有单向扫描的快排版本和伪码。

常用的写法：双向扫描

双向扫描是最基本的快速排序写法。但是几乎每一步都有或大或小的坑。

这里给出我写的版本：

容易产生以下问题：

1.初始化i,j：因为进入while循环首先要进行++i和--j操作，所以要把i和j初始化为start-1和end+1。问题表现：结果大致有序但是不正确。

2.要先进行++和--操作再比较：这里最容易出现问题。第一次写快速排序很容易就把指针++和--操作放入循环体中，这样指针会在第一次交换操作后停下。问题表现：不能跳出循环，一直运行。

3.边界判断：47行代码对于j的边界判断是多余的，但是为了正确性（以及与上一行对称），最好还是写上。问题表现：数组下标越界。

4.i<j才进行交换：如果把i<j放在45行while的判断条件中，删去48行的判断，会导致额外的交换，结果错误。问题表现：结果大致有序但是不正确。

5.交换枢纽元素与j元素：为什么不与i交换？很多书上没有写，如果不思考一下，写成与i元素交换，就会导致错误的结果。首先要理解：i停下时，i元素总是大于或等于枢纽元素，j停下时，j元素总是小于或等于枢纽元素。与i还是j交换关键看枢纽元素的位置，这里是选第一个元素作为枢纽元素，由于此次排序完成后第一个元素的值应该小于或等于枢纽元素，所以要找一个小于或等于枢纽元素的元素放到start位置，也就是j所指向的元素。

还有一个要注意的地方:元素与枢纽元素相等时指针也要停下。这样看起来做了额外的交换，但是可以保证在输入元素全部相等的情况下每次会将输入数组切分成一半。如果相等时指针不停下，快速排序就会在有大量重复元素的输入时复杂度退化为O(n^2)。