写点什么

快速排序算法实现及优化

用户头像
Silently9527
关注
发布于: 2021 年 03 月 08 日
快速排序算法实现及优化

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore

程序员常用的 IDEA 插件:https://github.com/silently9527/ToolsetIdeaPlugin

完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server

微信公众号:贝塔学 Java

前言

快速排序可以说是使用最广的排序算法了,主要的特点是基于原地排序(不需要使用辅助数组,节省空间);其实对于长度为 N 的数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法,都没能够把这两个特点结合起来。

快速排序思路

快速排序也是一种分治的排序算法,把数组划分为两个子数组,然后递归对子数组进行排序,最终保证整个数组有序。

算法思路:

  1. 随机选择一个切分元素,通常选择的是数组的第一个元素

  2. 从数组的左边开始扫描找出大于等于切分元素的值,从数组的右边开始扫描找出小于等于切分元素的值,交换这两个值

  3. 循环这个过程直到左右两个指针相遇,这样就排定了一个元素,保证了切分元素左边的值都是小于它的值,右边的元素都是大于它的值

  4. 递归这个过程,最终保证整个数组有序

算法实现

根据快速排序算法的思路,我们可以写出第一版实现:

public class QuickSort implements SortTemplate {@Overridepublic void sort(Comparable[] array) {quickSort(array, 0, array.length - 1);}private void quickSort(Comparable[] array, int lo, int hi) {if (lo >= hi) {return;}int partition = partition(array, lo, hi);quickSort(array, lo, partition - 1);quickSort(array, partition + 1, hi);}private int partition(Comparable[] array, int lo, int hi) {int i = lo, j = hi + 1;Comparable el = array[lo];while (true) {while (less(array[++i], el)) {if (i == hi) {break;}}while (less(el, array[--j])) {if (j == lo) {break;}}if (i >= j) {break;}exch(array, i, j);}exch(array, lo, j);return j;}}
复制代码

其中exchless方法的实现请看之前的文章《常见的初级排序算法,这次全搞懂》

这段代码是实现快速排序的常规实现,考虑最糟糕的情况,假如需要排序的数组是已经有序的[1,2,3,4,5,6,7,8],执行快速排序的过程如图:

对一个长度为 N 的数组,最糟糕的情况下需要递归 N-1 次,所以时间复杂度是 O(n²),为了避免这种情况出现,我们来看下算法如何改进

算法改进

  • 保证随机性

为了避免最糟糕的情况出现,有两个办法,第一是在排序数组之前先随机打乱数组;第二是在 partition 方法中随机取切分元素,而不是固定取第一个,简单实现:

private int partition(Comparable[] array, int lo, int hi) {int i = lo, j = hi + 1;int random = new Random().nextInt(hi - lo) + lo;exch(array, lo, random);Comparable el = array[lo];while (true) {while (less(array[++i], el)) {if (i == hi) {break;}}while (less(el, array[--j])) {if (j == lo) {break;}}if (i >= j) {break;}exch(array, i, j);}exch(array, lo, j);return j;}
复制代码
  • 切换到插入排序

这点和归并排序一样,对于小数组的排序直接切换成插入排序

private void quickSort(Comparable[] array, int lo, int hi) {  if (lo >= hi) {     return;  }  if (hi - lo < 5) { //测试,小于5就切换到插入排序    insertionSort(array, lo, hi);    return;  }  int partition = partition(array, lo, hi);  quickSort(array, lo, partition - 1);  quickSort(array, partition + 1, hi);}  //插入排序private void insertionSort(Comparable[] array, int lo, int hi) {  for (int i = lo; i <= hi; i++) {    for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {    	exch(array, j, j - 1);    }  }}
复制代码
  • 三向切分

当我们需要排序的数组中出现了大量的重复元素,我们实现的快速排序在递归的时候会遇到许多全部重复的子数组,我们的算法依然会对其进行切分,这里有很大的提升空间。

思路就是先随意选择一个切分元素(el),然后把数组切换成大于、等于、小于三个部分,一次递归可以排定所有等于切分元素的值;

维护一个指针 lt、gt,使得 a[lo..lt-1]都小于切分元素,a[gt+1..hi]都大于切分元素;

  • 初始化变量:lt=lo, i=lo+1, gt=hi

  • if a[i] < el ; 交换 a[i]与 a[lt], i++, lt++

  • if a[i] > el ; 交换 a[gt]与 a[i], gt--

  • a[i] == el; i++

代码实现:

public class Quick3waySort implements SortTemplate {@Overridepublic void sort(Comparable[] array) {quickSort(array, 0, array.length - 1);}@SuppressWarnings("unchecked")private void quickSort(Comparable[] array, int lo, int hi) {if (lo >= hi) {return;}int lt = lo, i = lo + 1, gt = hi;Comparable el = array[lo];while (i <= gt) {int tmp = el.compareTo(array[i]);if (tmp > 0) {exch(array, lt++, i++);} else if (tmp < 0) {exch(array, i, gt--);} else {i++;}}quickSort(array, lo, lt - 1);quickSort(array, gt + 1, hi);}}
复制代码

最后(点关注,不迷路)

文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。

最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源🙏

文中所有源码已放入到了 github 仓库https://github.com/silently9527/JavaCore


发布于: 2021 年 03 月 08 日阅读数: 18
用户头像

Silently9527

关注

公众号:贝塔学JAVA 2018.05.09 加入

Simple Programmer, Make the complex simple

评论

发布
暂无评论
快速排序算法实现及优化