读懂三向快速排序

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

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;
    }

}