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