排序算法 - 简书

本篇文章参考《算法(第四版)》以下为文章的整体结构，方便浏览，也方便我以后回忆。

排序.png

初级排序算法

游戏规则

我们以数组为源数据，将他们按照顺序排列好。以下为对应算法的模板。
排序算法类的模板

public class Example
{
    public static void sort(Comparable[] a){}
    private static boolean less(Comparable v, Comparable w)
    {return v.compareTo() <0;}
    private static void exch(Comparable[] a, int i, int j)
    {Comparable t = a[i]; a[i] = a[j];a[j]= t;}
    private static void show(Comparable[] a)
    {
        for(int i = 0; i< a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }
    public static boolean isSorted(Comarable[] a)
    {
        for(int i = 1; i< a.length; i++)
            if(less(a[i], a[i-1])) return false;
        return true;
    }
    public static void main(String[] args){
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

在大多数情况下，排序的代码智慧通过两个方法操作数据：less() 方法对元素进行比较，exch() 方法将元素交换位置。isSorted()判断是否完成排序。

额外的内存使用 ：排序算法的额外内存和运行时间同等重要。排序算法可以分成两类，除了函数调用所需要的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法。

选择排序

public class Selection
{
    public static void sort(Comparable[] a)
    {  // 将a[] 按升序排列
        int N = a.length;    // 数组长度
        for(int i = 0; i< N; i++){  // 将a[i] 和 a[i+1.. N] 中最小元素交换
            int min = i;    // 最小元素的索引
            for(int j = i+1; j< N; j++)
                if(less(a[j], a[min])) min =j;
            exch(a,i, min);
        }
    }
}

总的来说：排序算法是一种很容易理解和实现的简单排序算法，它有两个很鲜明的特点。

运行时间和输入无关
数据一定是最少的。

命题A：对于长度为N 的数组，选择排序需要大约 N^2 /2 次比较和 N 次交换。

插入排序

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i = 1; i< N; i++)
        {
            for(int j = i; j > 0 && less(a[j], a[j-1]); j--)
                exch(a,j,j-1);
        }
    }
}

下面是几种典型的部分有序的数组：

数组中每个元素距离它的最终位置都不远
一个有序的数组接一个小数组
数组中有几个元素的位置不确定
插入排序对这样的数组很有效，而选择排序则不然。事实上，当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。

命题B 对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要 ~ N^2 /4 次比较以及 ~ N^2 /4 次交换。最坏情况下需要 ~N^2/2 次比较和 ~ N^2/2 最好的情况需要 N-1 次比较和0 次交换。
插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

比较两个算法

对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常熟。

希尔排序

希尔排序的思想是一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成一个数组。

public class Shell
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h+1; 
        while(h >= 1)
        {
            for(int i = h; i<N; i++)
            {
                for(int j = i; j>= h && less(a[j],a[j-h]; j-= h))
                    exch(a,i,j-h);
            }
            h = h/3;
        }
    }
}

归并排序

要将一个数组排序，可以先将它分成两半分别排序，然后将结果归并起来。

自顶向下的归并排序

public class Merge{
    private staitc Comparable[] aux;              //归并所需的辅助数组
    public static void sort(Comparable[] a){
        aux = new Comparable[a.kength];           //一次性分配空间
        sort(a,0,a.length - 1);
    }
    
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int mid = lo +(hi - lo)/2;
        sort(a,lo,mid);               //将左半边排序
        sort(a, mid+1, hi);           //将右半边排序
        merge(a,lo,mid,hi);           //归并结果
    }
}

命题F：对于长度为N的任意数组，自顶向下的归并排序需要 1/2N lg(N) 至 Nlg(N)次比较。

命题G：对于长度为N的任意数组，自顶向下的归并排序最多需要访问数组 6NlgN 次。

对小规模子数组使用插入排序
测试数组是否已经有序
不将元素复制到辅助数组

自底向上的归并排序

public class MergeBU{
    private static Comparable[] aux;
    public static void sort(Comparable[] a){
        //进行lgN 次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz < N; sz = sz+sz)           //sz 子数组大小
            for(int lo = 0; lo < N-sz; lo += sz+sz)   //lo: 子数组索引
                merge(a,lo,lo+sz-1, Math.min(lo+sz+sz+1, N-1));
    }
}

命题H：对于长度为 N 的任意数组，自底向下的归并排序需要 1/2 NlgN 至 NlgN 次比较，最多访问数组 6NlgN 次。

命题I：没有任何基于比较的算法能够保证使用少于 lg(N!) ~ NlgN 次比较长度将问 N 的数组排序。

排序算法的复杂度

快速排序

基本算法

public class Quick{
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a);         //消除对输入的依赖
        sort(a,0, a.length -1);
    }
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int j = partition(a, lo, hi);   //切分
        sort(a, lo, j-1);               //将左半部分
        sort(a, j+1, hi);               //将右半部分
    }
}

// 快速排序的切分
private static int partition(Comparable[] a, int lo, int hi){
    int i = lo, j = hi+1;        //左右扫描指针
    Comparable v = a[lo];        // 切分元素
    while(true){                 // 扫描左右，检查扫描是否结束并交换文件
        while(less(a[++i],v)) if(i == hi) break;
        while(less(v,a[--j])) if(j == lo) break;
        if(i>= j) break;
        exch(a,i,j);
    }
    exch(a,lo,j);              //将 v = a[j] 放入正确的位置
    return j;
}

性能特点

命题K：将长度为 N 的无重复数组排序，快速排序平均需要 ~2NlnN次比较

命题L：快速排序最多约 N^2 次比较，但是随机打乱数组能够预防这种情况。

算法改进

切换到插入排序
三取样切分

public class Quick2way{
    private 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++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt+1, hi);
    }
}

命题M：不存在任何基于比较的排序算法能够保证在 NH-N 次比较之内将 N 个元素排序，其中H 为由主键值出现频率定义的香农信息量。

命题N：对于大小为 N 的数组，三向切分的快速排序需要~(2ln2)NH次比较。其中H 为由主键值出现频率定义的香农信息量。

熵最优的排序

优先队列

API
初级实现
- 数组实现（无序）
- 数组实现（有序）
- 链表表示法
堆的定义

定义：当一棵二叉树的每个节点都大于等于它的两个子结点时，它被成为堆有序。

堆的算法

由下至上的堆有序化（上浮）

由上至下的堆有序化（下沉）

public class MaxPQ<Key extends Comparable<key>>{
    private Key[] pd;
    private int N = 0;
    public MaxPQ(int maxN){
        pq = (key[]) new Comparable[maxN+1];
    }
    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }
    public void insert(Key v){
        pq[++N] = v;
        swim(N);
    }
    public Key delMax(){
        Key max = pq[1];      //从根结点得到最大元素
        exch(1,N--);          //将其和最后一个结点交换
        pq[N+1] = null;       // 防止越界
        return max;           // 恢复堆的有序性
    }
}

命题Q：对于一个含有N 个元素的基于堆的优先队列，插入元素操作只需要不超过（lgN+1）次比较，删除最大元素的操作需要不超过 2lgN 次比较。

堆排序

    public static void sort(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);
    }
}

堆的构造
下沉排序

命题 S：将N个元素排序，堆排序只需要少于（2NlgN+2N）次比较。