【校招VIP】排序算法 —— 直接插入排序- 校招VIP

转载声明：文章来源https://blog.csdn.net/D5486789_/article/details/143097275

1.直接插入排序的思想
直接插入排序的思想就是把待排序的元素按其关键码值的大小依次插入到一个已经排好序的有序序列中，直到所有的元素插入完为止，得到一个新的有序序列。
在我们日常生活中，玩扑克牌时，其实就是运用了直接插入排序的思想。

2.直接插入排序的实现
实现分析
当只有一个元素的时候，这一个元素肯定是有序的，所以，从第二个元素开始，直到后面的所有元素都是待排序的元素。

因此，我们只需要从左到右依次枚举待排序的元素，将待排序的元素插入到有序序列中即可。
比如：当我们要排升序的时候，枚举到4的时候，4就是待排序元素，4大于它的前一个元素，说明4所在位置值正确的，不需要做其他操作。当我们枚举到2的时候，2就是待排序的元素，对于这种情况，下面的图中，很详细的讲解了这种情况下如何实现一个元素的插入逻辑。

需要注意的是：

枚举待排序元素的时候是从左到右枚举，并且是从第二个元素开始枚举，直到最后一个元素。（因为第一个元素本来就是有序的）
寻找插入位置是从右往左开始寻找的，最后插入的时候，是赋值给end+1的位置。（因为，我们每次都去和end位置的值作比较，当end位置的值小于tmp中保存的值的时候，end+1就是要插入的值）
实现代码

#include <stdio.h>
  
void InsertSort(int* nums, int n)
{
    // [0,end]有序，把end+1位置的插入到前序序列
    // 控制[0,end+1]有序
    int i = 0;
    for (i = 1; i < n; i++)      // 枚举待排序的元素 
    {
        int tmp = nums[i];       // 保存待排序的值
         
        // 依次和前一个位置比较，寻找插入位置 
        int end = i-1;
        while (end >= 0)         
        {
            if (tmp < nums[end]) // 当tmp小于end位置的值的时候，需要继续寻找插入位置 
            {
                nums[end + 1] = nums[end];
                --end;
            }
            else                 // 当tmp大于or等于end位置的值的时候，说明找到了插入位置 
            {
                break;
            }
        }
         
        // 将tmp中保存的值插入到正确的位置 
        nums[end + 1] = tmp;
    }
}
  
int main()
{
    int nums[] = { 3,4,2,1,7,8,5,6 };
    InsertSort(nums, 8);
     
    int i = 0;
    while(i < sizeof(nums)/sizeof(int))
    {
        printf("%d ",nums[i]);
        i++;
    }
     
  
    return 0;
}</stdio.h>

代码运行结果如下：

3.直接插入排序的分析
时间复杂度分析
假如在最坏情况下：
我们需要枚举n-1个元素，从左到右依次需要比较1、2、3 …… n-1次，这不就是妥妥的等差数列吗？根据等差数列公式并结合大O表示法，最后的时间复杂度为O(N^2)。
空间复杂度分析
在整个排序中的实现中，我们并没有开辟其他的空间，只是使用了常数个的空间，所以空间复杂度是O(1)。

稳定性
在排序的过程中，由于我们是从右往左依次比较，当出现两个相同的元素的时候，后面的元素不会插入到前面那个相同元素的前面。只会插入在相同元素的后面，元素的相对顺序位置不会变，所以直接插入排序是稳定的。

比如：i位置的2并没有小于end位置的2，直接就跳出循环了，元素的相对顺序位置不变。