C++实现希尔排序（ShellSort）

下面是关于C++实现希尔排序（ShellSort）的攻略。

什么是希尔排序？

希尔排序是插入排序的一种改进版本，与普通插入排序不同的是，它会先将数组按一定间隔 gap 分成若干个小组进行插入排序，然后缩小间隔再分组排序，直到最后 gap 为 1，此时整个序列就是有序的。希尔排序的本质就是分组的插入排序。

希尔排序的代码实现

下面针对希尔排序的核心代码进行讲解说明，具体代码实现如下：

void shellSort(int arr[], int n) {
    // 初始化 gap 值
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        // 按 gap 分组进行插入排序
        for (int i = gap; i < n; i++) {
            int j = i - gap;
            int cur = arr[i];
            // 插入排序
            while (j >= 0 && arr[j] > cur) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = cur;
        }
    }
}

上述代码中，首先需要初始化 gap 值，然后按照一定间隔 gap 对数组进行分组，并对每个小分组进行插入排序，最后不断缩小间隔 gap，重复前面的分组和插入排序，直到 gap 为 1。

示例说明

下面为两条希尔排序的示例说明，围绕实际问题场景，分别模拟了整型数组、字符串数组的排序过程。

示例1

现在有一个整型数组，要求对它进行希尔排序。

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int j = i - gap;
            int cur = arr[i];
            while (j >= 0 && arr[j] > cur) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = cur;
        }
    }
}

int main() {
    int arr[] = { 10, 8, 4, 1, 9, 3, 6, 5, 2, 7 };
    int n = sizeof(arr) / sizeof(*arr);
    shellSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

输出结果如下：

1 2 3 4 5 6 7 8 9 10 

针对以上代码，解释如下：

• 创建一个整型数组 arr，长度为10
• 初始化数组 arr 的值为{ 10, 8, 4, 1, 9, 3, 6, 5, 2, 7 }
• 对数组 arr 进行希尔排序
• 输出排序后的数组结果

示例2

现在有一个字符串数组，要求对它进行希尔排序。

#include <iostream>
#include <string>
using namespace std;

void shellSort(string arr[], int n) {
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int j = i - gap;
            string cur = arr[i];
            while (j >= 0 && arr[j] > cur) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = cur;
        }
    }
}

int main() {
    string arr[] = { "apple", "orange", "banana", "pear", "grape", "watermelon" };
    int n = sizeof(arr) / sizeof(*arr);
    shellSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

输出结果如下：

apple banana grape orange pear watermelon 

针对以上代码，解释如下：

• 创建一个字符串数组 arr，长度为6
• 初始化数组 arr 的值为{ "apple", "orange", "banana", "pear", "grape", "watermelon" }
• 对数组 arr 进行希尔排序
• 输出排序后的数组结果

总结

通过上述实例讲解，我们可以发现，希尔排序是个很好的算法，它提高了插入排序的效率，常被用在实际的工程中。