【数据结构与算法】希尔排序 python和c++实现

算法思路
每一次:固定间隔把数据分组,每一组进行排序
每次比上次选取更小的间隔分组,再每组排序,直到间隔为1

代码
c++:(越看越不明白了,后看)

int gap = length;//length是数组的元素个数,gap是间隔长度

    while (gap>1){

        gap = gap/3 +1;///其实就是生成一个间隔序列

        for (int i = gap; i<length; i+=gap) {

            int current = arr[i];//先把arr[i]中放的东西保存在current中

            int preIndex = i - gap;//上一个同组数据

            while (preIndex >= 0 && arr[preIndex]>current) {//如果同组上个数据大于当前数据

                arr[i]  = arr[preIndex];//就是把这两个格子里的数据调换了位置

                //注意此时current还存着最后的数据

                preIndex -= gap;//再找同组上上个数据

            }

            arr[preIndex+gap] = current;//当找到每组第一个数据时,把current放进去

        }

    }

py:

import numpy as np#import这个为了后面生成测试数据

def shellSort(arr):

    N = len(arr)

    increment = N//2

    while increment > 0:

        i = increment

        while i < N:

            j = i - increment#同组上个数的索引

            tmp = arr[i]#存下arr[i]

            while j >= 0 and arr[j] > tmp:

                arr[j + increment] = arr[j]#这里是把arr[j]存入同组下个数据中了

                j -= increment

            arr[j + increment] = tmp

            i += 1

        increment //= 2

    return arr

if __name__ == '__main__':

    #随机生成20个20以内的数,乱序

    nums=np.random.permutation(20)

    print(shellSort(nums))

【数据结构与算法】希尔排序 python和c++实现的相关教程结束。