本文共 1329 字，大约阅读时间需要 4 分钟。

十大常用的排序算法之插入排序 C#实现

算法描述

  什么是插入排序呢?插入排序，一般也被称为直接插入排序，英文名Insertion Sort。它的主要思想为：将数组分为有序数组和无序数组，在无序数组中抽出一个元素，插入到有序数组。当然不可能随随便便就放进有序数组了，在插入有序数组时需要找到一个合适的位置。那么怎么来找到这个合适的位置呢，我举一个简单的例子。

  大家都打过扑克牌吧！假设你摸起的第一张牌是“9”，这个时候将你手上的牌看做一个有序数组，牌堆的牌是无序数组。

摸起的第二张牌是“5”，那么这第二张牌就是一个待插入的元素。 这时你会把“5”和“9”做一个大小的比较，很明显“5”是更小的一个，合适的位置“9”的左边。 再摸起来一张“10”。 将“10”与“9”做比较，“10”更大一些，合适的位置是“9”的右边。 这时，又摸起来一张“5”。 优先与“10”比较，小于“10”。再与“9”比较，小于“9”。再与（方片）“5”比较，（梅花）“5”并不会小于（方片）“5”，那么手上（图中方片）“5”和“9”之间就是我们要找的合适的位置！把（梅花）“5”插入进去。（注：比大小只比数字，与花色无关。如果待插入元素小于比较元素才会继续向左遍历，提到花色只是为了区分我说的是哪个“5”） 依次类推…摸到“7”…比较…插入。 摸到“Q（12）”…比较…插入。

当所有元素都在有序数组时，排序结束。 算法实现 C#

//插入排序        public static int[] InsertSort(int[] arr)        {
               //数组下标0的元素视为有序,从1开始遍历            for(int i = 1; i < arr.Length; i++)            {
                   //将待插入的元素取出                int inserted = arr[i];                //j所指向的是待比较的元素                int j = i-1;                //如果j所指向的待比较元素下标大于或等于0时,并且待插入的元素小于待比较的元素时,待比较元素向后移动                //然后继续向左遍历(j--),那么空出来的位置就是(j+1)                for (; j >= 0 && inserted < arr[j]; j--)                {
                       arr[j+1] = arr[j];                }                //直到不满足条件时结束循环,空出来就是"合适的位置",将元素插入                arr[j + 1] = inserted;            }            return arr;        }

算法分析

  插入排序是稳定排序()，时间复杂度为O(n²)(最好的情况下O(n)),空间复杂度为O(1)。

转载地址：https://blog.csdn.net/m0_56500170/article/details/115261258 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！