插入排序

缘起

邓俊辉 数据结构与算法(C++语言版) 第三章

分析

其实插入排序就是类似于打扑克的摸牌理牌

测试数据是

99 5 36 7 22 17 46 12 2 19 25 28 1 92

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 "stdafx.h"
#include <iostream>
#include <algorithm>

#define LOCAL
#define N 14

using namespace std;

// a是数组, n是数组元素的个数
void sort(int *a, int n)
{
	for (int i = 1; i<n;i++) // 从第二个数字摸进来, 现在想给a[i]找新位置
	{
		int j = i, tmp = a[i];
		while(tmp<a[j-1] && j)
		{
			a[j]=a[j-1];
			j--;
		}
		// 为tmp，也就是原来的 a[i]找到了新位置
		a[j] = tmp; 
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int a[N];
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	sort(a, N);
	for (int i = 0; i < N; i++) cout<< a[i]<< endl;
	return 0;
}

插入排序是稳定的, 就地的. 复杂度 O(n^2)