Morning Star's blog
  2. cplus

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

在其实现过程通常使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

其C/C++语言实现的示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

const int TESTS_LENGTH = 10;

void insertion_sort(int a[], int length) {

	for (int i=1; i<length; i++) {

		int key = a[i];
		int j = i-1;

		while (j>=0 && a[j]>key) {
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = key;
	}
}


int main() {

    int a[TESTS_LENGTH] = {100, 120, 110, 9, 2, 8, 1090, 20, 31, 57};


    insertion_sort(a, TESTS_LENGTH);

    // 打印运行结果
    printf("\n");
    for(int i = 0; i < TESTS_LENGTH; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

}
TAGS