基础排序（四）

希尔排序（Shell Sort）

算法思想：先将待排序表分割成若干个形如L[i, i+d, i+2d, ... , i+kd]的“特殊”子表，分别进行插入排序，当整个表中元素已呈“基本有序”时，再对全体记录进行一次插入排序。

算法图解：

希尔排序

注：图片来自Lyndon的专栏，如若侵权请联系本人删除，谢谢！

基本代码如下：

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

    // Incremnet表示增量
    int i, j, Increment;
    T tmp;
    // 增量变化
    for (Increment = n / 2; Increment > 0; Increment /= 2) {
        // 在增量为某个值时，进行插入排序
        for (i = Increment; i < n; ++i) {
            tmp = arr[i];
            for (j = i; j >= Increment; j -= Increment) {
                if (tmp < arr[j - Increment])
                    arr[j] = arr[j - Increment];
                else
                    break;
            }
            arr[j] = tmp;
        }
    }
}

为了和选择排序、插入排序、冒泡排序比较算法效率，故分别创建SelectionSort.h文件、InsertionSort.h和BubbleSort.h文件，并分别添加如下代码：

// 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]);
    }
}

// InsertionSort.h

#include <iostream>

using namespace std;

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;
    }
}

// BubbleSort.h

#include <iostream>

using namespace std;

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

    for (int i = 0; i < n - 1; ++i) {
        // 表示本趟冒泡是否发生交换的标志
        bool flag = false;
        for (int j = n - 1; j > i; --j) {
            if (arr[j - 1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
                flag = true;
            }
        }
        // 本趟遍历后没有发生交换，说明已有序
        if (flag == false) return;
    }
}

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

int main(void) {

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

    SortTestHelper::testSort("Shell Sort", shellSort, arr_1, n);
    SortTestHelper::testSort("Insertion Sort", insertionSort, arr_2, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr_3, n);
    SortTestHelper::testSort("Bubble Sort", bubbleSort, arr_4, n);

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

其运行结果如下：

Shell Sort : 0.003 s
Insertion Sort : 0.124 s
Selection Sort : 0.187 s
Bubble Sort : 0.866 s

从结果中，我们发现希尔排序在随机数组的情况下，其运行效率比之前我们学习的排序算法的效率都高。那么我们不禁想问希尔排序在处理近乎有序的数据时，其效率也会这么高吗？为此，我们调用generateNearlyOrderdArray()来测试一下，其代码如下：

int main(void) {

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

    SortTestHelper::testSort("Shell Sort", shellSort, arr_1, n);
    SortTestHelper::testSort("Insertion Sort", insertionSort, arr_2, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr_3, n);
    SortTestHelper::testSort("Bubble Sort", bubbleSort, arr_4, n);

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

其运行结果如下：

Shell Sort : 0.002 s
Insertion Sort : 0.003 s
Selection Sort : 0.293 s
Bubble Sort : 0.344 s

从结果中，我们发现希尔排序在处理近乎有序的数据时，仍然可以保证高效率。因此，我们在处理近乎有序的数据时，不仅推荐使用插入排序，也推荐希尔排序。