希尔排序

#include <iostream>

using namespace std;

void shellSort(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    shellSort(arr, length);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

void shellSort(int arr[], int n)
{
    int d, i, j;
    //arr[0]为暂存单元
    for (d = n / 2; d > 0; d /= 2)  //d为步长
    {
        for (i = d + 1; i <= n; i++)    //从子表中第二个元素开始
            if(arr[i] < arr[i - d])     //小于子序列前一项
            {
                arr[0] = arr[i];    //暂存待插入元素
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];    //向后移动，为待插入元素腾出空位
                arr[j + d] = arr[0];    //插入暂存元素
            }
    }
}