希尔排序

发表于 | 分类于 |
字数统计: 498 字 | 阅读时长 ≈ 2 分钟

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定算法。

希尔排序是基于插入排序的以下两点性质提出的改进方法：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思路是：先将整个待排序的记录序列分割成若干字序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

算法步骤

  1. 选择一个增量序列t1，t2，……，tk，其中ti > tj，tk = 1;
  2. 按增量序列的个数k，对序列进行k躺排序；
  3. 每趟排序，根据对应的增量ti，将待排序序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序；
  4. 当增量因子为1时，整个序列作为一个表来处理，表长度即整个序列的长度；

动图演示

shellSort

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T>
void shellSort(T arr[], size_t len) {
    int gap = (int)len / 2;
    for (int g = gap; g > 0; g = g / 2) {
        for (int i = g; i < len; i++) {
            // 对g组数据进行插入排序（注意：此处不是一组一组进行的，而是穿插进行的）
            // 例如：当i=g时，对第一组的第二个数进行插入排序；当i=g+1时，对第二组的第二个数进行插入排序......依次类推
            int j = i;
            while (j >= g && arr[j] < arr[j-g]) {
                std::swap(arr[j], arr[j-g]);
                j = j-g;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    shellSort(arr, sizeof(arr) / sizeof(int));
    return 0;
}