排序算法之希尔排序

宜家博客
宜家博客
宜家博客
39146
文章
0
评论
2019年8月14日00:45:44 评论 23 682字阅读2分16秒

基本思想
设待排元素序列有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
欢迎加入中国站长博客之家
本站的所有资源都会上传分享到博客之家,希望大家互相学习交流进步。
宜家博客
进程控制块的task_struct结构 Linux编程

进程控制块的task_struct结构

》进程控制块       在linux中进程信息存放在叫做进程控制块的数据结构中,每个进程在内核中都有⼀个进程控制块(PCB)来维护进程相关的信息,Linux内核的 进程...
C語言 rand函数 进阶探讨与实现 Linux编程

C語言 rand函数 进阶探讨与实现

C语言中随机函数应用 可能大家都知道C语言中的随机函数random,可是random函数并不是ANSI C标准,所以说,random函数不能在gcc,vc等编译器下编译通过。那么怎么实现C语言中的随机...
Python多进程中使用pool Linux编程

Python多进程中使用pool

Python 多进程中使用pool,pool中指定每次运行几个进程,当其中一个进程结束完毕后,会加入新的进程 #!/usr/bin/env python#coding: utf-8import mul...
Java synchronized 总结 Linux编程

Java synchronized 总结

在Java开发的时候经常会用到关键字synchronized来对代码进行同步,在使用的过程中,对于synchronized确不是很熟悉,最近在看Spring源码时,发现有不少地方都用到同步,因此,趁此...
匿名

发表评论

匿名网友 填写信息

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