铭记:

源码下载

插入排序

1、插入排序思想

把 n 个待排序的元素看成为一个有序表和无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表

2、分析插入排序 {4, 3, 2, 1}，正序

从数组下标 index = 1 开始，只需要比较 arr.length - 1 次

第1趟 记录当前值： index = 1，temp = 3

• 使用temp值逐一与 index-- 的值来比较，3 小于 4则移动下标为index-- 的值到 下标为 index， {4, 4, 2, 1}
• 如果 index = 0，那么就把temp赋值到0的位置 {3, 4, 2, 1}

第2趟 记录当前值： index = 2，temp = 2

• 1、使用temp值逐一与 index-- 的值来比较，2 小于 4则移动下标为index-- 的值到 下标为 index， {3, 4, 4, 1}
• 2、移动后要是index = index - 1
• 3、判断index是否大于 0，如果大于0，继续第1步
• 4、使用temp值逐一与 index-- 的值来比较，2 小于 3则移动下标为index-- 的值到 下标为 index， {3, 3, 4, 1}
• 5、移动后要是index = index - 1，测试index=0
• 6、如果 index = 0，那么就把temp赋值到0的位置 {2, 3, 4, 1}

第3趟 记录当前值： index = 3，temp = 1

• 继续上面的逻辑，移动的过程可以通过 while语句实现

实例代码

package com.raven.alg.s6sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 插入排序 arr【101, 43, 119, 1】
 * 插入排序的思路：
 * 在遍历的时候，没遍历一趟（index）都要确保 0~index 数据是有序。从下标1开始，因为第一个元素肯定是有序的（101）
 * 1、开始遍历数组 arr，从下标 1 开始
 * 2、比较 下标 1 的元素值(43)，与 小于 1 下标的值一一比较，如果大于则移动 arr【101, 101, 119, 1】
 * 3、如果 下标 等于 0 时，则把 下标为 1 的值 放置到下标 0 的位置 arr【43, 101, 119, 1】
 * 4、temp = 43
 * 5、上述的移动使用 while 来实现，条件为：while(index > 0 && arr[index - 1] > 43) { index-- }
 * 6、如果没有移动 index = i ，表示不需要移动，位置合适
 */
public class InsertionSort {


    public static void main(String[] args) {
//        Integer[] arr = {17, 3, 25, 14, 20, 9};
//        Integer[] arr = {101, 43, 119, 1};
//        Integer[] arr = {3, 1, 5, 2, -2};
//        Integer[] arr = {1, 2, 3, 4, 6};
//        Integer[] sort = sort(arr);
//        System.out.println("args = " + Arrays.deepToString(sort));


        // 十万个数据
        Integer[] arr = new Integer[100000];
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            arr[i] = random.nextInt(80000);
        }
        long startTime = System.currentTimeMillis();
        sort(arr);
        long endTime = System.currentTimeMillis();

        //冒泡排序10万个数据耗时 = 46334 49523 52203 40252
        //优化冒泡排序10万个数据耗时 = 43635 41963 41150
        //选择排序10万个数据耗时 = 13355 16778 13461
        //优化选择排序10万个数据耗时 = 18096 18548 15211 15897
        //插入排序10万个数据耗时 = 28481 27034 27254 27670
        System.out.println("排序10万个数据耗时 = " + (endTime - startTime));
    }


    public static Integer[] sort(Integer[] arr) {
        // 保存新增数据
        Integer index = 0;
        Integer temp = 0;
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i];
            index = i;
            // 给 sort 排序
            while (index > 0 && arr[index - 1] > temp) {
                arr[index] = arr[index - 1];
                index--;
            }
            if (index != i) {
                arr[index] = temp;
            }
//            System.out.println(index + " 第 " + i + " 次交换后" + Arrays.toString(arr));
        }
        return arr;
    }
}