希尔排序算法

//排成递增序列
void shell_sort(int *a, int n){
    int gap = n/2;
    //每一波gap缩一半
    for(;gap>0; gap/=2){
        //按gap的间隔，一直往后移动
        for(int i = 0; i < n-gap; i++){
            int tmp = i;
            //发现前面节点大于后面节点，则互换
            //往左换的那个值要不停地以gap互换，直到[0-i]的、间距为gap的子串为递增序列
            while(tmp>=0 && a[tmp] > a[tmp+gap]){
                swap(a[tmp],a[tmp+gap]);
                tmp-=gap;
            }
        }
    }
}

这个视频有每一步的过程和讲解

完整代码

在线测试运行结果：click

#include <iostream>
using namespace std;
void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void shell_sort(int *a, int n){
    int gap = n/2;
    for(; gap>0; gap/=2){
        for(int i = 0; i < n-gap; i++){
            int tmp = i;
            while(tmp>=0 && a[tmp] > a[tmp+gap]){
                swap(a[tmp],a[tmp+gap]);
                tmp-=gap;
            }
        }
    }
}

int main()
{
    int a[] = {8,3,6,4,2,9,1,5,7};
    int n = sizeof(a)/sizeof(a[0]);
    shell_sort(a,n);
    for(auto s:a){
        cout << s << ' ';
    }
}