0%

《算法导论》| 第二章 算法基础

Posted on Edited on In Views: Valine:

插入排序

思路与实现

使用插入排序算法解决排序问题：输入一个待排序的序列，期待输出一个非递减的序列。

插入排序的思路是从左到右遍历序列，不断为遍历到的数（key）安排到左边（或原地）的合适位置。在遍历过程中，左边已遍历过的序列是已排序的，右边未遍历过的序列是未排序的。

下面是c语言实现的插入排序。

书中的伪代码的序列编号是从1开始的，在下面的c语言实现中，序列用数组存储，编号是从0开始的，因此边界值是不同的。

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
#include <stdio.h>
#define N 10

// 输入：待排序数组,数组长度
void InsertionSort(int A[], int n)
{
    int i = 0, j = 0;
    int key = 0; // 存储当前正在被安排位置的数
    for (j = 1; j < n; j++) {
        key = A[j];
        i = j - 1; // 从key的前一个位置的数开始比较
        while (i >= 0 && A[i] > key) {
            A[i + 1] = A[i];
            i--;
        }
        A[i + 1] = key; // 找到合适的位置i,将key安排在i后面
    }
    return;
}

int main()
{
    int i;
    int nums[N] = { 1, 0, 5, 6, 22, 3, 14, 56, 6, 8 }; 
    InsertionSort(nums, N);
    // 打印结果
    for (i = 0; i < N - 1; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

输出：

1
0 1 3 5 6 6 8 14 22 56

插入排序的正确性

循环不变式

插入排序的中间状态是，左边已遍历过的序列是已排序的，右边未遍历过的序列是未排序的。当我们遍历到位置$j$时，A[0…j-1]构成了已排序的序列，A[j+1…n-1]构成了未排序的序列。而且，A[0…j-1]的数就是原来未经处理的从0到j-1位置上的数，具有该性质的A[0…j-1]称为一个循环不变式。

循环不变式主要用来帮助我们理解算法的正确性。

循环不变式的性质

一个循环不变式具有如下性质：

  1. 初始化：循环的第一次迭代前，它为真；
  2. 保持：如果循环的某次迭代之前，它为真，那么下次迭代之前它仍为真；
  3. 终止：在循环终止时，不变式为我们提供了一个有用的性质，该性质有助于证明算法是正确的。

循环不变式的性质证明

按照数组存储编号来描述，序列编号从0开始。

当性质1初始化成立时，循环不变式保证在第一次迭代前都是真的。迭代开始前（j=1），循环不变式由A[0]一个元素组成，该元素在算法开始前后没有变，是已排序的。因而该性质是成立的。

当性质2保持成立时，循环不变式保证在每一次迭代前都是真的。如果遍历到A[j]，它的上一次迭代是将A[j-1]前的元素陆续向右移动一个位置直到为A[j-1]找到正确的位置插入。因此遍历到A[j]时的迭代前，A[0…j-1]是一个循环不变式，是已排序的、原元素组成的序列。

当性质3终止成立时，循环不变式在循环中之后为真。循环终止的条件是j>=A.length=n，当循环结束时，j等于n。将j=n带入上述性质验证中的标识，子数组A[0…n-1]由原来的A[0…n-1]组成，是已排序的状态。而A[0…n-1]就是整个数组，因此整个输入已排序。算法正确。

分析算法

分析算法，来预测算法需要多少资源。

插入排序算法的分析

一般来说，算法需要的时间与输入规模同步增长，所以通常把一个程序的运行时间描述成其输入规模的函数。

输入规模的度量

对于排序问题来说输入规模是输入中的项数；对于输入为图的问题来说，输入规模是图的顶点数和边数。

对于不同的问题，分析算法时需要指出输入规模的度量。

基本操作数

一个算法在特定输入上的运行时间是指执行的基本操作数步数。

设计算法

我们可以选择使用的算法设计技术有很多。

增量法

插入排序使用了增量方法：在排序子数组A[1…j-1]后，将单个元素A[j]插入子数组的适当位置，产生排序好的子数组A[1…j]。

分治法

分治法的算法结构是递归的——算法一次或多次递归地调用自身，以解决紧密相关的若干子问题。

分治法的思想是将原问题分解为几个规模较小但类似与原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

归并排序

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<math.h>
#define N 10

void Merge(int a[], int low, int mid, int high){
	int i, j, k;
	int b[N];
	i = low;
	j = mid + 1;
	k = low;
	while (i <= mid && j <= high) {
		while (a[i] <= a[j] && i <= mid && j <= high) {
			b[k] = a[i];
			i++;
			k++;
		}
		while (a[i] >= a[j] && i <= mid && j <= high) {
			b[k] = a[j];
			j++;
			k++;
		}
	}
	while (i <= mid) {
		b[k] = a[i];
		i++, k++;
	}
	while (j <= high) {
		b[k] = a[j];
		j++, k++;
	}
	for (i = low; i <= high; i++) {
		a[i] = b[i];
	}
	return;
}


void Mergesort(int M[], int low, int high)
{
	int mid;
	mid = (low + high) / 2;
	if (low < high){
		Mergesort(M, low, mid);
		Mergesort(M, mid + 1, high);
		Merge(M, low, mid, high);
	}
	return;
}

int main()
{
	int i;
	int M[N] = { 1, 0, 2, 32, 5, 1, 24, 20, 42, 0 };
	int len = N;
	Mergesort(M, 0, len - 1);
    // 打印结果
	for (i = 0; i < len; i++) {
		printf("%d ", M[i]);
	}
	return 0;
}

输出：

1
0 1 3 5 6 6 8 14 22 56

分析分治算法

使用递归方程或者递归式来描述包含递归调用的算法。