今天复习希尔排序的时候,对希尔排序有了新的理解
首先希尔排序是什么:希尔排序(Shell Sort)是一种基于插入排序的排序算法,又称缩小增量排序(Diminishing Increment Sort),是直接插入排序的一种更高效的改进版本。希尔排序通过将数组元素按一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的元素越来越多,当增量减至1时,整个数组恰被分成一组,算法便终止。
希尔排序的核心在于选择初始增量和后续减少增量的策略。常用的增量选择策略有希尔增量(Shell's original increment sequence)、希伯特增量(Hibbard increment sequence)、Sedgewick增量等
说人话就是希尔排序是插入排序的升级,具体内容是把数据分成一个个组,然后每个组进行希尔排序,然后再把整体进行排序,这样尽量把小数据往前放,提高效率。
然后是代码实现:
private static void shellSort(int[] arr) {int length = arr.length;int position = 0;//分组,i是组数也是步长for (int step = length / 2; step > 0; step = step / 2) {//循环每个组第一个元素,然后后续通过第一个元素遍历所有元素for (position = 0; position < step; position++) {insertStep(arr,length,position,step);}} }
/*** @param arr 数组* @param length 长度* @param iPosition 当前位置* @param step 步长,也就是几个组*/ private static void insertStep(int[] arr, int length, int iPosition, int step) {Integer j=0;for (int i = iPosition + step; i < length; i = i + step) {int temp=arr[i];for (j = i-step; j >= 0; j = j - step) {if(arr[j]>arr[i]){arr[j+step]=arr[j];}else{break;}}arr[j+step]=temp;} }
然后很多人在写这部分代码的时候表示很难写清楚,我告诉大家一个好方法:
把这个算法分成两部分,第一部分只负责分组及操作(不具体排序),第二部分只负责排序,
首先第一部分:
分组,我们需要不断分组,比如一共10个数排序,先除以2,分成5份(也就是步长是5,下边回会用),每份下标就是[0,5],[1,6],[2,7],[3,8],[4,9],(注意这是下标,不是值),然后再除以2,分成2份,以此类推,直到分成一份;然后我们要每个组进行操作:
分组:
int length = arr.length;
//这里分组数就是步长(每组下个元素需要跳的步长),大家试着理解一下
for(int step=length/2;step>;step=step/2)
分组后每个组进行操作:
for (int step = length / 2; step > 0; step = step / 2) {
//循环每个组第一个元素,然后后续通过第一个元素遍历所有元素
for (position = 0; position < step; position++)
}
到这里大家先不要管排序的事,只管这里分组和要怎么操作分组。
然后第二部分,排序:
排序就是排序,大家不要管分组的事,只要记得这里有个步长,也就是分几组就行,后边会用
我们分析不分组的插入和分组的插入有什么区别
不分组的时候我们插入每个值的时候是这样:
for(int i=1;i<n;i++)
也就是起始位置是,第一个,然后每次增加的位置是1,也就是i+1
分组的时候,只有间隙不一样,也就是增加的位置不一样,不是+1,而是+step也就是步长:
比如第一个组:
for(int i=0+step;i<n;i=i+step);
当然第二个组就是
for(int i=1+step;i<n;i=i+step);
这个i就是第一个组第几个元素,先记下,后边会说
然后再看插入排序第二层循环,有什么区别:
for(int j=i-1;i>0;j=j-1);
同理,分组后:
for(int j=i-step;i>0;j=j-step);
然后我们将两部分综合起来,发现排序的第一步也就是
for(int i=0+step;i<n;i=i+step);这里i=0+step,这个0就是分组后的第几个元素,也就是分组后的内层循环 for (position = 0; position < step; position++) 里的position,所以我们可以将两部分合起来:
//分组,i是组数也是步长 for (int step = length / 2; step > 0; step = step / 2) {//循环每个组第一个元素,然后后续通过第一个元素遍历所有元素for (position = 0; position < step; position++) {insertStep(arr,length,position,step);} }
排序:
private static void insertStep(int[] arr, int length, int iPosition, int step) {Integer j=0;for (int i = iPosition + step; i < length; i = i + step) {int temp=arr[i];for (j = i-step; j >= 0; j = j - step) {if(arr[j]>arr[i]){arr[j+step]=arr[j];}else{break;}}arr[j+step]=temp;} }
这里iPosition就是分组传过来的参数