插入排序算法之移动交换法

男娘i 2022-07-20 12:19 104阅读 0赞

# 简介： #

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# 动态效果图： #

![Center][]

（PS：图片是借来的）通过这个动态效果图可以直观理解插入排序的思想！

# 代码示例： #

static void Main(string[] args)
            {
                int[] arr = { 22, 12, 56, 78, 12125, 56, 44, 212, 45, 787, 21, 22, 56, 65,100 };  //待排序数组
                InsertSort(arr);    //调用插入排序函数    
                foreach (int item in arr)
                   Console.WriteLine(item);
                   Console.ReadKey();
            }
    
            private static void InsertSort(int[] arr)
            {
                //插入排序是把无序列的数一个一个插入到有序的数
                //先默认下标为0这个数已经是有序
                for (int i = 1; i < arr.Length; i++)
                {
                    int insertVal = arr[i];  //首先记住这个预备要插入的数
                    int insertIndex = i - 1; //找出它前一个数的下标（等下 准备插入的数 要跟这个数做比较）
    
                    //如果这个条件满足，说明，我们还没有找到适当的位置
                    while (insertIndex >= 0 && insertVal < arr[insertIndex])   //这里小于是升序，大于是降序
                    {
                        arr[insertIndex + 1] = arr[insertIndex];   //同时把比插入数要大的数往后移
                        insertIndex--;      //指针继续往后移，等下插入的数也要跟这个指针指向的数做比较         
                    }
                    //插入(这时候给insertVal找到适当位置)
                    arr[insertIndex + 1] = insertVal;
                }
            }

# 运行结果： #

![Center 1][]

# 总结： #

关于算法其实老师画了好长时间的讲解，自己一直都没有认真的总结过，很惭愧，其实也没有所谓的那么难，只要去做就一定能学会，接下来还是需要自己多动手做，“师父领进门修行靠个人”！

[Center]: /images/20220719/6a96408ebb0144038c9b2dbed5a1ad29.png
[Center 1]: /images/20220719/a6f3554da8464320b260ca0b64081bb4.png