姬長信(Redy)

十大排序算法之快速排序

本文首发于[个人博客](https://ityongzhen.github.io/十大排序算法之快速排序.html) ## 前言 本系列排序包括十大经典排序算法。 ![](https://raw.githubusercontent.com/ITyongzhen/myBlogsPictures/master/img/20191031153959.png) - 使用的语言为/uff1aJava - 结构为/uff1a 定义抽象类`Sort`里面实现了/uff0c交换/uff0c大小比较等方法。例如交换两个值/uff0c直接传入下标就可以了。其他的具体排序的类都继承抽象类`Sort`。这样我们就能专注于算法本身。 ~~~~ /* * 返回值等于0/uff0c代表 array[i1] == array[i2] * 返回值小于0/uff0c代表 array[i1] < array[i2] * 返回值大于0/uff0c代表 array[i1] > array[i2] */ protected int cmp(int i1, int i2) { return array[i1].compareTo(array[i2]); } protected int cmp(T v1, T v2) { return v1.compareTo(v2); } protected void swap(int i1, int i2) { T tmp = array[i1]; array[i1] = array[i2]; array[i2] = tmp; } ~~~~ ## 什么是快速排序 - 快速排序/uff08Quicksort/uff09是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是/uff1a通过一趟排序将要排序的数据分割成独立的两部分/uff0c其中一部分的所有数据都比另外一部分的所有数据都要小/uff0c然后再按此方法对这两部分数据分别进行快速排序/uff0c整个排序过程可以递归进行/uff0c以此达到整个数据变成有序序列 ## 算法思想 ### 快速排序算法通过多次比较和交换来实现排序/uff0c其排序流程如下/uff1a - 首先设定一个分界值/uff0c通过该分界值将数组分成左右两部分。 - 将大于或等于分界值的数据集中到数组右边/uff0c小于分界值的数据集中到数组的左边。此时/uff0c左边部分中各元素都小于或等于分界值/uff0c而右边部分中各元素都大于或等于分界值。 - 然后/uff0c左边和右边的数据可以独立排序。对于左侧的数组数据/uff0c又可以取一个分界值/uff0c将该部分数据分成左右两部分/uff0c同样在左边放置较小值/uff0c右边放置较大值。右侧的数组数据也可以做类似处理。 - 重复上述过程/uff0c可以看出/uff0c这是一个递归定义。通过递归将左侧部分排好序后/uff0c再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后/uff0c整个数组的排序也就完成了。 ## 算法分析 ### 时间复杂度 - 在轴点左右元素数量比较均匀的情况下/uff0c同时也是最好的情况 O(nlogn) - 如果轴点左右元素数量极度不均匀/uff0c最坏情况 O(n^2) - 为了降低最坏情况的出现概率/uff0c一般采用**随机选择轴点元素** ### 空间复杂度 - 递归调用的原因/uff0c其空间复杂度是 O(nlogn) ### 算法稳定性 - 快速排序是一种不稳定排序算法。 ### 是否是原地算法 - 何为原地算法/uff1f - 不依赖额外的资源或者依赖少数的额外资源/uff0c仅依靠输出来覆盖输入 - 空间复杂度为 /ud835/udc42(1) 的都可以认为是原地算法 - 非原地算法/uff0c称为 Not-in-place 或者 Out-of-place - 快速排序属于 In-place ## 代码 ### 代码逻辑 - 从序列中选择一个轴点元素(pivot) - 假设每次选择0位置的元素为轴点元素 - 利用pivot将序列分割成2个子序列 - 将小于pivot的元素放在pivot左侧 - 将大于pivot的元素放在pivot右侧 - 等于pivot的元素放哪边都可以 - 对子序列进行前面两步操作/uff0c直到不能再分割(子序列中只剩下一个元素) - 快速排序的本质 - 逐渐将每个元素都转换成轴点元素 ~~~~ package YZ.Sort; public class QuickSort> extends Sort { @Override protected void sort() { sort(0, array.length); } /** * 对 [begin, end) 范围的元素进行快速排序 * @param begin * @param end */ private void sort(int begin,int end) { if (end-begin<2) { return; } // 确定轴点位置 O(n) int mid = pivotIndex(begin, end); // 对子序列进行快速排序 sort(begin,mid); sort(mid+1, end); } /** * 构造出 [begin, end) 范围的轴点元素 * @return 轴点元素的最终位置 */ private int pivotIndex(int begin,int end) { //随机选择一个元素和begin位置的元素进行交换 swap(begin, begin+(int)Math.random()*(end-begin)); // 备份begin位置的元素 T pivot = array[begin]; end--; while (begin 轴点元素 end--; }else {// 右边元素 <= 轴点元素 array[begin++] = array[end]; break; //break退出/uff0c从另外一边/uff08begin/uff09开始 } } while (begin0) { // 左边元素 < 轴点元素 begin++; }else {// 左边元素 >= 轴点元素 array[end--] = array[begin]; break;//break退出/uff0c从另外一边/uff08end/uff09开始 } } } // 将备份的轴点元素放入最终的位置 array[begin] = pivot; // 返回轴点元素的位置 return begin; } } ~~~~ ### 验证 使用数据源如下 >Integer[] array = Integers.random(20000, 1, 80000); 结果为/uff1a 【BubbleSort】 稳定性/uff1atrue 耗时/uff1a2.494s(2494ms) 比较次数/uff1a2.00亿 交换次数/uff1a9950.84万 【BubbleSort1】 稳定性/uff1atrue 耗时/uff1a1.95s(1950ms) 比较次数/uff1a2.00亿 交换次数/uff1a9950.84万 【BubbleSort2】 稳定性/uff1atrue 耗时/uff1a2.048s(2048ms) 比较次数/uff1a2.00亿 交换次数/uff1a9950.84万 【InsertionSort1】 稳定性/uff1atrue 耗时/uff1a1.125s(1125ms) 比较次数/uff1a9952.84万 交换次数/uff1a9950.84万 【InsertionSort2】 稳定性/uff1atrue 耗时/uff1a0.772s(772ms) 比较次数/uff1a9952.84万 交换次数/uff1a0 【InsertionSort3】 稳定性/uff1atrue 耗时/uff1a0.546s(546ms) 比较次数/uff1a25.80万 交换次数/uff1a0 【SelectionSort】 稳定性/uff1atrue 耗时/uff1a0.458s(458ms) 比较次数/uff1a2.00亿 交换次数/uff1a2.00万 【HeapSort】 稳定性/uff1afalse 耗时/uff1a0.013s(13ms) 比较次数/uff1a51.08万 交换次数/uff1a2.00万 【QuickSort】 稳定性/uff1afalse 耗时/uff1a0.01s(10ms) 比较次数/uff1a32.00万 交换次数/uff1a1.32万 【MergeSort】 稳定性/uff1atrue 耗时/uff1a0.011s(11ms) 比较次数/uff1a26.08万 交换次数/uff1a0 结果来看快速排序性能还是很好的。 ## 代码地址 - 文中的代码在git上/uff1a[github地址](https://github.com/ITyongzhen/DataStructureAndAlgorithm)

退出移动版