续说排序

接着上一篇文章常用的排序，继续说直接插入排序，直接选择排序和堆排序，默认排序顺序仍是递增排序。废话不多说了，开始进入正题。

插入排序其实分为：直接插入排序，二分插入排序（或折半插入排序），希尔排序，其基本思想就是：每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。在这里只介绍直接插入排序。

直接插入排序

直接先来代码好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(RecType R[],int n)
{
	int i,j;
	RecType tmp;
	for (int i = 1; i < n; i++)
	{
		tmp = R[i];
		j = i - 1;
		while(j >= 0 && tmp.key < R[j].key) 
		{
			R[j+1] = R[j];
			j--;
		}
		R[j+1] = tmp;
	}
}

此排序的操作过程为：假设有一序列为（6，3，7，5，1，4，2，9），刚开始时i = 1，j = 0，有序区暂时只有R[0]一个记录。从6起，从右向左查找，3小于6，将6右移一个位置，j– 后while条件不满足了，结束while循环，将3插入R[0]的位置，此时序列变为（3，6，7，5，1，4，2，9），第一趟排序结束。接下来第二趟排序，i = 2，待插入的记录为R[2] = 7，从6开始从右向左查找。7大于6，while条件不满足，所以7的位置不变。此时序列变为（3，6，7，5，1，4，2，9），第三趟排序…以此类推，直到所有记录都有序为止。

初始序列：6 3 7 5 1 4 2

i = 1： 3 6 7 5 1 4 2 9
i = 2： 3 6 7 5 1 4 2 9
i = 3： 3 5 6 7 1 4 2 9
i = 4： 1 3 5 6 7 4 2 9
i = 5： 1 3 4 5 6 7 2 9
i = 6： 1 2 3 4 5 6 7 9
i = 7： 1 2 3 4 5 6 7 9

选择排序的基本思想是：每一趟排序是从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的末尾，直到全部记录排序完毕。常用的选择排序方法有直接选择排序（或简单选择排序）以及 堆排序。

直接选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectSort(RecType R[],int n) 
{
	int i,j,k;
	RecType tmp;
	for (int i = 0; i < n - 1; i++)
	{
		k = i;
		for (int j = i + 1; j < n; j++)
			if (R[j].key < R[k].key)
				k = j;
		if (k != i)
		{
			tmp = R[i];
			R[i] = R[k];
			R[k] = tmp;
		}
	}
}

此排序的操作过程为：还是以序列为（6，3，7，5，1，4，2，9）的例子来说吧。刚开始时 i = 0，假设i = 0这个位置对应的关键字是最小的，从i+1开始，在6后面的序列中找到最小的那个记录，用 k 记下第一趟排序后目前找到的最小的关键字所在的位置，判断 k 是否等于 i，不相等，说明最小值的位置发生了变化，需要交换下R[i] 和 R[k]，此时序列为（1，3，7，5，6，4，2，9）。接着第二趟排序开始…以此类推，经过n - 1趟排序后，整个序列递增有序。

初始序列：6 3 7 5 1 4 2 ，排序过程如下所示：
直接选择排序

堆排序

待续 O(∩_∩)O