插入排序

概述

插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。

插入排序是一种简单直观的排序算法，其基本思想是将未排序的元素逐个插入到已排序序列中的正确位置，从而构建有序的序列。

插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找

插入排序的时间复杂度为 O(n^2)，但是在处理小型数组或基本有序的数组时，插入排序的性能往往比其他复杂的排序算法更好。此外，插入排序是稳定的排序算法，即具有相等值的元素在排序后的相对位置不会改变。

步骤

插入排序的过程如下：

1. 从第一个元素开始，认为该元素已经是有序序列。

2. 取出下一个元素，将其与已排序的元素从右到左依次比较。

3. 如果已排序的元素大于当前元素，则将已排序的元素后移一位，继续比较前一个已排序的元素。

4. 重复步骤 3，直到找到一个已排序的元素小于或等于当前元素，或者到达已排序序列的起始位置。

5. 将当前元素插入到已排序序列中找到的位置后面。

6. 重复步骤 2 到 5，直到所有元素都被插入到有序序列中。

插入排序每次将一个元素插入到已排序序列中，并将该元素放置在正确的位置上。通过逐步扩大已排序的部分，最终完成整个数组的排序。

将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

N的范围：0~最大索引

代码示例

需求：采用插入排序将下列数据进行排序，数据如下{3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};

例如：

package text.text02;

/*
插入排序：
   插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。

插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找


 */
public class text13A {
    public static void main(String[] args) {
        int[] arr = {3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};
        //定义一个变量记录无序序列的起始索引
        int startIndex = -1;
        //遍历数组，找到无序序列的起始索引
        for (int i = 0; i < arr.length - 1; i++) {
            //表明前i-1个数和第i+1个数都小于第i个数，说明前i个数都是有序的，第i+1个数以后都是无序的
            if (arr[i] > arr[i + 1]) {
                //将无序序列的起始索引赋值给startIndex
                startIndex = i + 1;
                break;
            }
        }
        //调用method1方法遍历数组，将无序序列中的数据插入到有序序列中(顺序查找/基本查找)
        int[] arr1 = method1(arr, startIndex);
        //调用method2方法遍历数组，将无序序列中的数据插入到有序序列中(折半查找/二分查找)
        int[] arr2 = method2(arr, startIndex);

        //调用printfArray方法遍历输出数组数据
        System.out.println("这是基本查找/顺序查找的方法：");
        printfArray(arr1);     //2	3	4	5	15	19	23	23	23	26	27	36	36	37	38	40	43	44	46	47	47	48	50

        System.out.println();  //换行

        System.out.println("这是折半查找/二分查找的方法：");
        printfArray(arr2);    //2	3	4	5	15	19	23	23	23	26	27	36	36	37	38	40	43	44	46	47	47	48	50
    }

    //遍历数组方法1，将无序序列中的数据插入到有序序列中(顺序查找/基本查找)
    public static int[] method1(int[] arr, int startIndex) {
        for (int i = startIndex; i < arr.length; i++) {
            //定义一个变量记录i的值（因为后面要更改j的值（j--），如果直接更改i，则循环永远不到达到i < arr.length）
            int j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {    //j表示无序序列的其实索引，j-1表示有序序列的最后索引
                //交换数据
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }
        return arr;
    }

    //遍历数组方法2，将无序序列中的数据插入到有序序列中(折半查找/二分查找)
    public static int[] method2(int[] arr, int startIndex) {
        //利用循环交换数组元素进行排序
        for (int i = startIndex; i < arr.length; i++) {
            //调用judgeIndex方法获取要插入元素的位置
            int index = judgeIndex(arr, i);
            //定义一个变量记录要插入的数
            int number = arr[i];
            //利用循环将已排序部分中要插入位置之后的元素向右移动，为待插入元素腾出空间（从 i1 开始向左遍历，将每个元素向右移动一位，直到达到插入位置 index。）
            for (int i1 = i; i1 > index; i1--) {
                arr[i1] = arr[i1 - 1];
            }
            //将记录要插入的值的变量赋值给要插入的位置
            arr[index] = number;
        }
        return arr;
    }

    //定义方法用来判断要插入的数的位置
    public static int judgeIndex(int[] arr, int startIndex) {
        //定义变量记录已经排序的数中的起始索引
        int min = 0;
        //定义变量记录已经排序的数中的结束索引
        int max = startIndex - 1;
        //利用循环找到要插入的位置
        while (min <= max) {
            //获取已排序的数的中间索引
            int mid = (min + max) / 2;
            //如果中间索引所对应的数等于要插入得数
            if (arr[mid] == arr[startIndex]) {
                return mid;
            }
            //如果中间索引所对应的数小于要插入得数
            if (arr[mid] < arr[startIndex]) {
                min = mid + 1;
            }
            //如果中间索引所对应的数大于要插入得数
            if (arr[mid] > arr[startIndex]) {
                max = mid - 1;
            }
        }
        //当循环结束时，“min” 指针指向了插入位置的右侧。在每次二分查找的过程中，如果目标元素小于当前中间元素，那么 “max” 指针会更新为 “mid - 1”，如果目标元素大于当前中间元素，那么 “min” 指针会更新为 “mid + 1”。最终当满足 “min > max” 时，说明目标元素应该插入的位置就是 “min” 指向的位置。因此，当二分查找未找到目标元素时，插入位置就是 “min” 所指向的位置，所以返回 “min”。如果找到目标元素，那么也返回该元素在数组中的位置。
        return min;
    }

    //遍历输出数组数据
    public static void printfArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

输出结果