一、插入排序（InsertSort）

插入排序从第二个数开始，拿出第二个数进行向前插入排序，一直到最后一个数向前做插入排序。算法稳定。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。最好的时间复杂度是O(n)，最坏也就是平均是O(n^2)

 

二、图解

对于一串数字（3，5，2，1，4，10）进行插入从小到大排序，如下图演示

 





 

三、算法分析

    /**
     * 插入排序
     * 1、确定插入排序的数，从第二个开始选择
     * 2、选择插入排序的数，保存为num
     * 3、计算num前一个数的索引
     * 4、进行检查，如果num小于前面的数，则将前一个数往后移，若比前一个数大，则结束此次循环
     * 5、结束时的位置保存num
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //选择插入排序的数，保存为num
            int num = arr[i];

            //计算num前一个数的索引
            int preIndex = i - 1;

            for (; preIndex >= 0; preIndex--) {
                //进行检查，如果num小于前面的数，则将前一个数往后移，若比前一个数大，则结束此次循环
                if (num < arr[preIndex])
                    arr[preIndex + 1] = arr[preIndex];
                else
                    break;
            }
            //结束时的位置保存num
            if (num != arr[i])
                arr[preIndex + 1] = num;
        }

 

四、算法实现

package com.arithmetic.sort;

/**
 * @Description
 * 功能：实现插入排序
 * 从第二个数开始，拿出第二个数进行向前插入排序，一直到拿到最后一个数向前做插入排序
 * 时间复杂度O(n^2)；空间复杂度O(1)；稳定；算法复杂度最好O(n),不需要加条件实现，最坏情况是O(n^2)
 * @Author xuexue
 * @Date 2019/11/9 22:25
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arrs = new int[]{3, 5, 2, 1, 4, 10};

        insertSort(arrs);

        for (int arr : arrs) {
            System.out.println(arr);
        }
    }

    /**
     * 算法：插入排序
     * 需要选择作为插入的数：从第二个开始，共n-1个数
     * 每次将选择作为插入的数与前面比较，如果小于则前面的数往后移动一位，否则插入到这个位置
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {//总共需要选择作为插入的数为n-1个
            int num = arr[i];//选择作为插入的数
/*            int leftIndex = i -1;//插入的数前一个位置索引

            //插入排序算法实现
            while (leftIndex >= 0 && num < arr[leftIndex]) {
                arr[leftIndex + 1] = arr[leftIndex];//交换位置
                leftIndex--;
            }

            if (num != arr[i])
                arr[leftIndex + 1] = num;*/

           int j = i - 1;//记录插入的数前一个位置的索引
           for (; j >= 0; j--) {//从插入元素的前一个开始
                //进行比较 如果作为插入的数小于则前面的数往后移动一位，否则进入else插入到这个位置
                if (num < arr[j])
                    arr[j + 1] = arr[j];//前面的数往后移动一位
                else
                    break;
            }
            if (num != arr[i])//说明移动了位置，需要插入
                arr[j + 1] = num;//将作为比较的数插入数组中，形成新的片段有序数组
        }
    }
}


 

运行结果：



 

 

 

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

/*
 * 直接插入排序（straight insertion sort）的做法是：
 * 每次从无序表中取出第一个元素，把它插入到有序表的合适位置使有序表仍然有序，直至无序表中所有元素插入完为止。
 * 第一趟扫描前两个数，然后把第二个数按大小顺序插入到有序表中；
 * 第二趟把第三个数与前两个数从前向后扫描，把第三个数按大小插入到有序表中；
 * 依次进行下去，进行了（n-1）趟扫描以后就完成了整个排序过程。
 * 
 * 直接插入排序属于稳定的排序，最坏时间复杂度为O（n^2），空间复杂度为O（1）。
 * 
 * 直接插入排序是由两层嵌套循环组成的。
 * 外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置。
 * 直接插入排序是将待比较的数值与它的前一数值进行比较，所以外层循环是从第二个数值开始的。
 * 当前一数值比待比较数值大的情况下后移该数值并继续循环比较，
 * 直到找到比待比较数值小的并将待比较数值插入其后一位置，结束该次循环。
 * 值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，
 * 因为当一趟比较完成时，我们要将待比较数值插入比它小的数值的后一位置。
 * 插入排序类似于玩纸牌时整理手中纸牌的过程。
*/

namespace InsertionSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// The main.
        /// </summary>
        public static void Main()
        {
            int[] a = {1, 4, 6, 2, 8, 7, 9, 3, 5, 10};

            Console.WriteLine("Before Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n\r\nIn Insertion Sort:");
            InsertionSort(a);

            Console.WriteLine("\r\nAfter Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }
        }

        /// <summary>
        /// The insertion sort.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        public static void InsertionSort(int[] a)
        {
            // 从第二个元素开始迭代。
            for (int i = 1; i < a.Length; i++)
            {
                // 存储待插入的元素。
                int tmp = a[i];
                int j = i - 1;

                // 从当前元素右边寻找插入点。
                while (a[j] > tmp)
                {
                    // 后移。
                    a[j + 1] = a[j];
                    j--;
                    if (j == -1)
                    {
                        break;
                    }
                }

                // 该后移的元素已经后移了，会留下一个空位置，这个位置就是待插入元素的插入点。
                a[j + 1] = tmp;

                // 打印数组。
                foreach (int k in a)
                {
                    Console.Write(k + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }
    }
}

// Output:
/*
Before Insertion Sort:
1 4 6 2 8 7 9 3 5 10

In Insertion Sort:
1 4 6 2 8 7 9 3 5 10
1 4 6 2 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 3 4 6 7 8 9 5 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

After Insertion Sort:
1 2 3 4 5 6 7 8 9 10
*/