十大排序算法之四-希尔排序【Shell'sSort】-初体验
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
关键点：
增量分组
直接插入排序算法
如上图，增量为4时，划分为3,4,5; 2,7,10; 8,6; 9,1;四个序列先进行插入排序。
当增量为5时，划分为15,6,8；5,1,10; 2,4; 7,3; 12,9; 5个序列进行插入排序；
当增量为3时。。。
当增量为1时，直接进行插入排序。
先写个.h文件
template<typename T>void ShellSort(T *arr, int length){int i, j, inc;T key = arr[0];//初始增量：n/2,每一趟之后除以2for (inc = length / 2; inc > 0; inc /= 2){cout << "增量为" << inc<<endl;//每一趟采用插入排序for (i = inc; i < length; i++){key = arr[i];for (j = i; j >= inc && key < arr[j - inc]; j -= inc)arr[j] = arr[j - inc];arr[j] = key;}for (int i = 0; i < length; i++)cout << arr[i] << " ";cout << endl;}cout << endl;}
再加入到main函数里
using namespace std;template <typename T>void PrintArray(T arr[], int n){for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;}template <typename T>void checkArrayIsSort(T arr[], int n){for (int i = 0; i < n-1; i++){if (arr[i] > arr[i + 1]){cout << "\n该数组为乱序\n";break;}}cout << "\n该数组已经排好序\n";}int main(){int arr[] = { 1,8,9,3,16,2,18,28};int length = sizeof(arr) / sizeof(arr[0]);/* cout << "插入排序前\n";PrintArray(arr, length);cout << endl<<"开始插入排序"<<endl;insertionSort(arr, length);cout << "插入排序后\n";PrintArray(arr, length);checkArrayIsSort(arr, length);*/cout << "希尔排序前\n";PrintArray(arr, length);cout << endl<<"开始希尔排序"<<endl;ShellSort(arr, length);cout << "希尔排序后\n";PrintArray(arr, length);checkArrayIsSort(arr, length);std::cout << "Hello World!\n";}
运行结果如下
希尔排序完结，撒花