Java数据结构之排序

Comparable接口

源码：

public interface Comparable<T>{
    int compareTo(T other);
}

主要用于比较
基本类型的包装类、String、File和URL类都实现了这个接口，所以写排序方法时入参可以定义为Comparable[]数组，这样可以接收多个类型的数组
其中浮点数的比较技巧是扩大为长度一致的整型再进行比较，但是无法避免数据为NaN或无穷的情况，建议自定义比较方法
选择排序

不具有稳定性：假设倒数四个元素是3332，当擂台是第一个3时，2会被换到它的位置上，擂轮到后面另外两个3来当时，数组都不会动了，那么第一个3变成了最后一个，稳定性就被破坏了。

/**
 * @Author haien
 * @Description 选择排序:每趟都比较剩余未排序元素，记住最小的那个的下标，与擂台互换位置
 *              时间复杂度：N^2
 *              缺点：运行时间和输入无关，一个有序的数组和无序的数组所需排序时间相同
 *              优点：数据移动是最少的，最多交换N次，这是其他算法不具备的
 * @Date 2018/10/16
 * @Param [a]
 * @return void
 **/
public static void selectSort(Comparable[] a){
    for (int i=0;i<a.length-1;i++){
        int min=i;
        for(int j=i+1;j<a.length;j++){
            if(less(a[j],a[min])){
                min=j;
            }
        }
        exch(a,i,min); //每趟只需交换一次；如果令剩余未排序元素和擂台比较，只要比擂台小则交换的话，那至多交换剩余元素那么多次
    }
}

插入排序

具有稳定性，即相等的元素，原来a1在a2前，排序后a1还在a2前

/**
 * @Author haien
 * @Description 插入排序：每一个都跟前面所有元素比较，比人小的话就跟人互换位置，互换一次即退出内层循环
 *              优点：运行时间跟输入有关，如果数组已接近有序则排序时间大大缩短
 *              缺点：对于元素都一样的数组排序时间和完全无序的相同
 *              时间复杂度：原始数组有序时为N，无序为N^2；比选择排序快1.2倍
 * @Date 2018/10/17
 * @Param [a]
 * @return void
 **/
public static void insertSort(Comparable[] a){
    for(int i=0;i<a.length-1;i++){
        for(int j=i+1;j>0&&!less(a[j-1],a[j]);j--){
            exch(a,j-1,j);
        }
    }
}

插入排序对于某些部分有序的数组效率很高
- 数组中每个元素距离它的最终位置都不远
- 一个有序的大数组接一个小数组
- 数组中只有几个元素的位置不正确
这些情况下插入排序很可能比任何排序算法都要快
快速排序

/**
 * @Author haien
 * @Description 快速排序：随机选一个基数，比它大的调到右边，小的调到左边，然后对左右两边都*                        递归进行这个操作
 *              时间复杂度：O(nlogn),logn次递归，每次递归n次比较
 * @Date 2018/10/21
 * @Param [a]
 * @return void
 **/
public static void quickSort(Comparable[]a,int lo,int hi){
    if(lo<hi){
        int mid=partition(a,lo,hi); //获取基数位置
        quickSort(a,lo,mid-1); //基数左边全是小的
        quickSort(a,mid+1,hi); //基数右边全是大的
    }
}

/**
 * @Author haien
 * @Description 以lo（排头元素）为基数，i从头扫描，发现比lo的元素停下，调动j从尾开始扫描，发现小的即与i交换位置
 *              直到两指针相遇结束
 * @Date 2018/10/21
 * @Param [a, lo, hi]
 * @return int
 **/
public static int partition(Comparable[]a,int lo,int hi){
    int i=lo,j=hi+1;
    while(true){
        while (less(a[++i],a[lo])) //i从头开始扫描，发现大于基数的元素停下
            if(i>=hi) break; //扫到尾结束
        while (less(a[lo],a[--j])) //j从尾开始扫，发现小于基数的元素停下
            if(j<=lo) break; //扫到头结束
        if(i>=j) break; //跳出循环的原因如果是因为扫到头、尾或相遇则结束
        exch(a,i,j); //否则就是该交换元素了
    }
    exch(a,lo,j); //算法没写好可能lo会被换到j所指的末尾上去
    return j; //把相遇点返回去
}


/**
 * @Author haien
 * @Description 三向切分的快速排序：把数组分为小于、等于、大于三组；三个指针，一个跟着基数，一个从头扫描，一个从尾
 *              优点：重复元素较多的数组适用，大大节省时间
 *              缺点：
 * @Date 2018/10/22
 * @Param [a, lo, hi]
 * @return void
 **/
public static void quick3way(Comparable[] a,int lo,int hi){
    if(lo<hi){
        int lt=lo,i=lo+1,j=hi,cmp;
        Comparable v=a[lo]; //先把基数lo取出来，若放在循环里会变
        while (i<=j) {
            cmp = v.compareTo(a[i]);
            if (cmp > 0) //小于基数则跟基数交换位置，相当于放在了基数的左边
                exch(a, lt++, i++); //lt++，跟上基数
            else if (cmp < 0)
                exch(a, i, j--);
            else i++; //等于则不用移动元素
        }
        quick3way(a,lo,lt-1); //左边全是比基数小但无序的数
        quick3way(a,i,hi); //右边全是比基数大但无序的数
    }
}

希尔排序

前面我们说插入排序针对部分有序数组效率特别高，所以我们可以在进行选择排序前先把数组排成部分有序的。
首先设想一个完全逆序的数组，想要把最小的元素排到首位要经过多次交换，这是由于插入排序每次交换只移动一位的缘故，那我们可不可以每次都把元素移动得远一点呢？
希尔排序的思路就是这样的，比如有16个数据，那我们从第13位开始，让它跟第0位比较，第14位跟第1位交换，……，一直到最后一位，这样一来比较小的元素自然都到了前面去（当然可能后面这几位原本都是些大数，但是这样做却能有效应对逆序等极端情况）。这次比较的距离是13，接下来我们控制比较距离为4，第4位跟第0位，第5位跟第1位，……，一直到最后一位，这样数组进一步有序，被分为了4个各自有序的数组（0，4,8,12组成一个有序数组，…）。

最后比较距离设为1，即应用插入排序，由于数组基本有序，最小值一定是这4个小数组首位的其中一个，所以比较次数大大减少，性能提高。

数组越大，希尔排序的优势越大。

/**
 * @Author haien
 * @Description 希尔排序：前面我们说插入排序针对部分有序数组效率特别高，
 *                       所以我们可以在进行选择排序前先把数组排成部分有序的
 *                       思路即是比较时不要邻位比较而是隔一段距离比较
 *              优点：适用于大数组、无序数组
 *              时间复杂度：N^3/2（无法推算）
 *
 * @Date 2018/10/17
 * @Param [a]
 * @return void
 **/
public static void shellSort(Comparable[] a){
    int h=1;
    int n=a.length;
    while(h<n/3)
        h=h*3+1; //保证第一次排序时距离足够远,h=1,4,13,40,121,364,1093,……
    //当n=16时，h=13,4,1
    while(h>=1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && !less(a[j - h], a[j]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h/=3; //逐渐缩小距离
    }
}

归并排序

具有稳定性

/**
 * @Author haien
 * @Description 归并排序：将两个有序数组合并为一个；所以要另写一个算法将数组分到只剩一个元素，保证有序
 *              优点：处理数百万甚至更大规模的数组
 *              缺点：辅助数组所需空间和N成正比
 *              时间复杂度：NlogN
 * @Date 2018/10/21
 * @Param [a, lo, mid, hi]
 * @return void
 **/
public static void mergeSort(Comparable[] a,int lo,int mid,int hi){
    int i=lo,j=mid+1,n=lo; //原数组要排的是哪一段就放到预备数组的对应位置，这样复制回去的时候才不会把空元素也复制回去
    while(i<=mid&&j<=hi){
        if(less(a[j],a[i])){
            aux[n++]=a[j++];
        }
        else{
            aux[n++]=a[i++];
        }
    }
    while(i<=mid){
        aux[n++]=a[i++];
    }
    while(j<=hi){
        aux[n++]=a[j++];
    }
    //注意：复制回去的时候一定不能把空位置也复制回去
    for(i=lo;i<=hi;i++){
        a[i]=aux[i];
    }
}

/**
 * @Author haien
 * @Description 分治
 * @Date 2018/10/21
 * @Param [a, lo, hi]
 * @return void
 **/
public static void split(Comparable[] a,int lo,int hi){
    int mid;
    if(lo<hi){
        mid=(lo+hi)/2;
        split(a,lo,mid);
        split(a,mid+1,hi);
        mergeSort(a,lo,mid,hi);
    }
}

应用：2-sum问题——找到一个数组中所有和为0的整数对（假设所有元素均不相同）。这个问题很容易用平方级别解决，但是如果先把数组排序然后用二分查找的话就能降为线性对数级别。

/**
 * @Author haien
 * @Description 统计
 * @Date 2018/10/30
 * @Param [a]
 * @return int
 **/
public static int count(int[] a){
    //归并排序（为二分查找做准备）
    //Arrays.sort(a);
    split(a,0,a.length-1);
    int j=0,count=0;
    for(int i=0;i<a.length-1;i++){
        //找到返回索引，否则返回-1
        j=binarySearch(-a[i],a,i+1,a.length-1); //i+1：从哪里开始找起；a.length-1：到哪里结束
        if(j!=-1) count++;
    }
    return count;
}

在2-sum外面套个循环就可以构建平方对数级别的3-sum解决方案

public static int count(int[] a){
    //归并排序（为二分查找做准备）
    //Arrays.sort(a);
    split(a,0,a.length-1);
    int k=0,count=0;
    for(int i=0;i<a.length-2;i++){
        for(int j=i+1;j<a.length-1;j++) {
            //找到返回索引，否则返回-1
            k = binarySearch(-a[i] - a[j], a, j + 1, a.length - 1);
            if (k != -1) count++;
        }
    }
    return count;
}

代码实例：DataStructure/sort/TwoSum、ThreeSum
堆排序
优先队列
首先介绍优先队列：有的时候不要求元素一定要全部有序，或是不一定要一次就将它们排好序。很多情况下是要收集当前集合的最大几个元素。
例如，一台电脑总是处理正在等待的程序中优先级最高的一个。

优先队列是一种数据结构

/**
 * @Author haien
 * @Description 优先队列：找出数组中最大的M个元素
 *                                         定义一个固定容量的队列，把数组的元素装进去，多了就删掉最小的那个，最后剩下的就是最大的那几个
 *              时间复杂度：NM
 * @Date 2018/10/22
 * @Param
 * @return
 **/
public class PriorityQueue {
    public static void main(String[] args) {
        //打印输入流中最大的M行
        int M=Integer.parseInt(args[0]);
        //新建一个大小为M+,容量必须比M大
        MinPQ<Transaction> pq=new MinPQ<>(M+1);
        //输5行进来
        for(int i=0;i<5;i++){
            //为下一行创建一个元素并放入优先队列
            Scanner in=new Scanner(System.in);
            pq.insert(new Transaction(in.nextLine()));
            //超过容量了
            if(pq.size()>M)
                pq.delMin(); //如果优先队列中的元素超过M+1个则删除其中最小的元素
        }
        //新建一个栈
        Stack<Transaction> stack=new Stack<>();
        while (!pq.isEmpty())
            stack.push(pq.delMin()); //每次都弹出最小的元素进栈
        //输出倒序的事务
        for(Transaction t:stack)
            StdOut.println(t);
    }
}

基于二叉堆的优先队列

二叉堆：在二叉堆的数组中，每个元素要保证大于等于另两个特定位置的元素。
最大堆：父结点大于子结点，根结点是其最大结点，每一层都比下一层所有元素大
最小堆：父结点小于子结点，根结点是其最小结点，每一层都比下一层元素小

基于二叉堆实现的优先队列就是内置数组是按照最大堆的排序形式存放元素的

/**
 * @Author haien
 * @Description 基于二叉堆的优先队列
 *              优点：对于需要大量混杂的插入和删除最大元素的用例来说，能保证在对数时间内完成
 * @Date 2018/10/23
 **/
public class BinaryHeap {
    //泛型数组
    private Comparable[] pq;
    //容量
    private int N;

    /**
     * @Author haien
     * @Description 构造指定容量的优先队列
     * @Date 2018/10/23
     * @Param [maxN]
     * @return
     **/
    public BinaryHeap(int maxN) {
        pq=new Comparable[maxN+1]; //泛型数组，取元素时必须强转
    }

    public BinaryHeap(Comparable[] pq){
        N=pq.length;
        this.pq=(Comparable[])new Object[N+1];
        for(int i=0;i<N;i++){
            this.pq[i+1]=pq[i];
        }
        /*N是最后一个结点的序号，N/2是其父结点，也就是说叶结点都是不用管的，
        因为前面的元素如果是最小的自然会下沉到最底下代替叶结点，
        都不是最小的则说明叶结点已经是最小的几个元素了*/
        for(int k=N/2;k>=1;k--){
            sink(k);
        }
        assert isMaxHeap();
    }

    /**
     * @Author haien
     * @Description 判断队列是否最大堆（即父结点都比子结点大）
     * @Date 2018/10/24
     * @Param []
     * @return boolean
     **/
    private boolean isMaxHeap(){
        return isMaxHeap(1);
    }

    /**
     * @Author haien
     * @Description 判断以k号元素为首的子树是否为最大堆
     * @Date 2018/10/24
     * @Param [k]
     * @return boolean
     **/
    private boolean isMaxHeap(int k){
        //溢出则不存在，不存在判断为是最大堆
        if(k>N) return true;
        int left=k*2;
        int right=k*2+1;
        if(left<=N && less(k,left)) return false;
        if(right<=N && less(k,right)) return false;
        return isMaxHeap(left) && isMaxHeap(right);
    }

    public int size(){
        return N;
    }

    /**
     * @Author haien
     * @Description 数组扩容：重开一个数组，把原数组的元素复制过去，再把该数组的引用赋给原数组
     * @Date 2018/10/24
     * @Param [capacity]
     * @return void
     **/
    private void resize(int capacity){
        assert capacity>N;
        Comparable[] temp=new Comparable[capacity];
        for(int i=1;i<=N;i++){
            temp[i]=pq[i];
        }
        pq=temp;
    }

    public boolean isEmpty(){
        return N==0;
    }

    public boolean isFull(){
        return N+1==pq.length;
    }

    private boolean less(int i, int j){
        return pq[i].compareTo(pq[j])<0;
    }

    private void exch(int i,int j){
        Comparable t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
    }

    /**
     * @Author haien
     * @Description 上浮：堆中出现比父结点大的子结点，令其与父结点交换直到遇到比它大的父结点为止
     * @Date 2018/10/23
     * @Param [k]
     * @return void
     **/
    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k/=2;
        }
    }

    /**
     * @Author haien
     * @Description 下沉：出现比子结点小的父结点，把两子结点中最大者跟它互换直到没有比它大的子结点为止
     * @Date 2018/10/23
     * @Param [k]
     * @return void
     **/
    private void sink(int k){
        int j=k*2;
        while (k < N) {
            //跟最大的子结点交换
            if(j<N&&less(j,j+1)) {
                j++;
            }
            if(less(k,j)){
                exch(k,j);
                k=j;
            }
        }
    }

    public void insert(Comparable v){
        //已满，扩容
        if(isFull()) resize(2*pq.length);
        pq[++N]=v;
        swim(N);
    }

    public Comparable delMax(){
        if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Comparable v=pq[1];
        exch(1,N);
        //防止对象游离
        pq[N--]=null; //其实元素如果是int的话可能不行，不过元素不可能是int，因为int不是类，它不可能实现了Comparable接口
        sink(1);
        return v;
    }
}

索引优先队列

为了方便找到已经存入队列的元素，我们可以在存储的时候顺便传入一个键值作为其索引，要获取该元素的时候依据索引来获取

/**
 * @Author haien
 * @Description 索引优先队列：存放进来的元素都带了个键，方便获取元素；做比较的是元素，实际排序的是键
 *                          开一个数组作为队列存放键，开一个数组存放这些键在队列中的位置，开一个数组存放元素本身
 * @Date 2018/10/24
 **/
public class IndexPriorityQueue {
    //容量
    private int N;
    /**存放键，这才是优先队列主要维护的数组；
     * 按照最大堆排序的是键而不是元素本身，
     * 元素怎么排都可以，只要键有序了找出来的元素就是有序的*/
    private int[] pq; //由于设为了int数组，所以键被限死了是int
    //存放键在pq中的索引，可以根据键找到键在队列中的位置
    private int[] qp;
    //存放元素:键是几就把元素放在第几位
    private Comparable[] value;

    public IndexPriorityQueue(int maxN){
        pq=new int[maxN+1];
        qp=new int[maxN+1]; //所以k为0~N闭区间，至于为什么容量要定为maxN+1就不得而知了
        value=new Comparable[maxN+1];
        for(int i=0;i<=maxN;i++)
            qp[i]=-1;
    }

    private boolean less(int i,int j){
        //比较的是元素的值而不是元素的键
        return value[qp[i]].compareTo(value[qp[j]])<0;
    }

    private void exch(int i,int j){
        int t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
        t=qp[pq[i]];
        qp[pq[i]]=qp[pq[j]];
        qp[pq[j]]=t;
    }

    public boolean isEmpty(){
        return N==0;
    }

    public boolean isFull(){
        return N==pq.length-1;
    }

    public boolean contains(int k){
        return qp[k]!=-1;
    }

    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k,k/2);
            k/=2;
        }
    }

    public void sink(int k){
        while(k*2<=N){
            int j=k*2;
            if(j<N&&less(j,j+1)) j++;
            if(less(j,k)) break;
            exch(k,j);
            k=j;
        }
    }

    public void insert(int k,Comparable v){
        if(contains(k)||isFull()) throw new IllegalArgumentException();
        N++;
        pq[N]=k;
        qp[k]=N;
        value[k]=v;
        swim(N);
    }

    public int delMax(){
        if(isEmpty()) throw new NoSuchElementException();
        int min=pq[1];
        exch(1,N--);
        sink(1);
        qp[min]=-1;
        value[min]=null;
        pq[N+1]=-1;
        //返回最小元素的键
        return min;
    }
}

应用：实现多向归并排序——将多个有序的小数组归并为有序的数组。从命令行读入文件名，将对应文件搞成输入流，每个文件都包含一个字符串，这几个字符串就是有序的小数组了，其中每个字符都是一个元素单位。把它们排成一个有序的字符串并打印。

/**
 * @Author haien
 * @Description 多向归并：用索引优先队列实现；输入多个有序数组，归并为一个有序的大数组
 * @Date 2018/10/25
 **/
public class MultiwayMerge {
    /**
     * @Author haien
     * @Description 多向归并：入参为多个输入流组成的数组，每个输入流都是一个字符串（升序），每个字符串包含的字符是一个元素单位
     * @Date 2018/10/25
     * @Param [streams]
     * @return void
     **/
    public static void merge(In[] streams){
        int N=streams.length;
        //创建一个索引优先队列，它跟IndexPriorityQueue的区别就是顺序相反而已
        IndexMinPQ<String> pq=new IndexMinPQ<>(N);

        //先读取每一个字符串的第一个字符，因为最小的肯定在这里面
        for(int i=0;i<N;i++){
            if(!streams[i].isEmpty())
                //把它在数组中的索引作为键插入队列
                pq.insert(i,streams[i].readString()); //读取下一个单词，以空格为分隔符
        }

        while(!pq.isEmpty()){
            //把目前最小的输出
            StdOut.println(pq.minKey());
            //删掉最小元素并返回其键
            int i=pq.delMin();

            //把最小元素原本所在的字符串的下一个字符插入队列，因为它最可能是第二小的元素，即使不是加入了队列也没事，元素出队的时候队列自然会找最小的那个出来
            if(!streams[i].isEmpty())
                pq.insert(i,streams[i].readString());
        }
    }
    public static void main(String[] args) {
        int N=args.length;
        In[] streams=new In[N];
        for(int i=0;i<N;i++){
            streams[i]=new In(args[i]); //args为文件名数组；输入指定文件
        }
        /**
         * 输入文件m1.txt:A B C F G I I Z
         * m2.txt:B D H P Q Q
         * m3.txt:A B E F J N
         **/
        merge(streams);
    }
}

堆排序

/**
 * @Author haien
 * @Description 堆排序：先把数组排成最大堆，然后把根结点不断跟最后第1,2，……，n交换，最终排成升序数组 
 *              优点：是目前同时能够最优地节省空间和时间的排序方式
 *              时间复杂度：NlgN
 * @Date 2018/10/25
 * @Param [a]
 * @return void
 **/
public static void heapSort(Comparable[] a){
    int n=a.length;
    //将原数组排成最大堆
    for(int k=n/2;k>=1;k--)
        sink(a,k,n);
    /**
     * 将最大堆排成升序数组：让根结点与最后一个结点交换，把交换上来的结点下沉；
     * 让新的根结点跟倒数第二个结点交换，然后下沉；……；
     * 最大的结点不断被交换到最后，最终排序完毕
     **/
    while(n>1){
        exch(a,1,n);
        sink(a,1,n);
    }
}

/**
 * @Author haien
 * @Description 下沉：出现比子结点小的父结点，把两子结点中最大者跟它互换直到没有比它大的子结点为止
 * @Date 2018/10/23
 * @Param [k]
 * @return void
 **/
private static void sink(Comparable[] a,int k,int N){
    int j=k*2;
    while (k < N) {
        //跟最大的子结点交换
        if(j<N&&less(a[j],a[j+1])) {
            j++;
        }
        if(less(k,j)){
            exch(a,k,j);
            k=j;
        }
    }
}

总结

稳定性：除了插入排序和归并排序（因为它们都是从左往右依次排的），其他算法都不具有稳定性。但是稳定性只是针对那些需要相同元素保持相对顺序的应用才另外考虑的，大部分时候都可以忽略。
实践证明，快速排序是最快的、最佳的选择。
但如果稳定性很重要而空间又不是问题，那么归并排序是最好的。
有了SortCompare这样的工具，能够更仔细地比较
以上排序算法不能排列基本数据，基本数据应该实现属于自己的只操作某种数据类型的排序算法，而不能装箱之后继续用上面的算法，因为使用引用来访问和交换数据比直接操作数据本身要耗费很多时间。
应用
java.util.Arrays.sort()对基本数据采用（三向切分）快速排序，对引用类型采用保证稳定性的归并排序
找出重复元素：小数组的话，用平方级别的算法将左右元素互相比较一遍；大数组，先排序，再记录连续出现的元素即可。

查找中位数

/**
 * @Author haien
 * @Description 找到数组中排行第K的元素
 * @Date 2018/10/25
 * @Param [a]
 * @return java.lang.Comparable
 **/
public Comparable findRankK(Comparable[] a,int k){
    //将数组重新排序，可避免最坏情况
    StdRandom.shuffle(a);
    int lo=0,hi=a.length-1,j;
    while(lo<hi){
        j=partition(a,lo,hi);
        if(j==k) return a[j];
        if(j<k) hi=j-1;
        if(j>k) lo=j+1;
    }
    return a[k];
}

/**
 * @Author haien
 * @Description 以lo（排头元素）为基数，i从头扫描，发现比lo的元素停下，调动j从尾开始扫描，发现小的即与i交换位置
 *              直到两指针相遇结束
 * @Date 2018/10/21
 * @Param [a, lo, hi]
 * @return int
 **/
public static int partition(Comparable[]a,int lo,int hi){
    int i=lo,j=hi+1;
    while(true){
        while (less(a[++i],a[lo])) //i从头开始扫描，发现大于基数的元素停下
            if(i>=hi) break; //扫到尾结束
        while (less(a[lo],a[--j])) //j从尾开始扫，发现小于基数的元素停下
            if(j<=lo) break; //扫到头结束
        if(i>=j) break; //跳出循环的原因如果是因为扫到头、尾或相遇则结束
        exch(a,i,j); //否则就是该交换元素了
    }
    exch(a,lo,j); //算法没写好可能lo会被换到j所指的末尾上去
    return j; //把相遇点返回去
}

代码实例

DataStructure/sort/MySort

Java数据结构之排序

Comparable接口

选择排序

插入排序

快速排序

希尔排序

归并排序

堆排序

优先队列

基于二叉堆的优先队列

索引优先队列

堆排序

总结

应用

代码实例

谢谢大爷~