读懂三向快速排序

今天时间有限先讲一下三向快速排序

java中原始数据类型采用的就是三向快速排序 引用数据类型采用归并排序 归并排序有自顶向下和自顶向上两种 先介绍一下快速排序

  1. 快速排序是每次取当前数组的第一个元素作为基准
  2. 最左边和最右边出现指针,分别向中间移动
  3. 右边指针遇到比基准小的暂停移动,左边指针用到比基准大的暂停移动
  4. 交换元素位置
  5. 指针相遇赋值给基准
  6. 递归进行 排序算法地址 快速排序-简单实现

快速排序的缺点 想象一下如果按照生日日期对员工进行排序,排序过程的子数组中肯定存在大量重复的子数组,我们不应该对子数组再进行排序。

排序思想(开始时i,lt等于lo,gt等于hi)

  • a[i]小于v,将a[lt]和a[i]交换,lt和i都加一
  • a[i]大于v,将a[gt]和a[i]交换,将gt--
  • a[i]等于v,将i+1

排序轨迹

package com.snail.basic;

public class Quick3Way {
    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i<=gt){
            int cmp = a[i].compareTo(v);
            if(cmp<0)exch(a,lt++,i++);
            else if(cmp>0)exch(a,i,gt--);
            else i++;
        }
    //   现在 a[lo...lt-1]<v=a[lt..gt]<a[gt+1..hi]
        sort(a,lo,lt-1);
        sort(a,gt+1,hi);
    }
    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[j] = a[i];
        a[i] = t;
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券