[算法] 希尔排序

萧闫子

插入排序速度慢，因为它进行的唯一交换涉及到邻接项，因此，在数组中，项只能一次移动一个位置。例如，如果最小键刚好就在数组的末端，则需要N步将它移到位。希尔排序（Shellsort）是插入排序的简单扩展，它允许离得很远的元素进行交换，所以提高了速度。
         希尔排序的思想是，重排文件后让它具有以下性质：每隔h取一个元素（从任意处开始），得到一个有序文件。这种文件称做h-有序（h-sorted）。换一个角度看，一个h有序文件是h个独立的有序文件，它们交叉排列在一起。当h较大时，通过h排序，我们可以在数组中长距离移动元素，因此，使得对于更小的h，更容易进行h-排序。对于任意的h值序列（以1结尾），使用这样的过程都生成一个有序文件。这就是希尔排序的实质。
         一种实现希尔排序的方式是，对每个h分别使用插入排序独立排序所有h个子文件。尽管这个过程已经很简单，但我们甚至还可以使用更简单的方式，因为这些子文件是独立的。当使用h-排序文件时，将较大元素移到右边，然后在h-子文件的前面元素中插入。

#include <iostream> using namespace std; void shellSort(int arr[, int n) {     int i, j;     int key;     int h;     for (h = 1; h <= (n-1)/9; h = 3*h + 1)         ;     for (; h > 0; h /= 3)         for (i = h; i < n; i++)         {             key = arr[i;             j = i;             while ((j >= h) && (arr[j-h > key))             {                 arr[j = arr[j-h;                 j -= h;             }             arr[j = key;         } } int main() {     int arr[15 = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753};     int i;         cout << "Original array" << endl;     for (i = 0; i < 15; i++)         cout << arr[i << " ";     cout << endl << endl;         shellSort(arr, 15);     cout << "Sorted array" << endl;     for (i = 0; i < 15; i++)         cout << arr[i << " ";     cout << endl;     return 0; }