直接插入排序算法，看这篇就够了

2022-10-23
山东
本文字数：1545 字
阅读完需：约 5 分钟

前言：✌ 作者简介：游坦之 ✌🏆 大学软件工程在读，希望学到真本领，经世致用 🏆📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀💬 人生格言：成好人，行好事，做儒猿💬🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

@TOC

🍉什么是直接插入排序？

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增 1 的有序表。

🍊举个例子

对{5,2,8,7,9,4,3}进行直接插入排序

第一步，容器是空的，取出第一个元素 5，放在容器的第一位。

第二步，取出第二位元素 2，与有序容器里的元素依次排序，此时有序容器里只有一个元素 5,2 与 5 进行比较，2 比 5 小，2 放在 5 前面。

第三步，取出元素 8，依次与有序容器里的元素进行比较。与 2 进行比较，大于 2，继续往后进行比较，8 还是大于 5，所以放在 5 的后面。

第四步，取出元素 7，依次与有序容器里的元素进行比较。和 2 进行比较，7>2，继续往后取出元素 5 进行比较,7>5，继续取出元素 8 进行比较。7<8，所以 7 放在元素 8 的前面。

第五步，取出元素 9，依次与有序容器里的元素进行比较。和 2 进行比较，9>2，继续往后取出元素 5 进行比较，9>5，继续元素 7 进行比较，9>7，继续往后取出元素 8，进行比较，9>8，所以 9 放在 8 的后面。

第六步，取出元素 4，依次与有序容器里的元素进行比较，和 2 进行比较，4>2，继续往后取出元素 5 进行比较，4<5，所以 4 就放在 5 前面。

第七步，取出元素 3，依次与有序容器里的元素进行比较，和 2 进行比较,3>2，继续取出元素 4 进行比较，此时 3<4，所以把元素 3 放在元素 4 的前面。

🍌代码

#include <iostream>using namespace std;const int M = 10010;int a[M];int s[M];int n;int s_num = 0;//记载 int main(){  cout<<"请输入有多少个数据"<<endl;  cin>>n;  cout<<"请输入数据"<<endl;  for(int i=0;i<n;i++)  {    cin>>a[i];  }  for(int i=0;i<n;i++)  {    bool flag = true;    for(int j=0;j<s_num;j++)    {      if(a[i]<=s[j])      {        for(int k = s_num-1;k>=j;k--)//后移的操作         {          s[k+1] = s[k];         }        s_num++;        flag = false;//代表置换了        s[j] = a[i];        break;       }    }    if(flag)//意味着这个数比s这个有序数组里面所有的元素的都大     {            s[s_num++] = a[i];    }  }  for(int i=0;i<s_num;i++)  {    cout<<s[i]<<" ";  }    return 0; }

复制代码

🍋总结

由上面的栗子可以清晰的看出，直接插入排序需要两个容器，一是承载所有的集合，而是承载逐步扩充的有序集合。有序集合本是空集，随着每一步的扩充，集合的元素总数加 1.也就是原集合有多少个元素，就需要进行多少步，即原有 n 个元素，就要进行 n 步排序。而每一步排序，最坏情况都需要遍历 m 次，这就意味着直接插入排序的时间复杂度即为 O(n2)。但是从上面的代码来看，如果用到的是普通的数组，对于数组后移这样的操作，仍需要遍历 z 次，这就意味着时间复杂度变成了 O（n3)。对此，我们可以用动态数组或者是链表进行优化。

就比赛而言，每个比赛的时间限制大体在 1s，计算量在 10 的 8 次方，对于 O（n2）的时间复杂度而言，直接插入排序适合的计算量大约在 10000 左右，超过 10000 的数据不太适合用直接插入排序。则需要更高效的算法，或者需要更方便的容器。

而对于容器而言，常见的有数组、链表、set、vector、map、queue、stack 等等。