常用排序算法总结（基于算法第四版）

shawsun

2020-01-12

1.初级排序算法

1.1我们关注的主要对象为重拍数组元素的算法。，其中每个元素有个主键，将主键按照某种方式排列。在java中元素通常都是对象，对主键描述往往通过comparable接口。

一般排序模板

public class Example{
    public static void sort(Comparable[] a)
        {.......}
    private static boolean less(Comparable v,Comparable w)
        { return v.compareTo(w)<0;}
    private static void each(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(Comparable[] 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);         
        } 
}

在java中一般是靠这个比较，即V<W返回负值（-1），返回0;V=W,;V>W,返回正值（1）

private static boolean less(Comparable v,Comparable w)
        { return v.compareTo(w)<0;}

1.2 Selection选择排序

即先找出最小元素调整位置，往复。

特点：

对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换，运行时间和输入无关，数据移动最少

public class Selection {
    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i; j < n; j++)
                if (less(a[min], a[i])) min = j;
            exch(a, i, min);
        }
    }


    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 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();

    }


    private static boolean isSorted(Comparable[] 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 = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

其中比较交换是

for (int j = i; j < n; j++)
                if (less(a[min], a[i])) min = j;
            exch(a, i, min);执行顺序1.3 Insertion(插入排序)对随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~N^2/4比较及~N^2/4次交换。最坏情况需要~N^2/2比较及~N^2/2次交换，最好为N-1次比较及0次交换

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


    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 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();

    }


    private static boolean isSorted(Comparable[] 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 = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

插入排序需要的交换操作和数组倒置数量相同，需要比较次数大于等于倒置数量，小于等于倒置数量加上数组大小再减一。

执行顺序

常用排序算法总结（基于算法第四版）

1.4比较排序算法

public class sortCompare {
public static double time(String alg, Double[] a) {
        Stopwatch timer = new Stopwatch();
        if (alg.equals("Insersion")) Insertion.sort(a);
        if (alg.equals("Selection")) Selection.sort(a);        //其他排序。。。
        else throw new IllegalArgumentException("Invalid algorithm: " + alg);
        return timer.elapsedTime();
    }

    public static double timeRandomInput(String alg, int N, int T) {
        //
        double total = 0.0;
        Double[] a = new Double[N];
        for (int t = 0; t < T; t++) {
            for (int i = 0; i < N; i++)
                a[i] = StdRandom.uniform();
            total += time(alg, a);
        }
        return total;
    }

    public static void main(String[] args) {
        String alg1 = args[0];
        String alg2 = args[1];
        int N = Integer.parseInt(args[2]);
        int T = Integer.parseInt(args[3]);
        double t1 = timeRandomInput(alg1, N, T);
        double t2 = timeRandomInput(alg2, N, T);
        StdOut.printf("For %d random Double\n  %s id", N, alg1);
        StdOut.printf(" %.1f times faster than %s\\n", t2 / t1, alg2);

    }
}

1.5 Shell排序

基于插入排序的改进。当极值位于极端位置时，需要大量时间。

h有序数组

常用排序算法总结（基于算法第四版）

假设存在任意间隔h的元素为有序的，那么可以节省时间。

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


    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 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();

    }


    private static boolean isSorted(Comparable[] 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 = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

分析h,j,i,a[x]变化趋势

SHELLSORTEXAMPLE

h=13时 j=[h,2h]

比较区间为PS|LH|EE|

h=4时，i~16，j=[h,2h] 比较一次 j=[2h,3h]比较两次 j=[3h,4h]比较三次

j=[h,2h]时

比较区间为:|LP|SH|OE|RL|

j=[2h,3h]时

比较区间为：|TLP|ESH|XOE|ARL|

j=[3h,4h]时

h=1，插入排序

执行顺序