# 希尔排序

是一个分组插入排序算法,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL.Shell 于 1959 年提出而得名。

# 基本思想

先追求表中的元素部分有序,再逐渐逼近全局有序。

  1. 先将待排序表分割成若干子表,对各个子表分别进行直接插入排序。缩小增量,再次分割子表,对子表进行直接插入排序,直到增量为 1,排序完成。
//举例
DL. Shel建议的增量序列为:n/2,n/4,…,1,称为希尔增量,最后一个增量值必须为1int arr={9,1,2,5,7,4,8,6,3,5};
//arr长度为10,第一次增量为10/2=5
//分成5组,每组两个元素,分别进行直接插入排序

//第一次分组为 {9,4} {1,8} {2,6} {5,3} {7,5}
//第一次分组排序后为 {4,9} {1,8} {2,6} {3,5} {5,7}
//第一次排序为 {4,1,2,3,5,9,8,6,5,7}

//第二次增量为5/2=2
//分成2组,每组5个元素,分别进行直接插入排序
//第二次分组为 {4,2,5,8,5} {1,3,9,6,7}
//第二次分组排序后为 {2,4,5,5,8} {1,3,6,7,9}
//第二次排序为 {2,1,4,3,5,6,5,7,8,9}

//第三次增量为2/2=1
//分成1组,每组10个元素,分别进行直接插入排序
//第三次分组为 {2,1,4,3,5,6,5,7,8,9}
//第三次分组排序后为 {1,2,3,4,5,5,6,7,8,9}
//第三次排序为 {1,2,3,4,5,5,6,7,8,9}

//代码实现
void shellSort(int *arr, int length) {
    int i, j, temp, gap;
    // 增量每次都/2 直到为1
    for (gap = length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素开始,因为前面的元素默认是有序的
        for (i = gap; i < length; ++i) {
            // 如果当前元素比前一个元素小,那么就需要将当前元素插入到前面的有序序列中
            if (arr[i] < arr[i - gap]) {
                temp = arr[i];
                // 从当前元素的前一个元素开始,依次和当前元素比较,如果比当前元素大,那么就将该元素后移gap位

                // 如果是多个分组的话 每次循环会切换一个分组 有点不好理解
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
    }
}

//第二种实现方式 (这种方式比较好理解 每次插入排序都是 先处理每个分组的所有元素 在处理下一个分组)
void shellSort1(int *arr, int length) {
    int i = 0, j, temp, gap;
    for (gap = length / 2; gap > 0; gap /= 2) {
      // 这里的i++是为了每次循环都切换一个分组
        i += 1;
        for (j = i + gap; j < length; j += gap) {
            if (arr[j] < arr[j - gap]) {
                temp = arr[j];
                int k = j - gap;
                // 将当前分组的所有元素都对比一遍 确保当前分组的所有元素都是有序的
                while (k >= 0 && arr[k] > temp) {
                    arr[k + gap] = arr[k];
                    k -= gap;
                }
                arr[k + gap] = temp;
            }
        }
    }
}
Copied!

# 算法分析

# 时间复杂度

和增量序列有关, 不太好计算确切的时间复杂度, 总体是优于直接插入排序的

最坏情况下的时间复杂度为 O(n^2)

  • 和插入排序一样, 所有都是逆序的

# 空间复杂度

O(1) 和插入排序一样

# 稳定性

不稳定

  • 例如: 5 8 5 2 9 这样一组数据, 第一次增量为 2, 5 和 5 交换了位置, 所以不稳定