希尔排序

程序员文章站 2022-06-04 17:54:12

...

#include<iostream>
using namespace std;

void shell_sort(int arr[], int len) {
    int increment, i, j;
    increment = len;
    do {
        increment = increment / 3 + 1;  //当 increment = 10 / 3 + 1 = 4时， 意味着数组被分成4组，且最后一个增量必须为1             
        for (i = increment; i < len; i++) {
            int temp = arr[i];
            //每组内分别进行直接插入排序
            for (j = i - increment; j >= 0 && temp < arr[j]; j = j - increment) {
                arr[j + increment] = arr[j];
            }           
            arr[j + increment] = temp;
        }
    } while (increment > 1);
}



int main()
{
    int arr[10] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    shell_sort(arr, 10);
    for (int i = 0; i < 10; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}