插入排序 订阅
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。 展开全文
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。
信息
外文名
Insertion sort
空间复杂度
O(1)
别    称
直接插入排序
分    类
排序方法
中文名
插入排序
时间复杂度
O(N^(1-2))
稳定性
稳定
插入排序基本思想
插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌 [1]  。插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 [3]  。
收起全文
精华内容
下载资源
问答
  • 插入排序

    千次阅读 多人点赞 2019-12-09 19:49:16
    一、插入排序(InsertSort) 插入排序从第二个数开始,拿出第二个数进行向前插入排序,一直到最后一个数向前做插入排序。算法稳定。 插入排序的时间复杂度为O(n^2),空间复杂度为O(1)。最好的时间复杂度是O(n),最...

    一、插入排序(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;//将作为比较的数插入数组中,形成新的片段有序数组
            }
        }
    }
    

     

    运行结果:

     

     

     

    展开全文
  • 算法 - 插入排序(C#)

    万次阅读 多人点赞 2019-02-01 10:58:01
    * 直接插入排序(straight insertion sort)的做法是: * 每次从无序表中取出第一个元素,把它插入到有序表的合适位置使有序表仍然有序,直至无序表中所有元素插入完为止。 * 第一趟扫描前两个数,然后把第二个数...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击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
    */

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,181
精华内容 32,072
关键字:

插入排序