怎么实现及优化快速排序算法

发布时间:2021-10-18 11:24:03 作者:iii
来源:亿速云 阅读:147

本篇内容主要讲解“怎么实现及优化快速排序算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么实现及优化快速排序算法”吧!

前言

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

快速排序思路

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

算法思路:

  1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

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

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

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

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

算法实现

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

public class QuickSort implements SortTemplate {     @Override     public 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;     } }

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

怎么实现及优化快速排序算法

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

算法改进

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]都大于切分元素;

代码实现:

public class Quick3waySort implements SortTemplate {     @Override     public 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);     } }

到此,相信大家对“怎么实现及优化快速排序算法”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. java实现快速排序算法
  2. C++如何实现快速排序算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

排序算法

上一篇:v-model结合radio、checkbox、select怎么用

下一篇:linux中如何使用gets和puts读写文件

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》