今天时间有限先讲一下三向快速排序
java中原始数据类型采用的就是三向快速排序 引用数据类型采用归并排序 归并排序有自顶向下和自顶向上两种 先介绍一下快速排序
快速排序的缺点
想象一下如果按照生日日期对员工进行排序,排序过程的子数组中肯定存在大量重复的子数组,我们不应该对子数组再进行排序。
排序思想(开始时i,lt等于lo,gt等于hi)
排序轨迹
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;
}
}