排序算法4 希尔排序

    插入排序速度慢，因为它进行的唯一交换涉及到邻接项，因此，在数组中，项只能一次移动一个位置。例如，如果最小键刚好就在数组的末端，则需要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;
}