排序算法总结：二、插入排序

先说一下比较排序的定义吧：

比较排序的定义

就是除了赋值操作外, 只存在小于‘<’和大于‘>’这两种运算符是仅有的允许对
输入数据进行的操作。

插入排序的性质

插入排序是一种比较排序
将一个数组分为两部分,前面为排好序的部分,后面为未排序的部分
将未排序部分的元素逐个插入到已排好序部分的正确位置上
就像扑克牌按顺序排列,原先 2,4,5 和 10 都排好序了,现在需要为 7 找到正确的位置

时间复杂度

运行时间为 T(N) = O(N^2)
平均运行时间为 T(N) = Θ(N^2)。

代码实现

 1 #include 
 2  
 3 typedef int ElementType;
 4 void InsertionSort(ElementType A[], int N);
 5  
 6 void main(void)
 7 {
 8     int i;
 9     int unordered[] = {4, 5, 2, 1, 0};
10     InsertionSort(unordered, 5);
11     for(i = 0; i &lt; 5; i++)
12     {
13         printf("%d
", unordered[i]);
14     }
15 }
16  
17 //双重循环，时间复杂度为T(N)=O(N^2)
18 void InsertionSort(ElementType A[], int N)
19 {
20     int j, p;
21  
22     ElementType Tmp;
23     for(p = 1; p < N; p++)
24     {
25         Tmp = A[p];
26         for(j = p; j > 0 && A[j - 1] > Tmp; j--)
27         {
28             A[j] = A[j - 1];
29         }
30         A[j] = Tmp;
31     }
32 }

排序过程演示

排序数组 5, 2, 4, 6, 1, 3 的过程: