插入排序Insertion sort



一、问题：

输入：n个数<a₁，a₂，a₃，a₄，…，a_n>

输出：输入序列的一个排列，使得a₁≤a₂≤a₃≤a₄≤…≤a_n

        插入排序的原理类似我们打牌时整理手里牌一样，我们将每次抓到的牌插入到手里已抓的牌的正确位置当中。而为了找到这张拍的正确位置，我们需要将抓到的牌和另一只手中已有的每一张牌进行比较。这种情况下，左手中的牌都是排好序的。

如图演示一张牌插入到已经整理好的牌中去：

待插入tmep = 15           已经整理好的：3    5     9     21  24

24 >15

              →         

21>15

     →      

9<15循环结束

C++实现：

#include<iostream> #include<algorithm> using namespace std; int temp; //待插入数据 void Insert_sort(int *arr, int len) //len决定了问题的输入规模，会影响时间 { for (int j = 1; j < len; j++) { temp = arr[j]; int i = j - 1; while (i >= 0 && arr[i] > temp) { arr[i + 1] = arr[i]; //从小到大进行排序 i--; } arr[i + 1] = temp; } } void main() { int a[] = { 21,3,7,9,15,4,1 }; int size = sizeof(a) / sizeof(int); Insert_sort(a, size); for (int i = 0; i < size; i++) cout << a[i] <<" "; cout<< endl; } 运行结果：

二、时间复杂度分析

(1)最优情况：○(n)

      每次插入时带插入数据temp都在for循环的第一次比较时就不满足while循环条件，此时直接插入temp到arr[j]。这样执行次数就是关于输入问题规模len的一个线性函数，这种情况下时间复杂度为○(n).

(2)最差情况：○(n^2)

      每次插入时所有数据都满足while循环条件，即插入式考虑了已排好序的数组中的所有数值，那么第2次插入式比较次数为1，第3次比较次数为2……第n次为n，这样执行次数就是1+2+3+……+n=n(n-1)/2，所以时间复杂度为○(n^2)。