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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了常用排序算法总结（基于算法 第四版），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5424字，纯文字阅读大概需要8分钟。

内容图文

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]时

比较区间为：|MTLP|SESH|LXOE|EARL|

h=1，插入排序

执行顺序

 

常用排序算法总结（基于算法 第四版） - 文章图片

 

可视化

常用排序算法总结（基于算法 第四版） - 文章图片

 

 




内容总结

以上是互联网集市为您收集整理的常用排序算法总结（基于算法 第四版）全部内容，希望文章能够帮你解决常用排序算法总结（基于算法 第四版）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/646597.html

来源：【匿名】