笔记

将数组分成若干个子序列，一开始是 len/2，然后不断除以2，直到1为止，对每个子序列进行插入排序。

注意

不稳定排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 希尔排序
 * */

// 通过交换方式插入
void shell_sort_swap(int a[], int len) {
    for(int gap = len/2; gap > 0; gap /= 2) {
        for(int i = gap; i < len; i++) {
            int pre = i;
            while(pre-gap >= 0 && a[pre] < a[pre-gap]) {
                swap(a[pre], a[pre-gap]);
                pre -= gap;
            }
        }
    }
}

// 通过移动方式插入
void shell_sort_move(int a[], int len) {
    for(int gap = len/2; gap > 0; gap /= 2) {
        for(int i = gap; i < len; i++) {
            int pre = i;
            int cur = a[i];
            while(pre-gap >= 0 && cur < a[pre-gap]) {
                a[pre] = a[pre-gap];
                pre -= gap;
            }
            a[pre] = cur;
        }
    }
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    shell_sort_swap(a, len);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

参考链接

菜鸟教程-希尔排序 (opens new window)

博客园 (opens new window)