插入排序及其优化

作者: TinyDolphin | 来源:发表于2017-11-04 18:02 被阅读0次

插入排序及其优化
插入排序及其简单优化
c算法O(n)^2(一)
插入排序算法及其优化（Rust）
对于基础排序算法的简要总结
数据结构与算法---排序篇
chapter 11
排序算法（二）：希尔排序
MapReduce过程详解及其性能优化
希尔排序

基本思路

正如生活中整理扑克的方法：一张一张的来，将每一张扑克插入到其他已经有序的扑克中的适当位置。

Q：计算机中如何实现？
A：为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。（这里我们用交换代替移动）

Q：与选择排序的相同点？
A：当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。当索引到达数组的右端时，数组排序就完成了。

Q：与选择排序的不同点？
A：插入排序所需的时间取决于输入中元素的初始顺序。速度：元素已经有序（或接近有序）的数组 > 随机顺序的数组

运行轨迹

插入排序运行轨迹

代码实现

根据排序算法类的模板实现插入排序（提醒：点蓝字查看详情）

import java.util.Random;

/**
 * 插入排序
 *
 * @author TinyDolphin
 *         2017/11/1 14:20.
 */
public class Insertion {
    /**
     * 排序实现
     *
     * @param arr 待排序数组
     */
    public static void sort(Comparable[] arr) {
        //排序代码
        int length = arr.length;
        for (int indexI = 1; indexI < length; indexI++) {
            for (int indexJ = indexI; indexJ > 0 && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
                exch(arr, indexJ, indexJ - 1);
            }
        }
    }

    /**
     * 比较两个元素的大小
     *
     * @param comparableA 待比较元素A
     * @param comparableB 待比较元素B
     * @return 若 A < B,返回 true,否则返回 false
     */
    private static boolean less(Comparable comparableA, Comparable comparableB) {
        return comparableA.compareTo(comparableB) < 0;
    }

    /**
     * 将两个元素交换位置
     *
     * @param arr    待交换元素所在的数组
     * @param indexI 第一个元素索引
     * @param indexJ 第二个元素索引
     */
    private static void exch(Comparable[] arr, int indexI, int indexJ) {
        Comparable temp = arr[indexI];
        arr[indexI] = arr[indexJ];
        arr[indexJ] = temp;
    }

    /**
     * 打印数组的内容
     *
     * @param arr 待打印的数组
     */
    private static void show(Comparable[] arr) {
        for (int index = 0; index < arr.length; index++) {
            System.out.print(arr[index] + " ");
        }
        System.out.println();
    }

    /**
     * 判断数组是否有序
     *
     * @param arr 待判断数组
     * @return 若数组有序，返回 true，否则返回 false
     */
    public static boolean isSort(Comparable[] arr) {
        for (int index = 1; index < arr.length; index++) {
            if (less(arr[index], arr[index - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[100000];
        for (int index = 0; index < 100000; index++) {
            arr[index] = new Random().nextInt(100000) + 1;
        }
        long start = System.currentTimeMillis();
        sort(arr);      //83001ms
        long end = System.currentTimeMillis();
        System.out.println("耗费时间：" + (end - start));
        assert isSort(arr);
    }
}

性能分析

对于随机排列的长度为 N 且主键不重复的数组
平均情况下：~N²/4 次比较、~N²/4 次交换、O(N^2)
最坏的情况：~N²/2 次比较、~N²/2 次交换、O(N^2)
最好的情况：N-1 次比较、0次交换（线性级别）（当倒置的数量很少时，比其他的排序算法都要快）（对于部分有序的很有效）、O(N)

Q：何为倒置？
A：数组中的两个顺序颠倒的元素，如：3 2 5 1 4 中，有 5 对倒置：3-2、3-1、2-1、5-1、5-4。

Q：何为部分有序？
A：数组中倒置的数量小于数组大小的某个倍数。

插入排序需要的交换次数 = 数组中倒置的数量
倒置数量 <= 需要的比较次数 <= 倒置的数量 + 数组的大小 - 1

优化方案

NO.1

原有方案：在内循环中，总是交换两个元素。
优化方案：进行了预处理操作，并在内循环中，总是将较大的元素向右移动。（这样访问数组的次数就能减半）

优化之后的运行轨迹

优化之后的插入排序

优化之后的代码

public static void sortPlus(Comparable[] arr) {
        int length = arr.length;
        int exchanges = 0; //交换次数
        // 预处理：若 arr[index] < arr[index - 1]，则交换两数
        for (int index = length - 1; index > 0; index--) {
            if (less(arr[index], arr[index - 1])) {
                exch(arr, index, index - 1);
                exchanges++;
            }
        }
        // 若交换次数为0（即数组有序），则无需进行下一步排序。
        if (exchanges == 0) return;
        // 若有交换次数，表明目前的数组无序。
        for (int indexI = 2; indexI < length; indexI++) {
            Comparable temp = arr[indexI];  //记录一下 arr[indexI] 的值
            int indexJ = indexI;            // indexI 的代替品
            // 若 indexJ 的前一位元素小于 temp，则将小于 temp 的元素向右移动一位
            while (less(temp, arr[indexJ - 1])) {
                arr[indexJ] = arr[indexJ - 1];
                indexJ--;
            }
            arr[indexJ] = temp; // 将记录的值放在 indexJ 的位置上
        }
    }

NO.2

优化方案：进行了预处理操作，并查找插入位置时使用二分查找的方式

优化之后的代码

    public static void sortPlus2(Comparable[] arr) {
        int length = arr.length;
        int exchanges = 0; //交换次数
        //若 arr[index] < arr[index - 1]，则交换两数
        for (int index = length - 1; index > 0; index--) {
            if (less(arr[index], arr[index - 1])) {
                exch(arr, index, index - 1);
                exchanges++;
            }
        }
        //若交换次数为0（即数组有序），则无需进行下一步排序。
        if (exchanges == 0) return;
        //若有交换次数，表明目前的数组无序。
        for (int indexI = 1; indexI < length; indexI++) {
            Comparable key = arr[indexI];  //记录一下arr[indexI]的值
            int left = 0;
            int right = indexI - 1;
            // 二分查找寻找插入点
            while (left <= right) {
                // ①：a >> n 相当于 a/2^n ②：此处有坑，不要图快用加法，会溢出。③、注意 >> 的优先级别低于 + ,也就是说先执行 + ，在执行 >>
                int middle = left + ((right - left) >> 1);
                if (less(key, arr[middle])) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            // 将插入点以后的所有元素，后移一位
            for (int indexJ = indexI - 1; indexJ >= left; indexJ--) {
                arr[indexJ + 1] = arr[indexJ];
            }
            // 插入元素到插入点
            arr[left] = key;
        }
    }

测试代码

【高效复制数组的方法】，提示：点击蓝色字体查看方法详情。

    public static void main(String[] args) {
        int length = 100000;// 十万数量级别
        Integer[] arr = new Integer[length];
        Integer[] arr2 = new Integer[length];
        Integer[] arr3 = new Integer[length];
        for (int index = 0; index < length; index++) {
            arr[index] = new Random().nextInt(length) + 1;
        }
        //高效复制数组的方法
        System.arraycopy(arr, 0, arr2, 0, arr.length);
        System.arraycopy(arr, 0, arr3, 0, arr.length);

        long start = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗费时间：" + (end - start) + "ms");
        assert isSort(arr);

        start = System.currentTimeMillis();
        sortPlus(arr2);
        end = System.currentTimeMillis();
        System.out.println("耗费时间：" + (end - start) + "ms");
        assert isSort(arr2);

        start = System.currentTimeMillis();
        sortPlus2(arr3);
        end = System.currentTimeMillis();
        System.out.println("耗费时间：" + (end - start) + "ms");
        assert isSort(arr3);
    }