排序算法之希尔排序

  • A+
所属分类:Linux编程
摘要

设待排元素序列有n个,首先取一个整数gap(gap< n)作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列

基本思想
设待排元素序列有n个,首先取一个整数gap(gap< n)作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别进行直接插入排序。然后缩小间隔gap,重复上述的子序列划分和排序工作。知道最后gap等于1时,将所有元素放在同一个序列中排序为止。
至于gap的取法有各种方案。最初Shell提出取gap=⌊n/2⌋ ,gap=⌊gap/2⌋ ,直到gap=1 。但由于直到最后一步,在奇数位置的元素才会与偶数位置的元素进行比较,其效率将很低。后来Knuth提出取gap=⌊gap/3⌋+1。还有人提出都取奇数为好,也有人提出各gap互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

代码
//待排数据存储在数组a中,以及待排序列的左右边界
public void ShellSort(int[] a, int left, int right) {
    int gap = right - left + 1;//划分子序列的间距
    do {
        gap = gap / 3 + 1;
        for (int i = left + gap; i <= right; i++) {
            if (a[i] < a[i - gap]) {
                int j = i - gap;
                int temp = a[i];

                do {
                    a[j + gap] = a[j];
                    j = j - gap;
                } while (j >= left && temp < a[j]);

                a[j + gap] = temp;
            }
        } 
    } while (gap > 1);
}

weinxin
欢迎加入中国站长博客之家
本站的所有资源都会上传分享到博客之家,希望大家互相学习交流进步。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: