:-: 14.7 快速排序 * * * * * **基本概念：** 它又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nlogn)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。 它的基本思想：挖坑填数+分治法。首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 **算法的运作** 快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分区版本。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为： 1、从数列中挑出一个元素，称为"基准"（pivot）。 2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 3、递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 **图片示例：** :-:  **代码实现：** 第一种方式：基准取头法。 ~~~ public void quickSort(int array[], int top, int tail) { if (top >= tail) { return; } int left = top, right = tail; int temp = array[left];// 数组的第一作为中轴 while (left < right) { while (left < right && array[right] >= temp) { right--; } array[left] = array[right];// 比中轴小的记录移动到低端 while (left < right && array[left] < temp) { left++; } array[right] = array[left]; } if (left == right) { array[left] = temp; } if (left != top) { quickSort(array, 0, left - 1); } if (right != tail) { quickSort(array, right + 1, array.length - 1); } } ~~~ 第二种方式：基准取尾法。 ~~~ public void quickSort(int nums[], int top, int tail) { if (top >= tail) return; int mid = nums[tail]; int left = top, right = tail - 1; while (left < right) { while (nums[left] < mid && left < right) { left++; } while (nums[right] >= mid && left < right) { right--; } int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } if (nums[left] >= nums[tail]) { int temp = nums[left]; nums[left] = nums[tail]; nums[tail] = temp; } else { left++; } quickSort(nums, top, left - 1); quickSort(nums, left + 1, tail); } ~~~ 第三种方式：基准取中法。 ~~~ public void quickSort(int nums[], int top, int tail) { if (top >= tail) return; int left = top, right = tail, mid = nums[(top + tail) / 2]; while (left <= right) { while (nums[left] < mid) { ++left; } while (nums[right] > mid) { --right; } if (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; ++left; --right; } else if (left == right) { ++left; } } quickSort(nums, top, right); quickSort(nums, left, tail); } ~~~ **基准的选择：** 基准普遍的有三种选择方法： 1、固定基准元，一般选取中间值或头部值或尾部值。如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时或部分有序，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，数组全部有序时，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为O(n^2)。所以此种方式要慎用。 2、随机基准元，这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。 3、三数取中，一般是分别取出数组的头部元素，尾部元素和中部元素， 在这三个数中取出中位数，作为基准元素。最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形。（简单来说，就是随机取三个数，取中位数）。 **复杂度分析：** 时间复杂度：平均：O(nlogn)、最坏：O(n^2)、最优：O(nlogn)。 空间复杂度：最坏：根据具体的实现方式，一般为O(logn),最优：O(1)。 **优化：** 1、快速排序对于处理小数组（N <= 20）的数组时，快速排序比插入排序要慢， 所以在排序小数组时应该切换到插入排序，我们面对小数组的通常的解决办法是对于小的数组不递归的使用快速排序，而代之以诸如插入排序这样的对小数组有效的排序算法。 2、普通的快速排序还有一个缺点， 那就是会交换一些相同的元素，尤其是当我们处理有大量重复元素的数组时，快排会做很多的无用功，所以由此人们研究出了三切分快排（三路划分） ， 在左右游标的基础上，再增加了一个游标，用于处理和基准元素相同的元素，也就是将数组分为三部分：小于当前切分元素的部分，等于当前切分元素的部分，大于当前切分元素的部分。 ~~~ public static void exchange(int[] sum, int i, int j) { int temp = sum[i]; sum[i] = sum[j]; sum[j] = temp; } public static void quickSort(int[] nums, int top, int tail) { if (top >= tail) { return; } int lt = top, gt = tail, i = top + 1; int pivot = nums[top]; while (i <= gt) { if (nums[i] > pivot) { exchange(nums, i, gt--); } else if (nums[i] < pivot) { exchange(nums, i++, lt++); } else { i++; } } quickSort(nums, top, lt - 1); quickSort(nums, gt + 1, tail); } ~~~ **复杂度分析：** 时间复杂度：最优：O(nlgn)提升到O(n)。 时间复杂度：根据具体实现情况。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [维基百科——快速排序](https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) [快速排序、基准元的选取及其优化](https://blog.csdn.net/liuyi1207164339/article/details/50827608) [快速排序算法的优化](https://www.cnblogs.com/penghuwan/p/7883076.html) **扩展了解：** [三向切分的快速排序（扩展了解）](https://www.jianshu.com/p/d70aeccaee19) [基本排序算法（扩展了解）](https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/) [聊聊4种主流排序算法(下)（扩展了解）](https://blog.staynoob.cn/post/2016/05/insertion-shell-merge-quick-sort-algorithm-2/)