排序算法学习(2)-希尔排序

希尔排序

希尔排序是简单排序中插入排序的一种更高效的改进版本,但是直接插入排序是稳定的,希尔排序是不稳定的。

其基本思路是:

  • 假设数组长度为 n ,假设初始步长为 k (1<k<n ,k=1即为直接插入排序)
  • 根据步长 k 对数组进行分组,第一组为:第 1 个数、第 1+k 个数 ... ,第二组为:第 2 个数、第 2+k 个数... ,...... ,第 k 组为:第 k 个数、第 k+k 个数 ...
  • 如此对每个组进行插入排序;接下来,将步长设为 k/2 ,同样的进行分组,对每一组进行插入排序
  • 重复这个步骤直到步长为 1 ,对整个数组进行一次插入排序后,排序完成。

示意图

ShellSort_1.png

在示例中先对数组进行 4 分组,每组进行一次插入排序,再进行 2 分组的插入排序,最后步长为 1 ,进行一次普通的插入排序。

虽然在示意图中对每一分组单独进行了插入排序,但这只是便于理解,实际上,可以在数组的一次遍历过程中对所有分组进行插入排序。下图是 4 分组插入排序的示意图。

ShellSort_2.png

示例代码

public class ShellSort {
    public static void sort(int[] arr) {
        for (int i = arr.length >> 1; i > 0; i >>= 1) {
            insertSort(arr, i);
        }
    }
    private static void insertSort(int[] arr, int delta) {
        for (int i = delta; i < arr.length; i ++) {
            int j = i;
            int temp = arr[j];
            while (j >= delta && temp < arr[j-delta]) {
                arr[j] = arr[j-delta];
                j-=delta;
            }
            arr[j] = temp;
        }
    }
}

步长的设置

毫无疑问,希尔排序与直接插入排序最大的不同在于设置了步长序列,在上面的代码中,设置的步长序列直接是上一个步长除以 2 直到步长为 1 ,但实际上,效率最高的步长序列并非是上述结构,不同的序列的排序快慢不同,可以阅读相关资料,得知其他步长的具体细节。

时间复杂度和空间复杂度

由于不同步长会影响到排序算法的时间复杂度,所以无法确定算法的平均时间复杂度,不过根据维基百科上所说其时间复杂度在 $O(nlog_2n)$ 和 $O(n^2)$ 之间。

而空间复杂度,由于没有用到额外空间,因此其空间复杂度为 $O(1)$ 。

稳定性

虽然直接插入排序是稳定的,但是由于希尔排序通过步长分割数组,在分组排序中其自然顺序会被打乱,因此他是不稳定排序。

评论

暂无评论