插入算法改进-排序-数据结构与算法

文章目录

    • 1 前言
    • 2 性能结论及证明
    • 3 改进插入排序算法实现
    • 4 备注

1 前言

关于插入排序的概述、原理及通用实现,这里不再赘述,可以参考之前的博文插入排序-排序-算法。这里主要参考算法第4版,给出插入排序的算法性能、证明以及根据建议做的改进。

2 性能结论及证明

命题:对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要 N 2 4 \frac{N^2}4 4N2次比较以及 N 2 4 \frac{N^2}4 4N2次交换。最坏的情况下需要 N 2 2 \frac{N^2}{2} 2N2次比较和 N 2 2 \frac{N^2}{2} 2N2次交换,最好的情况下需要 N − 1 N-1 N1次比较和0次交换。

证明:根据代码实现分析,最好的情况就是数组有序,只需要比较 N − 1 N-1 N1次,交换0次;最坏的情况是数组为逆序,i从1开始,第一次循环比较1次,交换1次 。 i = 2 i=2 i=2时,比较2次,交换2次,知 i = N − 1 i=N-1 i=N1。交换次数和比较次数相等,交换次数=比较次数 = 1 + 2 + … + N − 1 ≈ N 2 2 =1+2+\ldots+{N-1}\approx\frac{N^2}{2} =1+2++N12N2。(忽略低次幂项)

​ 倒置指的是数组中两个顺序颠倒的元素。不如EXAMPLE中有11对倒置:E-A、X-A、X-M、…。

命题:插入排序需要的交换次数和数组中倒置的数量相同,需要的比较次数大于等于倒置的数量,小于等于倒置的数量加上数组大小在减一。

证明:每次交换改变2个倒置元素的位置,相当于减少了一堆倒置,当倒置数量为0时,排序完成。每次交换对应一次比较,且1到 N − 1 N-1 N1之间的每个i都可能需要一次额外的比较。

3 改进插入排序算法实现

​ 要提高插入排序速度,只需要在内循环中将较大的元素右移而不总是交换2个元素,这样访问数组的次数就能减半。实现代码如下:

public static void sortImprove(Comparable[] a) {

        for (int i = 1; i < a.length; i++) {
            // 保存当前元素的值
            Comparable k = a[i];
            for (int j = i; j > 0; j--) {
                // 当前元素逆序和有序元素依次比较
                if (compare(a[j - 1], k)) {
                    // 当前元素小于等于前面元素,把较大的元素右移
                    a[j] = a[j-1];
                    // 如果比较到有序元素最左端,当前元素还是最小的,则把当前元素放置索引为0的位置,结束内循环
                    if (j == 1) {
                        a[0] = k;
                        break;
                    }
                } else {
                    // 当前元素大于要比较的元素,吧当前元素插入当前位置(之前较大元素已经右移)
                    if (j != i) {
                        a[j] = k;
                    }
                    break;
                }
            }

        }
    }

性能比较:

性质:对于随机排序的无重复主键的数组,插入排序和优化后的插入排序的运行时间是平方级别,两者之比应该是一个较小的常数。

验证:使用SortCompare类来测试,

SortCompare源代码:

package com.gaogzhen.algorithm.test;

import com.gaogzhen.algorithm.sort.*;
import edu.princeton.cs.algs4.Heap;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

/**
 * 比较2个算法用时
 */
public class SortCompare {

    /**
     * 计算某个算法用时
     * @param alg       算法名称
     * @param a         随机数组
     * @return          时间
     */
    public static double time(String alg, Double[] a) {
        Stopwatch timer = new Stopwatch();
        if (alg.equals("Insertion")) Insertion.sort(a);
        if (alg.equals("InsertionImprove")) Insertion.sortImprove(a);
        if (alg.equals("Selection")) Selection.sort(a);
        if (alg.equals("Shell")) Shell.sort(a);
        if (alg.equals("Merge")) Merge.sort(a);
        if (alg.equals("Quick")) Quick.sort(a);
        if (alg.equals("Heap")) Heap.sort(a);
        return timer.elapsedTime();
    }

    /**
     * 测试T次长度为N的数组排序用时
     * @param alg      算法名称
     * @param N        数组长度
     * @param T        测试次数
     * @return          总用时
     */
    public static double timeRandomInput(String alg, int N, int T) {
        // 使用算法alg将T个长度为N的数组排序
        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]);

        // 算法1总时间
        double t1 = timeRandomInput(alg1, N, T);
        // 算法2总时间
        double t2 = timeRandomInput(alg2, N, T);

        StdOut.printf("For %d random Doubles and %d times compare\n %s is ", N, T, alg1);
        StdOut.printf("%.1f times faster then %s\n", t2/t1, alg2);
    }
}


// 命令行输入
Insertion InsertionImprove 1000 100

SortCompare类源代码在选择排序和插入排序及比较-排序-算法第4版 以及文章最后面的源代码仓库中都有,测试结果如下:

For 1000 random Doubles and 100 times compare
 Insertion is 0.8 times faster then InsertionImprove

4 备注

  • 参考
    • 书籍:[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法:第4版[M].北京:人民邮电出版社,2012.10
    • 视频:[2]黑马程序员.Java数据结构与java算法[VD/OL].上海:B站,2022
      • 视频地址:https://www.bilibili.com/video/BV1iJ411E7xW

QQ:806797785

仓库地址:https://gitee.com/gaogzhen/algorithm

你可能感兴趣的