排序算法之插入排序
罗朝辉（http://www.cppblog.com/kesalin）
转载请注明出处
排序是数据处理中经常使用的一种重要运算，在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重，其重要性无需多言。下文将介绍常用的如下排序方法，对它们进行简单的分析和比较，并提供 C/C++ 语言实现。
所谓排序，就是要将一堆记录，使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略，可以分为如下五种：
1、插入排序（直接插入排序、希尔排序）
2、交换排序（冒泡排序、快速排序）；
3、选择排序（直接选择排序、堆排序）；
4、归并排序；
5、桶排序（桶排序，基数排序）；
其中插入排序、交换排序、选择排序、选择排序、归并排序都是基于关键字比较的排序，比较排序的平均时间复杂度好不过 O(nlogn)。
而桶排序是基于映射的排序，其平均时间复杂度可达到 O(n)，但桶排序需要额外的空间来存储经过映射的记录。
通常在待排序记录较多的时候，基于映射的排序 O(n) 比基于比较的排序 O(nlogn) 的效率要高得多，这很好理解：用空间换时间。（查找算法其实也是如此，散列查找比其他查找算法的效率要高得多）。
另外，在讨论一个排序算法的效率时，光看时间复杂度是不够的，还要看待排序记录的规模。比如说，平均时间复杂度为 O(n ^ 2) 的插入排序，冒泡排序等在待排序记录规模较小的情况下，其效率反而比平均时间复杂度为 O(nlogn) 的堆排序要好。
废话少说，下面开始简单介绍排序算法及其 C/C++ 语言实现。
插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
下面介绍两种插入排序方法：直接插入排序和希尔排序。
直接插入排序
基本思想：将待排序记录分成两部分：有序部分和无序部分，逐个从无序部分中取出记录插入有序部分中的合适位置，使有序部分依然保持有序，直到无序部分为空，完成排序。
代码实现：
1
void insert_sort(int* array, int length)
2
{
3
assert(array && length >= 0);
4
5
if (length <= 1) {
6 return;
7
}
8
9 int i, j, temp;
10 for (i = 1; i < length; ++i) {
11 temp = array[i];
12 j = i - 1;
13
14 while (j >= 0 && temp < array[j]) {
15 array[j + 1] = array[j];
16 --j;
17 }
18
19 array[j + 1] = temp;
20 }
21
}
时间复杂度分析：
直接插入排序算法主要进行有两个操作：查找比较，移动记录，这两个操作均和记录长度 n 相关。其平均时间复杂度为 O(n ^ 2)。这在排序算法里面算慢的，但是当记录较少时，它的效率还是可以不错的。
空间复杂度分析：
直接插入排序只需要一个元素的辅助空间，用于元素的位置交换 O(1)。
补充：
直接插入排序是稳定排序。
它在元素基本有序的情况下（接近最好情况），比较和移动的次数都较少，效率是很高的。
希尔排序(Shell sort)
希尔排序是插入排序的一种，它是利用直接插入排序实现的。
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小，通常为 1）时，再对全体元素进行一次直接插入排序。
代码实现：
1void shell_sort(int* array, int length)
2{
3 assert(array && length >= 0);
4
5 if (length <= 1) {
6 return;
7 }
8
9 int i, j , temp;
10 int increment = length;
11
12 do {
13 increment = increment / 3 + 1;
14
15 // 希尔排序中的一趟排序，increment 为当前增量
16 // 将 [increment, length - 1] 之间的记录分别插入各组当前的有序区
17 for (i = increment; i < length; ++i) {
18 temp = array[i];
19 j = i - increment;
20
21 while (j >= 0 && temp < array[j]) {
22 array[j + increment] = array[j];
23 j -= increment;
24 }
25
26 array[j + increment] = temp;
27 }
28 } while (increment > 1);
29}
时间复杂度分析：
希尔排序的执行时间依赖于增量序列。如果选取好的增量序列呢，总的来说有如下两点：
① 最后一个增量必须为 1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况，所以一般都取奇数。
希尔排序的平均时间复杂度也为 O(n ^ 2)，其效率通常比直接插入排序要高，因为当增量减少到接近 1 时，序列已经基本有序了，前面分析过，直接插入排序在序列基本有序的情况下，效率是很高的。
空间复杂度分析：
直接插入排序只需要一个元素的辅助空间，用于元素的位置交换 O(1)。
补充：
希尔排序是不稳定的。
=============================================
测试代码：
1typedef void (*Sort_Function)(int* array, int length);
2
3struct SortFucntionInfo {
4 char * name;
5 Sort_Function func;
6};
7
8SortFucntionInfo sort_function_list[] = {
9 {"直接插入排序", insert_sort},
10 {"希尔排序", shell_sort},
11 {"", NULL}
12};
13
14void print_array(const int* a, int length, const char* prefix)
15{
16 assert(a && length >= 0);
17
18 if (prefix) {
19 printf("%s", prefix);
20 }
21
22 for (int i = 0; i < length; i++) {
23 printf("%d ", a[i]);
24 }
25
26 printf("\n");
27}
28
29void test_sort(Sort_Function func)
30{
31 const int length = 11;
32 const int count = 2;
33 int array[count][length] = {
34 {65, 32, 49, 10, 8, 72, 27, 42, 18, 58, 91},
35 {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
36 };
37
38 for (int i = 0; i < count; i++) {
39 print_array(array[i], length, " original: ");
40
41 func(array[i], length);
42
43 print_array(array[i], length, " sorted: ");
44
45 printf("\n");
46 }
47}
48
49int main(int argc, const char* argv[])
50{
51 for (int i = 0; sort_function_list[i].func != NULL; i++) {
52 printf("\n=== %s ===\n", sort_function_list[i].name);
53 test_sort(sort_function_list[i].func);
54 }
55
56 system("pause");
57 return 0;
58}
运行结果：
=== 直接插入排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10
=== 希尔排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10