插入排序算法

JusterZhu

发布于 2022-12-07 20:40:57

2820

发布于 2022-12-07 20:40:57

文章被收录于专栏：JusterZhuJusterZhu

概要

插入排序属于内部排序法，是对需要排序的元素以插入的方式寻找该元素适当位置，以达到排序的目的。

算法思想

插入排序（insertion sorting）的基本思想是：把n个待待续的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。

详细内容

应用实例：

有一群学生，考试成绩分别是101,34,119,1请从小到大排序。

分解代码：

 public class InsertSort
    {
        public static void Sort(int[] arr)
        {
            //第一轮：{101,34,119,1}  --> {34,101,119,1}

            //定义待插入的数
            int insertVal = arr[1];
            //即arr[1]的前面这个数的下标
            int insertIndex = 1 - 1;
            //给insertval找到插入的位置
            //1.insertindex >0 保证在给 insertval找到插入位置，不越界
            //2.insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            //3.就需要将arr[insertIndex]后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex])
            {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //当推出while循环时，说明插入的位置找到，insertindex+1
            arr[insertIndex + 1] = insertVal;

            Console.WriteLine("第一轮插入后");
            Console.WriteLine(string.Join(' ', arr));
        }
    }

    static void Main(string[] args)
        {
            int[] array = { 101,34,119,1 };
            InsertSort.Sort(array);
            Console.Read();
        }

基于以上逻辑分解之后，再看看完整代码演示：

   public class InsertSort
    {
        public static void Sort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                //定义待插入的数
                int insertVal = arr[i];
                //即arr[1]的前面这个数的下标
                int insertIndex = i - 1;
                //给insertval找到插入的位置
                //1.insertindex >0 保证在给 insertval找到插入位置，不越界
                //2.insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
                //3.就需要将arr[insertIndex]后移
                while (insertIndex >= 0 && insertVal < arr[insertIndex])
                {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
                //当推出while循环时，说明插入的位置找到，insertindex+1
                //举例：
                arr[insertIndex + 1] = insertVal;
                Console.WriteLine(string.Join(' ', arr));
            }
        }
    }

        static void Main(string[] args)
        {
            int[] array = { 101,34,119,1 ,-1 , 89};
            InsertSort.Sort(array);
            Console.Read();
        }