希尔排序 Shell sort

希尔排序 Shell sort

我认为希尔排序的思想是比较另类的,属于插入排序的一个变种。由于插入排序在插入新数时需要遍历整个序列,希尔排序针对这种情况做出了修改:将整个序列分为几部分分别进行插入排序,而希尔排序的分组比较有意思,并不是像切肉一样简单分为几个连续的部分,而是设定了一个小于数组长度的跨度d(d通常小于数组长度/2),每隔d长度的为一组。假设共有10个数,d为3的情况,分组即为{0,3,6,9},{1,4,7},{2,5,8}这样三组。这一步的优点一是,由于每个子序列变短了,虽然总的需要排序的个数不变,但移动次数减少;优点二是可以将较小的数尽量快的放到整个数组的前面;例如按上面的分组第一次排序后,下标为0,1,2的元素均为个分组中最小的。然后将d缩短,即子序列变短,再对每部分进行插入排序,直到d=1时,无需排序,则完成整个序列的排序。

希尔排序

  1. 设定初始跨度d=array.length/2,相隔相同跨度的为一组,进行插入排序。
  2. 缩小跨度d,d=d/2,再此进行分组与插入排序。
  3. d=1时结束。
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
int d = array.length;
while (d > 1) {  // 控制跨度
    d = d / 2;  // 每次跨度缩小一半
    for (int start = 0; start < d; start++) {  // 每个分组的起点
        for (int currPos = start + d; currPos < array.length; currPos = currPos + d) {  // 此处开始为通常的插入排序,只是由于跨度分组的不同,循环的步长会有不同。
            int comparePos = currPos - d;
            int current = array[currPos];
            while (comparePos >= 0 && array[comparePos] > current) {
                array[comparePos + d] = array[comparePos];
                comparePos = comparePos - d;
            }
            array[comparePos + d] = current;
        }
    }
}

发表评论