1、希尔排序的效能简介

希尔排序是插入排序的改进型,也因此,它的空间复杂度是O(1)。不过有趣的是,希尔排序的平均时间复杂度计与其增量有关,算起来较为复杂,dalao们的研究认为是O[n^(1.3 ~ 2)]之间。

其实相比于快排、归并、堆排这些平均之间复杂度为O [ nlog(n) ]的线性对数阶排序,希尔排序并不占优势(因为希排有亚二次时间界),但作为第一批突破第二次时间屏障的算法之一的存在,我jio得还是要重温一下经典(其实是面试爱考ORZ)。


2、本文中的一些定义

2.1——有序区与无序区

在本文中,对于一个任意一个无序的的序列:

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]

我们把这个序列从逻辑上分为有序区和无序区,并默认在开始排序前,第一个元素为有序区,其余为无序区。

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]  (绿色为有序区,红色为无序区)

在我们对其逐渐有序化的时候,依次从无序区中取出其第一个元素并插入有序区:

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]   (有序区会增加,无序区会减少,同时无序区第一个元素前的元素必然在有序区)

2.2——按增量(gap)划分多个序列

一个序列可以按增量(gap)在逻辑上划分为gap个序列(关于的gap的取值,第一次取序列长度一半,之后再取用gap前要除2):

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]   gap = 9/2 = 4 ,即在逻辑上分成4组小序列,同一小序列内的、逻辑上相邻的元素,在序列中的小标差为gap:

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]   比如红色小序列应该是[  5, 7, 3 ],它们在原序列中的小标为0、4、8,相差为gap


 

3、希尔排序的流程 

第一步,在逻辑上按gap将序列划分为gap个小序列。(第一次时取增量(gap)为序列长度的一半)

如, [ 569874123

第二步,一个指针从序列的无序区(由各个小序列的无序区组成)由左向右遍历,遍历到的元素,将其插入对应小序列的有序区”

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]  指针最开始指向序列无序区第一个即7,7在第一个小序列里,把它插入第一个小序列的有序区,

如, [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]  指针+1指向无序区新的第一个元素4,4在第二个小序列里, 把它插入第二个小序列的有序区,

如, [ 5, 4, 9, 8, 7, 61, 2, 3 ]  注意,这里是插入到第二个小序列的有序区,所以4、6换位,然后指针+1。。。。操作同上

第三步,gap/=2后若小于1就结束了,否则回调第一步。


4、代码

 

 1 import java.util.Arrays;
 2 public class Main {
 3     public static void shellSort(int[] arr) {
 4         int temp;
 5         //控制增量(gap),增量将不断/2直到小于1。(序列会在逻辑上按gap划分为gap个小序列)
 6         for (int gap = arr.length/2; gap >0; gap/=2) {
 7             //遍历无序区(最开始>=gap的下标都属于无序区)
 8             //变量p_in_unorder始终指向当前序列的无序区的第一个元素的下标
 9             for (int p_in_unorder = gap; p_in_unorder < arr.length; p_in_unorder++) {
10                 /*
11                 *p_in_order是小序列有序区内的下标指针
12                 *p_in_unorder - gap 是当前小序列有序区的最后一个
13                 *把当前无序区第一个元素插入对应小序列有序区
14                 */
15                 for (int p_in_order = p_in_unorder-gap ; p_in_order >= 0 ; p_in_order-=gap) {
16                     if(arr[p_in_order]>arr[p_in_order+gap]){
17                         temp = arr[p_in_order];
18                         arr[p_in_order] = arr[p_in_order+gap];
19                         arr[p_in_order+gap] = temp;
20                     }
21                 }
22             }
23         }
24     }
25 
26     public static void main(String[] args) {
27         int[] arr = new int[]{5,6,9,8,7,4,1,2,3};
28         shellSort(arr);
29         System.out.println(Arrays.toString(arr));
30     }
31 }

 

最后,如果小伙伴觉得这篇博文对你有帮助的话,就点个推荐吧

内容来源于网络如有侵权请私信删除