插入排序，稳定排序的一种,平均时间复杂度为O(n^2),它的代码量很小，对于处理小数据的排序还是可以的。
排序扑克牌可以形象地描述插入排序（贴近生活），算法导论就是用它来引入主题的。
算法描述如下（摘自百度百科）：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
具体代码如下：
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
38
39
40
41
42
43
44
45
46
|
#include <stdio.h>
#define MAX 100
void Insert(int [], int);
int main(void)
{
int i = 1;
int n;
int ar[MAX];
//freopen("input.txt", "r", stdin);/*可以将标准输入输出重定向到文件*/
//freopen("output.txt","w", stdout);
scanf("%d", &n); /*读取待排序元素的个数*/
for(i = 1; i <= n; i++)
{
scanf("%d", &ar[i]); /*读取元素并写入数组中*/
}
Insert(ar, n); /*排序*/
for(i = 1; i <= n; i++)
{
printf("%d ", ar[i]); /*显示排序后的数据*/
if(i % 10 == 0) putchar('\n'); /*输出每10个元素一行*/
}
return 0;
}
void Insert(int a[], int n) //a数组有效数据是下标1...n
{
int i, j;
for(i = 2; i <= n; i++)
{
a[0] = a[i]; /*用a[0]作为临时保存a[i]的变量*/
j = i-1;
while(a[0] < a[j]) /*从a[i - 1]开始到a[0]逐个检查，并将元素推后*/ a[j + 1] = a[j--]; a[j + 1] = a[0]; /*找到合适位置，将元素插入*/ } }
/* void Insert(int a[], int n) //递归版本 { int i; if(n > 1)
{
Insert(a, n - 1);
i = n - 1;
a[0] = a[n];
while(a[0] < a[i])
a[i + 1] = a[i--];
a[i + 1] = a[0];
}
}
*/
|
测试数据:
输入：
1
2
3
4
5
6
|
50
5 17 18 97 72 71 62 84 66 38
25 68 86 57 45 5 70 51 52 97
35 4 55 24 62 63 33 64 84 75
26 32 69 51 67 26 53 87 18 33
33 94 2 84 76 93 19 76 53 81
|
输出：
1
2
3
4
5
|
2 4 5 5 17 18 18 19 24 25
26 26 32 33 33 33 35 38 45 51
51 52 53 53 55 57 62 62 63 64
66 67 68 69 70 71 72 75 76 76
81 84 84 84 86 87 93 94 97 97
|