[数据结构与算法]希尔排序——C++实现

1. 简介

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
我写过直接插入排序了，可参考这请点击这里。
希尔排序和直接插入排序的区别在于希尔排序对数组的步长有一定的要求，不想直接插入的步长恒为1。
希尔排序原理图：

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int arraysize = 15;
    int array[15] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
// gap是此次循环中，数组被分为小数组的组数，也是每个数组中每个数的步长。int避免小数出现。
    for(int gap=int(arraysize/2);gap>=1;gap=int(gap/2)){  
    // 这部分可参考直接插入的代码
        for(int i=gap;i<arraysize;i++){
            int value = array[i];
            for(int j=i-gap;j>=0;j-=gap){
                if(array[j]>value){
                    int index = j+gap;
                    array[index] = array[j];
                    array[j] = value;
                }
            }
        }
        for(int n=0;n<arraysize;n++){
            cout << array[n] << " ";
            }
            cout << '\n'  << endl;
    }


    cout << "end" << endl;
    return 0;
}

运行结果：

有问题评论区见~欢迎指出问题。