Java教程

八大排序算法~希尔排序【改良版的直接插入排序】

本文主要是介绍八大排序算法~希尔排序【改良版的直接插入排序】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

八大排序算法~希尔排序【改良版的直接插入排序】

直接插入排序文章:https://www.cnblogs.com/shan333/p/15043607.html

1,为什么需要改良直接插入排序,以及改良后的希尔排序实现了什么效果?

希尔排序:对直接插入排序的改良版,原来的直接排序面对大量数的效率太低了,需要先对待排序数据进行处理,(希尔排序就是通过取一定间隔进行数据处理,

使得小的数基本在前边,大的数基本在后边,使得整体的数字看起来是基本有序的

2,如何实现希尔排序?

(1)希尔排序通过取某个“间隔”对原整体的数据进行分组

【不断以 某间隔划分有序区跟无序区,然后遍历无序区数据,跟有序区数据比较,找合适位置】。然后这个“间隔”缩小,再分组;“间隔”再缩小,再分组直到“间隔”为1,进行最后的分组就是数据本身的整体了。(间隔的取值是整体数据的一半,即d=n/2)

(2)然后小组内部需要直接排序

 (3)图解:引自《数据结构c语言版严蔚敏PPT.pdf ~

 https://wenku.baidu.com/view/9e73cb8b69dc5022aaea00c1.html》

 

 

3,代码逻辑分析:

第一层循环(间隔循环地缩小,直到间隔为1):for(int i = n/2; i >=1; i = i/2)

外循环(不断地取出无序区的数):for(j = 1 + i; j >=n; j++)
 ~1+i 无序区离有序区的距离是i,初始时,有序区只在第一个位置

内循环(取出的数不断地与有序区做比较,找到一个合适位置插入):for(k = j – i; r[0] < r [k] && k > 0; k = k – i)  
~有序区离无序区的距离是i,无序区第一个数距离i前就是有序区的最后一个数

 

4,直接上代码,分析如上:

for(int i = n/2; i >=1; i = i/2){
    for(j = 1 + i; j >=n; j++){
       arr[0] = arr[j];            //哨兵元素,作用:可以不用再添加额外的辅助空间;省去对数组下标越界的判断
        for(k = j – i; r[0] < r [k] && k > 0; k = k – i){    //边比较,边移动数组空间
         arr[k + i] = arr[k];
     }
    arr[k + i] = arr[0];
  }
}

 

这篇关于八大排序算法~希尔排序【改良版的直接插入排序】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!