数据结构-排序（三）希尔排序

1、算法思想

算法思想：

先追求表中元素部分有序，再逐渐逼近全局有序，先将待排序表分割成若干形如 $L[i, i + d, i + 2d,…, i + kd]$ 的“特殊”子表，对各个子表分别进行直接插入排序，缩小增量d，重复上述过程，直到d = 1为止。 第一趟一般d = n / 2，往后 d = d / 2 。每次将增量缩小⼀半

例子：

对数组【12 28 20 50 48 1 5 28】进行排序

第一趟

第二趟

第三趟

2、代码实现

/**
 * 希尔排序
 * @param arr
 * @param n
 */
void ShellSort(int arr[], int n) {
    int d, j;
    for (d = n / 2; d >= 1; d = d / 2) { //步长变化
        for (int i = d + 1; i <= n ; ++i) {
            if (arr[i] < arr[i - d]) { //arr[i]插入有序增量表
                arr[0] = arr[i]; //暂存
                for (j = i - d; j > 0 && arr[0] < arr[j] ; j -= d) {
                    arr[j + d] = arr[j]; //记录后移，查找插入位置
                }
                arr[j + d] = arr[0]; //插入数据
            }//if
        }//for
    }//for
}

3、算法复杂度分析

时间复杂度：和增量序列 d1, d2, d3… 的选择有关，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为 $O(n^2)$，当n在某个范围内时，可达$O(n^{1.3})$

空间复杂度： $O(1)$

稳定性：不稳定