数据结构-希尔排序

前言

希尔排序，又称“缩小增量排序”，也是插入排序的一种，是插入排序的一种更高效的改进版本

原理

在使用直接插入排序算法时，如果表中的记录只有个别的是无序的，多数保持有序，这种情况下算法的效率也会比较高；除此之外，如果需要排序的记录总量很少，该算法的效率同样会很高。希尔排序就是从这两点出发对算法进行改进得到的排序算法。

希尔排序的具体实现思路是：先将整个记录表分割成若干部分，分别进行直接插入排序，然后再对整个记录表进行一次直接插入排序。

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

来源：https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序动画过程解释

首先，选择增量 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式

初始增量为 gap = 10/2 = 5，整个数组分成了 5 组

按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】

对这分开的 5 组分别使用

上节所讲的插入排序

结果可以发现，这五组中的相对小元素都被调到前面了

缩小增量 gap = 5/2 = 2，整个数组分成了 2 组

【 3 , 1 , 0 , 9 , 7 】，【 5 , 6 , 8 , 4 , 2 】

对这分开的 2 组分别使用上节所讲的插入排序

此时整个数组的有序性是很明显的

再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组

【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0 】

此时，只需要对以上数列进行简单的微调，不需要大量的移动操作即可完成整个数组的排序

代码实现

C++代码

排序数据 演示

//gap = gap/2
//  0   1   2   3   4  5   6    7   8  9   数据下标
// 49  33  65  97  76  13  27  49  55  04  排序数据
// 步长 == 数组长度/2 == 5  然后插入排序算法
//首先按照步长去分组
// 49                  13
//     33                  27
//         65                  49
//             97                   55
//                 76                   04

//然后对每组进行排序
// 13                  49
//     27                  33
//         49                   65
//              55                  97
//                  04                  76

//当前数组变为
// 13  27  49   55  04 49  33   65  97  76

// 步长 == 上次步长/2 == 2
//按照步长去分组
// 13      49       04     33       97
//     27       55     49       65      76
//然后对每组进行插入排序
// 04      13       33     49       97
//     27       49     55       65      76
// 当前数组变为
// 04  27  13   49  33 55  49   65  97  76
//步长 == 上次步长/2 == 1
//然后对数组进行插入排序
// 04  13  27   33  49 49  55   65  76  97
//

代码

#pragma mark --希尔排序 交换
void shellExchangeInsertion_sort(int array[], int last) {
    int times = 0;
    int addGap =2;
    //分组  直到为1时 分组结束
    for (int gap = last/addGap; gap >= 1; gap = gap/addGap) {
        if (gap < addGap){
            gap = 1;
        }
        //对分组的数据进行插入排序
        for (int i = gap; i < last; i++) {

            for (int j = i - gap; j >= 0 && array[j] > array[j + gap]; j = j - gap) {
                int temp = array[j];
                array[j] = array[j + gap];
                array[j+ gap] = temp;
                times ++;
            }
        }
        
    }
}

void shellInsertion_sort(int array[], int last) {
    int times = 0;
    //分组  直到为1时 分组结束
    for (int gap = last/2; gap >= 1; gap = gap/2) {
        //对分组的数据进行插入排序
        for (int i = gap; i < last; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0 && array[j] > temp; j = j - gap) {
                array[j + gap] = array[j];
                times ++;
            }
            array[j+ gap] = temp;
        }
    }
}