(兔C残篇)希尔排序的代码实现与讲解

本文主要是介绍(兔C残篇)希尔排序的代码实现与讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 概念

希尔排序 又称缩小增量排序。是对直接插入排序的一种优化。

它的基本思想是：
先将原表按增量 ht 进行分解，每个子文件按照直接插入法排序。同样，用下一个增量继续 ht /2 将文件再分为子文件，再按照直接插入法进行排序。直到 ht = 1 时，整个文件便排好序。

其关键在于，选择好适量的增量，例如 9 - 3 ，通过三重循环来实现。

1.1 傻瓜式指南

理解了吗？不理解没关系，我们有傻瓜指南。
记得我们上一文聊天的话题么？直接插入排序，我们先不管别的内容，想一想上一文的话题，直接插入排序。

好的，你已经想起来了，直接插入排序，那 直接插入排序 其实就是 希尔排序的最后一轮排序。
乱么，迷糊了么，不乱！不迷糊！

希尔排序的方式与直接插入排序相同，只不过是按照自己的规律批量进行插入，其插入方式还是直接插入排序，也可以理解成，分批分量的进行直接插入排序，而不是哐当一下，直接一次的直接插入。

话题在转换开头段落，就算你现在设置了规律，按照自己设置的增量，进行分批分量的直接插入排序，那你最后的一次分批分量直接插入，不还是普通的直接插入排序么。

好的，你已经明白了，兔C残篇开篇招式，不晓得也没事，你在重复做一次刚才的两分钟用功，反复直明了即可。

1.2 举例说明

现在有一个数组
int arr[] = {60,30,50,20,10,80,40,70};

如 设置增量 为 4，8用4作为除数可以除尽，当然这不是最佳的处理方案，我们这里只是先进行举例说明，除4的话，那第一轮就需要第1个元素和加4个步数等于5也就是10这个元素进行比较和交换，同轮比较中，后面元素依次下推，
即：
第一轮：
60 10
30 80
50 40
20 70

第一轮会将以上顺序进行比较和交换，然后排序出一个新的大致顺序的内容。
当然后面还有轮次进行，那，具体需要多少轮，我们后面在继续说明，这里先明白这个概念，在往下继续推到步骤。

2. 过程推导第一步

刚才我们说过，希尔排序是直接插入排序的一个优化，而希尔排序的最终一轮次的排序就是个直接插入排序，那我们这里先把直接插入排序写出来，复习一下直接插入排序，然后在从这个直接插入排序上进行条件的改变和增量条件的设置。

//直接插入排序的复习
import java.util.Arrays;
public class ReturnArrayValue{public static void main(String[] args){int arr[] = {60,30,50,20,10,80,40,70};//调用直接排序的方法arraySort(arr);System.out.println(Arrays.toString(arr));}public static void arraySort(int arr[]){for(int i =1; i < arr.length; i++){for(int j = i; j > 0; j--){if (arr[j] < arr[j-1]) {arrayValue(arr, j, j - 1);}}}}public static void arrayValue(int[] arr,int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

2.1 直接插入排序的复习

1. 理论概念：将一个记录插入到一个长度为m的有序列表中。使其结果仍保持有序。
2. 循环的使用：外层循环依然是控制排序的轮数，内层循环依然是控制当前轮次中的元素操作，不同的是直接插入排序，可以使用while循环，也可以使用for的嵌套。

• 使用while，要自己设置下标的指向变量，用其指向控制元素
• 使用for，需要自己改变条件，单独使用if控制元素的交换，是不够的，因为经插入之后，结束了当前轮次的话，下一个轮次的比较的指针的位置是需要改变的，因为此时已经重新经过排序了，所以要有–的动作，但是减减的动作，不能小于零，小于零的话，就成了负数，会造成ArrayIndexOutOfBoundsException

3. – 动作，减减的动作是必然的，因为排序好之后，不能在从后移了的元素位置开始吧，所以一定要减减的。

2.2 第一步，初改造

现在开始改造

//直接对这个方法进行改造即可，因为算法的相关操作已经抽取成单独的方法public static void arraySort(int arr[]){//设置增量int h = 4;/*循环的下标起始值设置为==设置的增量，也就是 j = h下标的活动区间范围设置在 大于增量-1，也就是 j > h-1每轮条件满足下，下标的动作设置成-=增量，也就是j-=h*/for(int j = h; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) { //j -4 是指针指向的与前一个数满足步数为4的数arrayValue(arr, j, j - h);        }}}

然后我们来看一下此次执行的结果

我们会看到数组的执行结果发生了变化。
第一个元素和区间步数4的元素交换了位置，也就是第一个元素和第五个元素的位置。10和60
此时我们设置好内层循环，对元素的控制，在今天一层循环嵌套，让其满足增量区间的数都进行交换

public static void arraySort(int arr[]){//设置增量int h = 4;for(int i =h; i< arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) { //j -4 是指针指向的与前一个数满足步数为4的数arrayValue(arr, j, j - h);        }}}}

我们在来看一下按照 增量公式的轮数，执行第一轮后的结果

此时我们会看到，满足步数的数字，都按照我们设置的小数在前的规律进行了位置的交换。此时我们就完成了希尔排序的初步掌握，也就是按照 ht 进行分解和排序，接下来我们继续了解，ht/2的下一轮分解和排序。

3. 第二步改造

我们上面就说过，希尔排序，其实是对直接插入排序的优化，他的优化说白了，也就是将直接的一个一个插入，改变成，分批分量的进行插入。按照这个理解，第一步我们：我们有八个数，除2进行拆分，也就是每四个数进行交换，那第二步，我们继续做拆分，也就是4继续往下 / 2。
如果感觉有点模糊，可能是我的文字表达的不够清楚，下面我们来写代码，

public static void arraySort(int arr[]){//设置增量int h = 4;for(int i =h; i < arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) { //j -4 是指针指向的与前一个数满足步数为4的数arrayValue(arr, j, j - h);}}}h = 2;for(int i =h; i < arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) { arrayValue(arr, j, j - h);}}}}

然后我们在来看一下执行之后的结果：

4. 第三步改造

经过第二步改造之后，发现我们的增量值还可以进行优化，下面我们继续第三轮的改造

public static void arraySort(int arr[]){//设置增量int h = 4;for(int i =h; i < arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) { //j -4 是指针指向的与前一个数满足步数为4的数arrayValue(arr, j, j - h);}}}h = 2;for(int i =h; i < arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) {arrayValue(arr, j, j - h);}}}h = 1;for(int i =h; i < arr.length; i++){for(int j = i; j > h -1 ; j-=h){if (arr[j] < arr[j-h]) {arrayValue(arr, j, j - h);}}}}

到达此处，我们便完成了一个简单的希尔排序，那我们来看一下，我们希尔排序的执行结果

5. 希尔排序的优化方案

5.1希尔排序的重复代码优化

public static void arraySort(int arr[]){
//这里的优化，就是将每次重新赋值增量后的循环不在重写复写，让增量值自行运动
//在嵌套一层循环，用于控制增量值
for(int h = 4; h >0; h/=2){for(int i = h; i <arr.length; i++){for(int j =i; j > h-1; j-=h){if(arr[j] < arr[j -h]){int temp = arr[j];arr[j] =arr[j-h];arr[j-h] = temp;}}}}
}//应该没问题，手动写在csdn编辑博文文档的，自己没运行尝试。

5.2 增量值的优化

其实5.1的优化，等同于他的标题，就只是对重复代码的优化，虽然增量值是自己循环运动的，但这并不是对增量值的优化，就例如现在要增加数组的容量，那现在的增量值，是按照8个容量进行设置计算的，那增加了容量这个计算还可取么？
如果增加了容量，会不会影响运行效率？会不会影响元素交换的计算？
那这一步，我们对增量值进行优化。

//其实也就是把控制增量 h变量的值，不写死，不写成4
//按照希尔排序的思想去取值：也就是，在第一次选取数组长度一半进行交换之后，不断减半
for(int h =arr.length/2; h>0; h/=2){}

6. 希尔排序的最终实现方案

是最终的，也是最佳的。

public static void arraySort(int arr[]){//设置间隔，利用克努特序列，进行间隔的增长变化int spike =1;while(spike < arr.length /3){spike = spike *3+1;}//然后在开始排序的计算for(int h = spike ; h >0; h=(h-1)/3){for(int i = h; i <arr.length; i++){for(int j =i; j > h-1; j-=h){if(arr[j] < arr[j -h]){int temp = arr[j];arr[j] =arr[j-h];arr[j-h] = temp;}}}}
}

7. 最终实现方案的说明

spike 变量 是定义的增量，值为1，然后让其进入循环，按照 spike *3 +1 的公式去循环。

下面嵌套的三层循环，第一层for是用于控制增量的变化，第二次for用于控制循环的轮次，第三层for用于控制执行轮次内的元素

这篇关于(兔C残篇)希尔排序的代码实现与讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---