希爾排序（Shell Sort）
算法思想：先將待排序表分割成若干個(gè)形如L[i, i+d, i+2d, ... , i+kd]的“特殊”子表，分別進(jìn)行插入排序，當(dāng)整個(gè)表中元素已呈“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次插入排序。
算法圖解：
希爾排序
注：圖片來自Lyndon的專欄，如若侵權(quán)請聯(lián)系本人刪除，謝謝！
基本代碼如下：
template<typename T>
void shellSort(T arr[], int n) {
// Incremnet表示增量
int i, j, Increment;
T tmp;
// 增量變化
for (Increment = n / 2; Increment > 0; Increment /= 2) {
// 在增量為某個(gè)值時(shí)，進(jìn)行插入排序
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;
}
}
}
為了和選擇排序、插入排序、冒泡排序比較算法效率，故分別創(chuàng)建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)區(qū)間里的最小值
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應(yīng)該插入的位置
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) {
// 表示本趟冒泡是否發(fā)生交換的標(biāo)志
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;
}
}
// 本趟遍歷后沒有發(fā)生交換，說明已有序
if (flag == false) return;
}
}
好了，我們在main()中調(diào)用這幾個(gè)算法比較一下它們的性能，具體代碼如下：
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;
}
其運(yùn)行結(jié)果如下：
Shell Sort : 0.003 s
Insertion Sort : 0.124 s
Selection Sort : 0.187 s
Bubble Sort : 0.866 s
從結(jié)果中，我們發(fā)現(xiàn)希爾排序在隨機(jī)數(shù)組的情況下，其運(yùn)行效率比之前我們學(xué)習(xí)的排序算法的效率都高。那么我們不禁想問希爾排序在處理近乎有序的數(shù)據(jù)時(shí)，其效率也會(huì)這么高嗎？為此，我們調(diào)用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;
}
其運(yùn)行結(jié)果如下：
Shell Sort : 0.002 s
Insertion Sort : 0.003 s
Selection Sort : 0.293 s
Bubble Sort : 0.344 s
從結(jié)果中，我們發(fā)現(xiàn)希爾排序在處理近乎有序的數(shù)據(jù)時(shí)，仍然可以保證高效率。因此，我們在處理近乎有序的數(shù)據(jù)時(shí)，不僅推薦使用插入排序，也推薦希爾排序。
