写点什么

十大排序算法 -- 快速排序

用户头像
阿粤Ayue
关注
发布于: 3 小时前
十大排序算法--快速排序

快速排序

快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。JDK 中 Arrays 的 sort()方法,具体的排序细节就是使用快速排序实现的。


从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作。

问题

若给定一个无序数组 [8, 5, 6, 4, 3, 1, 7, 2],并指定一个数为基准,拆分数组使得左侧的数都小于等于它 ,右侧的数都大于它。


基准的选取最优的情况是基准值刚好取在无序区数值的中位数,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数,但是一般很难做到最优。基准的选取一般有三种方式:


  • 选取数组的第一个元素

  • 选取数组的最后一个元素

  • 以及选取第一个、最后一个以及中间的元素的中位数(如 4 5 6 7, 第一个 4, 最后一个 7, 中间的为 5, 这三个数的中位数为5, 所以选择 5 作为基准)。

思路

  1. 随机选择数组的一个元素,比如 6 为基准,拆分数组同时引入一个初始指针,也叫分区指示器,初始指针指向 -1

  2. 将数组中的元素和基准数遍历比较

  3. 若当前元素大于基准数,不做任何变化

  4. 若当前元素小于等于基准数时,分割指示器右移一位,同时

  5. 当前元素下标小于等于分区指示器时,当前元素保持不动

  6. 当前元素下标大于分区指示器时,当前元素和分区指示器所指元素交换


荷兰国旗问题

荷兰的国旗是由红白蓝三种颜色构成,如图:



若现在给一个随机的图形,如下:



把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,这类问题称作荷兰国旗问题。


对应 leetcode:颜色分类


给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
复制代码


分析:


假如给定一个数组[8, 3, 6, 2, 5, 1, 7, 5],做如下操作:


  1. 随机选择数组的一个元素,比如 5 为基准,拆分数组同时引入一个左分区指示器,指向 -1,右分区指示器指向基准数(注:此时的基准数为尾元素)

  2. 若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,

  3. 索引保持不变

  4. 若当前元素小于等于基准数时,左分区指示器右移一位,索引右移

  5. 当前元素大于等于左分区指示器所指元素,当前元素保持不动

  6. 当前元素小于左分区指示器所指元素,交换


简单来说就是,左分区指示器向右移动的过程中,如果遇到大于或等于基准数时,则停止移动,右分区指示器向左移动的过程中,如果遇到小于或等于主元的元素则停止移动。这种操作也叫双向快速排序


代码实现

public class QuickSort {
public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
private static int[] sort(int[] array, int left, int right) { if (array.length < 1 || left > right) return null; //拆分 int partitionIndex = partition(array, left, right); //递归 if (partitionIndex > left) { sort(array, left, partitionIndex - 1); } if (partitionIndex < right) { sort(array, partitionIndex + 1, right); } return array; }
/** * 分区快排操作 * * @param array 原数组 * @param left 左侧头索引 * @param right 右侧尾索引 * @return 分区指示器 最后指向基准数 */ public static int partition(int[] array, int left, int right) { //基准数下标---随机方式取值,也就是数组的长度随机1-8之间 int pivot = (int) (left + Math.random() * (right - left + 1)); //分区指示器索引 int partitionIndex = left - 1; //基准数和尾部元素交换 swap(array, pivot, right); //按照规定,如果当前元素大于基准数不做任何操作; //小于基准数,分区指示器右移,且当前元素的索引大于分区指示器,交换 for (int i = left; i <= right; i++) { if (array[i] <= array[right]) {//当前元素小于等于基准数 partitionIndex++; if (i > partitionIndex) {//当前元素的索引大于分区指示器 //交换 swap(array, i, partitionIndex); } } } return partitionIndex; }
/** * 双向扫描排序 */ public static int partitionTwoWay(int[] array, int left, int right) { //基准数 int pivot = array[right]; //左分区指示器索引 int leftIndex = left - 1; //右分区指示器索引 int rightIndex = right; //索引 int index = left; while (index < rightIndex) { //若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,索引保持不变 if (array[index] > pivot) { swap(array, index, --rightIndex); } else if (array[index] <= pivot) {//当前元素小于等于基准数时,左分割指示器右移一位,索引右移 leftIndex++; index++; //当前元素小于等于左分区指示器所指元素,交换 if (array[index] < array[leftIndex]) { swap(array, index, leftIndex); } } } //索引和 L 指向同一个元素 swap(array, right, rightIndex); return 1; }
//交换 private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }

public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); }

public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY, 0, ARRAY.length - 1)); System.out.println("====================双向排序=================="); print(ARRAY2); System.out.println("============================================"); print(sort(ARRAY2, 0, ARRAY2.length - 1)); }}
复制代码

时间复杂度

在拆分数组的时候可能会出现一种极端的情况,每次拆分的时候,基准数左边的元素个数都为 0,而右边都为 n-1 个。这个时候,就需要拆分 n 次了。而每次拆分整理的时间复杂度为 O(n),所以最坏的时间复杂度为 O(n<sup>2</sup>)。什么意思?举个简单例子:


在不知道初始序列已经有序的情况下进行排序,第 1 趟排序经过 n-1 次比较后,将第 1 个元素仍然定在原来的位置上,并得到一个长度为 n-1 的子序列;第 2 趟排序经过 n-2 次比较后,将第 2 个元素确定在它原来的位置上,又得到一个长度为 n-2 的子序列;以此类推,最终总的比较次数:


C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2


所以最坏的情况下,快速排序的时间复杂度为 O(n^2)


而最好的情况就是每次拆分都能够从数组的中间拆分,这样拆分 logn 次就行了,此时的时间复杂度为 O(nlogn)。


而平均时间复杂度,则是假设每次基准数随机,最后算出来的时间复杂度为 O(nlogn)


参考:快速排序的时间复杂度与空间复杂度

算法稳定性

通过上面的分析可以知道,在随机取基准数的时候,数据是可能会发生变化的,所以快速排序有不是稳定的情况。

发布于: 3 小时前阅读数: 2
用户头像

阿粤Ayue

关注

微信搜:Javatv 2019.10.16 加入

学习知识,目光坚毅

评论

发布
暂无评论
十大排序算法--快速排序