24.总结

26.排序-插入排序

---

26.1 知识点

插入排序的基本原理

• 把要排序的元素分成两个区域：排序区和未排序区，用一个索引值做分水岭。
• 用未排序区元素与排序区元素比较，将元素插入到合适位置，直到未排序区清空。

代码实现

前提规则

• 排序开始前，首先认为第一个元素在排序区中，其它所有元素在未排序区中。

排序开始后

• 每次将未排序区第一个元素取出，与排序区中元素比较（从后往前），满足条件（较大或较小）则排序区中元素往后移动一个位置。

注意

• 所有数字都在一个数组中。
• 所谓的两个区域是一个分水岭索引。

插入排序实例

实现升序排序：[8, 7, 1, 5, 4, 2, 6, 3, 9]，将大的元素放在最后面。

// 创建无序数组
int[] array = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

// 插入排序核心代码
for (int i = 1; i < array.Length; i++)
{
    // 每轮要做的事情
    
    // 每一轮取出排序区的最后一个元素索引
    int sortIndex = i - 1;
    // 每一轮取出未排序区的第一个元素
    int nowSortNum = array[i];
    
    // 创建每轮未排序区的第一个元素和排序区逐个比较的循环
    while (sortIndex >= 0 && array[sortIndex] > nowSortNum)
    {
        // 排序区中的元素往后移一格
        array[sortIndex + 1] = array[sortIndex];
        // 移动到排序区的前一个位置，准备继续比较
        sortIndex--;
    }
    
    // 最终插入数字
    array[sortIndex + 1] = nowSortNum;
}

// 打印输出
for (int i = 0; i < array.Length; i++)
{
    Console.WriteLine(array[i]);
    // 1
    // 2
    // 3
    // 4
    // 5
    // 6
    // 7
    // 8
    // 9
}

总结

• 插入排序需要两层循环：
  • 第一层循环：每一轮依次取出未排序区的元素进行排序。
  • 第二层循环：未排序区的元素依次和排序区元素进行比较，找到想要插入的位置。
• 第一层循环从1开始遍历的原因是，插入排序的关键在于分两个区域：已排序区和未排序区，而默认第一个元素在已排序区。
• 使用while循环是因为只有满足条件才进行比较，否则插入位置已确定，不需要继续循环。
• 直接往后移位置是因为每轮要插入的未排序区的元素已记录，所以不怕丢失或覆盖。
• 确定位置后，放在sortIndex + 1的位置是因为当循环停止时，插入位置应该是停止循环的索引加1处。

基本原理：

• 两个区域：用索引值来区分未排序区与排序区，元素不停比较，找到合适位置，插入当前元素。

套路写法：

• 两层循环，一层获取未排序区元素，一层找到合适插入位置。

注意事项：

• 默认开头已排序。
• 第二层循环外插入。

---

26.2 知识点代码

using System;

namespace Lesson25_插入排序
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("插入排序");

            #region 知识点一 插入排序的基本原理

            //把要排序的元素分成两个区域：排序区和未排序区 用一个索引值做分水岭
            //用未排序区元素 与排序区元素比较 插入到合适位置 直到未排序区清空


            #endregion

            #region 知识点二 代码实现

            //前提规则
            //排序开始前
            //首先认为第一个元素在排序区中
            //其它所有元素在未排序区中

            //排序开始后
            //每次将未排序区第一个元素取出用于和
            //排序区中元素比较(从后往前)
            //满足条件（较大或者较小）
            //则排序区中元素往后移动一个位置。

            //注意
            //所有数字都在一个数组中
            //所谓的两个区域是一个分水岭索引

            //插入排序实例

            //实现升序排序 8 7 1 5 4 2 6 3 9 把大的元素放在最后面

            //创建无序数组
            int[] array = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

            //插入排序核心代码

            //第一步
            //创建每轮的比较循环
            //每轮的目标是把未排序区中的一个元素找到合适位置插入到排序区中
            //这样排序区逐渐扩大 未排序区逐渐减小
            //i=1的原因：默认第一个元素就在排序区 最后一轮判断时i = Length-1，最后i++后i=Length
            for (int i = 1; i < array.Length; i++)
            {
                //每轮要做的事

                //第二步
                //1.每一轮取出排序区的最后一个元素索引
                int sortIndex = i - 1;
                //2.每一轮取出未排序区的第一个元素
                int nowSortNum = array[i];

                //第三步
                //创建每轮未排序区的第一个元素和排序区逐个比较的循环
                //把未排序区的第一个元素放在排序区逐个进行比较 移动位置 确定插入索引

                //循环停止的条件
                //1.发现排序区中所有元素都已经比较完了（说明这个元素已经是小的元素了 放排序区最前面）
                //2.发现排序区中的元素不满足比较条件了（说明这个元素已经找到了合适的位置 前面的一个元素比自己小 后面的元素比自己大）

                //所以只要 排序区元素没有比较完 且 当前排序区元素大于取出来的未排序区的第一个元素 进循环
                while (sortIndex >= 0 &&
                    array[sortIndex] > nowSortNum)
                {
                    //只要进了这个while循环 证明满足条件

                    //排序区中的元素 就应该往后退一格
                    array[sortIndex + 1] = array[sortIndex];

                    //移动到排序区的前一个位置 准备继续比较
                    --sortIndex;
                }

                //最终插入数字
                //循环中知识在确定位置 和找最终的插入位置
                //最终插入对应位置 应该循环结束后
                array[sortIndex + 1] = nowSortNum;
                //sortIndex + 1是因为满足循环最后一次--sortIndex了 

            }

            //打印输出
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
                //1
                //2
                //3
                //4
                //5
                //6
                //7
                //8
                //9
            }

            #endregion

            #region 知识点三 总结

            //为什么有两层循环
            //第一层循环：每一轮 依次取出 未排序区的元素 进行排序
            //第二层循环：未排序区的元素 依次 和排序区元素进行比较 找到想要插入的位置

            //为什么第一层循环从1开始遍历
            //插入排序的关键是分两个区域
            //已排序区 和 未排序区
            //默认第一个元素在已排序区

            //为什么使用while循环
            //满足条件才比较
            //否则证明插入位置已确定
            //不需要继续循环

            //为什么可以直接往后移位置
            //每轮 要插入的未排序区的元素 已记录
            //要插入的未排序区的元素的原来的位置的值 不怕丢失或覆盖

            //为什么确定位置后,是放在sortIndex + 1的位置
            //当循环停止时，插入位置应该是停止循环的索引加1处

            //基本原理
            //两个区域
            //用索引值来区分
            //未排序区与排序区
            //元素不停比较
            //找到合适位置
            //插入当前元素

            //套路写法
            //两层循环
            //一层获取未排序区元素
            //一层找到合适插入位置

            //注意事项
            //默认开头已排序
            //第二层循环外插入

            #endregion

        }
    }
}

---

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com