排序算法

插入排序（Insertion Sort）

算法思想：每次将一个待排的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。

算法演示（只演示了前4个元素）：

插入排序

基本代码如下：

template<typename T>
void insertionSort(T arr[], int n) {

    for (int i = 1; i < n; i++) {
        // 寻找元素arr[i]合适的插入位置
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1])
                swap(arr[j], arr[j - 1]);
            else
                break;
        }
    }
}

这里为了比较选择排序和插入排序的性能，我们在SortTestHelper.h文件中添加如下代码：

// 复制数组
int *copyIntArray(int a[], int n) {
    int *arr = new int[n];
    copy(a, a + n, arr);
    return arr;

同时，我们创建一个SelectionSort.h文件，在该文件中添加如下代码：

#include <iostream>

using namespace std;

template<typename T>
void selectionSort(T arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 寻找[i, n)区间里的最小值
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex != i)
            swap(arr[i], arr[minIndex]);
    }
}

好了，我们在main()中调用两个算法比较一下它们的性能，具体代码如下：

int main(void) {

    int n = 10000;
    int *arr_1 = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr_1, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr_2, n);

    delete[] arr_1;
    delete[] arr_2;
    return 0;
}

其输出结果如下：

Insertion Sort : 0.533 s
Selection Sort : 0.171 s

从结果中发现，插入排序算法的性能不及于选择排序，这是为什么呢？这是因为我们在插入排序中，对数组不断遍历的同时，还在不断地交换，在交换的时候，我们还要不断遍历数组并在相应的位置进行赋值操作。这样一来，我们插入排序的性能自然不及于选择排序。那我们有什么办法改进插入排序呢？

改进插入排序算法思想：每次将一个待排的记录保存下来，按其关键字的大小插入到前面已经排好序的子序列中，直到全部记录插入完成。

改进插入排序算法演示（只演示了前4个元素）：

改进插入排序

改进插入排序基本代码如下：

template<typename T>
void insertionSort(T arr[], int n) {

    for (int i = 1; i < n; i++) {
        // 寻找元素arr[i]合适的插入位置

        T e = arr[i];
        // j保存元素e应该插入的位置
        int j;
        for (j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

我们再运行一遍，来看看现在这两个算法运行的时间结果如何。其结果如下所示：

Insertion Sort : 0.108 s
Selection Sort : 0.163 s

此时，我们发现插入排序的性能发生了显著变化，其效率已经好于选择排序算法。在插入排序中，我们通过控制内层循环的运行与终止进而提高了插入排序的性能。为了让大家更为显著地了解控制内层循环的运行与终止对插入排序而言是一个非常重要的性质，我们在SortTestHelper.h文件中，添加如下代码：

    // 生成一个近乎有序的随机数组
    int *generateNearlyOrderdArray(int n, int swapTimes) {

        int *arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;

        srand(time(NULL));
        for (int i = 0; i < swapTimes; i++) {
            int posx = rand() % n;
            int posy = rand() % n;
            swap(arr[posx], arr[posy]);
        }

        return arr;
    }

然后，我们在main()中调用，其代码如下：

int main(void) {

    int n = 10000;
    int *arr_1 = SortTestHelper::generateNearlyOrderdArray(n, 100);
    int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr_1, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr_2, n);

    delete[] arr_1;
    delete[] arr_2;
    return 0;
}

其运行结果如下：

Insertion Sort : 0.004 s
Selection Sort : 0.186 s

从结果中，我们可以看出对一个近乎有序的数组而言，插入排序的性能是远远好于选择排序的。事实上，插入排序在处理近乎有序的数据时其性能甚至好于时间复杂度为O(nlogn)的算法。 因此，我们在处理近乎有序的数据时推荐使用插入排序。