willcool4ever • O(n^(1.3—2))排序：希尔

#include <iostream>

using namespace std;

void PutArray(int *array, int size) {

//    cout << " Array:";

    for (int i = 0; i < size; ++i) {
        cout << array[i] << "  ";
    }

    cout << endl;

}

void ShellSort(int *array, int size) {

    int gap = size;

    do {
        gap = gap / 3 + 1;

        for (int i = gap; i < size; i += gap) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 && tmp < array[j]; j -= gap) {
                array[j + gap] = array[j];
            }
            array[j + gap] = tmp;

        }

    } while (gap > 1);

}

int main() {

    int array[7] = {23, -22, 241, 23, 640, 0, 50};
    // int array[2] = {23, -22};

    int size = sizeof(array) / sizeof(*array);

    PutArray(array, size);

    ShellSort(array, size);

    PutArray(array, size);

    return 0;
}