数据结构与算法之排序算法-快速排序(分治)

排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~

那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：

📕 插入类排序：数据结构与算法之排序算法-插入排序-CSDN博客

📖 直接插入排序

📖 希尔排序

📕 交换类排序：[本篇]

📖 冒泡排序

📖 冒泡排序-优化

📖 快速排序(Hoare，挖坑法，前后指针法)

📖 快速排序-优化

📕 选择类排序：(博主正在连夜码字中...)

📖 简单选择排序

📖 堆排序

📕 归并类排序：(博主正在连夜码字中...)

📖 归并排序

📚 线性时间非比较类：

📕 非比较类排序：(博主正在连夜码字中...)

📖 计数排序

📖 桶排序

📖 基数排序

一、冒泡排序

稳定性：稳定

时间复杂度：O(n^2)

额外空间复杂度：O(1)

① 冒泡排序实现

作为排序算法中最为基础的一种排序，有关冒泡排序的知识，想必大家早都了解了，但是既然这边提到的是交换排序，或多或少也要提一嘴嘛~

📚 算法思想：

冒泡排序：通过两层循环，外层循环(int i = 0;i < len - 1;i++)代表需要比较的轮数，内层循环(int j = 0;j < len - 1 - i;j++)代表每次循环的遍历与交换。

通过内层循环，每次比较两个元素，如果前者元素大于后者，则将两者调换位置(使大的靠后)，这也一层下来就能将数组中最大的元素放到最后，而下轮再次进行时，就可以不必再遍历已经排好序的元素，这也就是为什么内层循环的边界条件为(len - 1 - i)。

📖 代码实现：

    public static void bubbleSort(int[] arr){int len = arr.length;for(int i = 0;i < len - 1;i++){for(int j = 0;j < len - 1 - i;j++){if(arr[j] > arr[j + 1]){swap(arr,j,j + 1);}}}}private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

② 冒泡排序简单优化

稳定性：稳定

时间复杂度：O(n^2) -> 最好为O(n)

额外空间复杂度：O(1)

📚 算法思想：

而对于这种排序，其实有时数组具有一定的特殊性，比如可能出现刚刚将外层循环遍历一半，数组就已经有序了的情况，而针对这种情况，我们也可以做一个简单的优化：

就是创建一个布尔类型变量，在一轮比较的过程中如果没有发生交换，就代表此时数组已经有序，即可以通过判断布尔类型变量来直接结束排序。

📖 代码实现：

    public static void bubbleSortUp(int[] arr){int len = arr.length;for(int i = 0;i < len - 1;i++){boolean flg = true;for(int j = 0;j < len - 1 - i;j++){if(arr[j] > arr[j + 1]){swap(arr,j,j + 1);flg = false;}}if(flg){return;}}}

③ 排序算法的时间测试

上面我们提到了，它的时间复杂度是O(n^2)，这是比较不理想的，那么对于它处理数据的效率究竟如何，我们可以写一段代码，用随机数填满数组，然后让它进行排序，并输出其中所消耗的时间：

📖 将数组中填满随机数的方法：

    public static void randomOrder(int[] array) {Random random = new Random();for (int i = 0; i < array.length; i++) {array[i] = random.nextInt(array.length);}}

📖 测试排序算法消耗时间的方法：

    public static void testSort(int[] array) {array = Arrays.copyOf(array,array.length);//获取当前时间与1970年1月1日0点0分0秒之间的时间差，时间差以毫秒为单位long startTime = System.currentTimeMillis();bubbleSort(array);long endTime = System.currentTimeMillis();System.out.println("冒泡排序耗时："+(endTime-startTime));System.out.println(Arrays.toString(array));}

可以在主函数创建一个随机数填满的数组，修改testSort方法测试不同排序算法需要消耗的时间：

可以看到，优化的效果确实还是有的。但即便如此...冒泡排序仍然不适合日常生活中使用，为了增强说服性，我们可以再将上篇学习过的希尔排序也测试一下：

二、快速排序

稳定性：不稳定

时间复杂度：O(n logn) --->最坏为O(n^2)

额外空间复杂度：O(logn)

(快速排序是一种主要以递归思想实现的算法，所以后面代码的书写中，一定不要忘记递归出口~)

① 习题引入:移动零

快速排序的基本思想是"分治" ，也就是将大问题不断地化作一个个类似的小问题，直到某一次这些小问题能够很快的解决，就从此刻从小问题到向上的大问题开始解决。

而想要实现"分治"中的"大问题化小问题"，就需要我们利用双指针遍历数组，并且按照某种规律，使得最后left与right相遇时，左侧部分符合某种性质，右侧部分同样符合某种性质，这样才能够将两侧化作两个小问题，才算得上是"分治"。

那么引入"移动零"这道题，就是因为其实这题的解决方法，就类似我们快速排序的中最核心的"大问题分小问题"的这一步：

📚 思路提示：

我们可以通过双指针的方式，使left作为区域划分的临界点(因为开始时还未分治，所以开始时指向0位置)，使right代表移动指针扫描数组，如果right扫描到了非0元素，就将这个元素通过交换扔到left的位置，同时left++，最终就能够达到(left左侧都为非0元素，left右侧都为0)的目的。

⭐ 图示：

📖 代码示例：

class Solution {public void moveZeroes(int[] nums) {int len = nums.length;int left = 0;int right = 0;for(;right < len;right++){while(right < len && nums[right] != 0){swap(nums,left++,right++);}}}public void swap(int[] arr,int i,int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

② 快速排序(前后指针法)

通过上面"移动零"的练习，我们已经知道了快速排序的基本思想"分治"。

📚 思路提示：

快速排序的具体实现思想：以数组的首元素作为基准元素，同样以left作为区域划分的临界点，以right作为移动指针扫描数组，将小于基准元素的值交换到左边部分，同时扩大区域，left++，这样当right扫描完整个数组后，就能将数组分为 [start,left - 1] [left + 1,end] 这两个部分，而这两个部分分别代表(小于基准值)和(大于等于基准值)

(注意点："移动零"只需要分辨(0和非0)，所以对基准值的要求并不严格，但"快速排序"需要我们精确的将元素排序，所以在使用right扫描数组时，我们要确保基准值一直在原位置保持不动，以便于最后将它放在两个区域中间。(解决方案就是先扩大左侧范围，后交换元素 -> ++left))

⭐ 图示：

📖 代码示例：

    public static void quickSort3(int[] nums,int start,int end){if(start >= end){return;}int count = nums[start];int left = start;int right = start + 1;for(;right <= end;right++){while(right <= end && nums[right] < count) {swap(nums, ++left, right++);}}int index = left;swap(nums,start,index);quickSort3(nums,start,index - 1);quickSort3(nums,index + 1,end);}

③ 快速排序(挖坑法)

📚 思路提示：

思想大致保持不变，仍然是采取我们的"分治"思想，只是"挖坑法"的 left 和 right 的起始位置与其中的交换条件或许与"前后指针法"稍微有些差异。

挖坑法指，我们仍然取数组中的 start 位置作为基准元素，并且将基准元素用一个整型变量存储起来。那么我们就可以看做 start 位置的元素被挖了出来(实际还存在)

而为了填上这个坑，我们就需要在后面找到一个合适的元素(小于基准元素)填上这个坑，同时被找到的元素也相当于被挖走了，所以就要从前再找一个合适的元素(大于等于基准元素)填上这个新坑

所以过程中一直都会有一个"虚构"的坑，最后当 left 和 right 相遇时，我们将基准元素再放入这个坑中，即完成了(left左侧都小于基准元素)(left右侧都大于等于基准元素)

⭐ 图示：

📖 代码示例：

    public static void quickSort1(int[] array,int start,int end){if(start >= end){return;}int tmp = array[start];int left = start;int right = end;while(left < right){while(left < right && array[right] >= tmp){right--;}array[left] = array[right];while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}int index = left;array[index] = tmp;quickSort1(array,start,index - 1);quickSort1(array,index + 1,end);}

④ 快速排序(Hoare法)

📚 思路提示：

该方法与挖坑法的形式类似，仅仅修改了一些元素交换的细节：

同样取数组中的 start 位置作为基准元素，使用左侧的left和右侧的right同时进行查找，左侧left需要找到(大于基准元素)，右侧的right需要找到(小于基准元素)。

当找到两个目标元素时，时left和right的元素进行交换，然后再次继续查找，直到left 与 right相遇，再将这个相遇点与最开始的基准元素再次交换一次，达成分组。

(由于和上一个挖坑法非常类似，很好理解~这里就不上图了)

📖 代码示例：

    public static void quickSort2(int[] array,int start,int end){if(start >= end){return;}int tmp = array[start];int left = start;int right = end;while(left < right){while(left < right && array[right] >= tmp){right--;}while(left < right && array[left] <= tmp){left++;}swap(array,left,right);}swap(array,start,left);int index = left;quickSort2(array,start,index - 1);quickSort2(array,index + 1,end);}

三、快速排序优化(非常重要)

到这里或许有人会产生疑问：快速排序的速度不是很快吗？这么快的排序也有优化空间？

有这样的疑问是正常的，但或许大家没有注意到前面一个不起眼的点：最坏时间复杂度为O(n^2)

所以快速排序也并不能做到在任何情况下都"快速"，那么为什么会有这么一种情况呢？这种情况又是什么？

这种情况就是：当数组本身已经有序或趋近有序时，快速排序的效率会显著下降

因为当数组本身已经有序，那我们每次进行分治，遍历整个数组后只能将原数组分出去一个元素，而一次次的进行分治，最后不仅分治了(n - 1)次，多次调用函数还会造成额外的消耗。所以这种低效率的情况是非常严重和急需解决的。

那就要引入我们快速排序优化的核心思想：数组分三块

① 习题引入:颜色分类

我们可以发现，题中数组的值只有三种情况：0，1，2。也正因为如此，我才选这题作为引入"数组分三块"的概念引入题~

在往常的情况下，我们使用快速排序对数组进行排序是非常快的。但那是对于数组本无序，并且重复元素也并不多的情况下。但这题中数组的值只有0，1，2。如果测试用例给我们一个形如[0，0，0，0，0，0，0，1，1，1，1，1，1，1，1，2，2，2，2，2，2]...的数组，那么此时将它交给快速排序(时间复杂度退化成O(n^2))，快速排序也会表示："我也很头疼啊~"。

📚 思路提示：

但那是因为我们之前分组的方法是："小于基准元素放左边，大于等于基准元素放右边"。

现在我们摒弃这种思路，而是仅看此题，就能得出一个更清晰的结论：

"小于1的放左边，等于1的放中间，大于1的放右边"。

没错的！这就是我们"数组分三块"的非常关键的核心！

那么通过这种方式，去实现这题就非常简单了，在之前将数组分两块的情况下，我们需要用left作为分组的标志；而将数组分三块也很简单，我们只需要再定义一个指针就好了。

我们用left作为左侧"小于1"范围的边界，用right作为右侧"大于1"范围的边界，再定义一个 i 用于扫描整个数组，将"小于1"的元素放到左侧，将"大于1"的元素放到右侧，这样到最后扫描结束，[left，right]的范围内自然而然就都是1了。

⭐ 图示：

📖 代码示例：

class Solution {public void sortColors(int[] nums) {int len = nums.length;int left = -1;int right = len;int i = 0;while(i < right){if(nums[i] < 1){swap(nums,++left,i++);}else if(nums[i] > 1){swap(nums,--right,i);}else {i++;}}}
}

② 快速排序优化(数组分三块)

经过上面习题的练习，我们就已经将快速排序优化的最关键点解决了，接下来我们只需要补充一些概念即可：

取基准元素：使用随机数取下标的方法，将对应下标的值作为该次扫描的基准值。

    int tmpindex = new Random().nextInt(r - l + 1) + l;int tmp = array[new Random().nextInt(r - l + 1) + l];

其中(r - l + 1)代表数组的元素，" +l "代表偏移量
(比如将长度[0，100]分为[0，50] [51，100]的两个数组时，则(r - l + 1 = 50) l = 51)

(如果想使快速排序的时间复杂度逼近O(n logn)，必须使用随机取基准元素的方式，而相应的证明步骤过于繁琐，想要详细了解可以去——《算法导论》这本书去查找)

通过这个取基准值的方式，结合上面"数组分三块"的思想，很容易就能写出我们的快排：

📖 代码示例：

    public static void qsort(int[] array,int l,int r){if(l >= r){return;}int tmp = array[new Random().nextInt(r - l + 1) + l];int left = l - 1;int right = r + 1;int i = l;while(i < right){if(array[i] < tmp){swap(array,++left,i++);}else if(array[i] == tmp){i++;}else if(array[i] > tmp){swap(array,--right,i);}}qsort(array,l,left);qsort(array,right,r);}