作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器------牛客网
文章目录
- 算法思想
希尔排序是一种基于插入排序的快速的排序算法。简单插入排序对大规模乱序数组很慢，元素之恩那个一点一点从数组一端移动到另一端
为了解决这个问题，希尔排序改进了插入排序，称为缩小增量排序，该算法也是突破O（n*n）的第一批算法之一
主要思想是：把数据按照一定增量分组，对每组使用直接插入排序算法，然后缩小增量继续分组排序，随着增量逐渐减小，每组包含的关键词越来越多，增量减小至1时，整个数组被分为一组，再次排序，完成整个数组的排序，这个不断缩小的增量构成了增量序列
常用的增量序列有：
- 算法图解
int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};
以数组array排升序为例：
希尔排序图解
第一个增量为6，则原始数组被分为6组，组内的每个元素下标之差为6，然后对这6组进行插入排序
第二个增量为3，则第一次排序后数组被分为三组，组内每个元素之间数组下标之差为3 ，这三组分别进行插入排序
第三个增量为1，则第二次排序后数组被分为1组，进行插入排序
结果为：
至此希尔排序完成
- 代码实现
代码：
import java.util.Arrays;
public class ShellSort {
public int[] sortArray(int[] nums){
int len = nums.length;
//按增量分组后，每个分组中temp代表当前待排序数据，该元素之前的组内元素均已被排过
//gap只用来分组的增量，会依次递减
int currentValue,gap = len / 2;
while(gap>0){
for (int i = gap; i < len; i++) {
currentValue = nums[i];
//组内已被排序数据的索引
int preIndex = i - gap;
//在组内已被排序过的数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小，
// 则将比较的元素在组内后移一位
while(preIndex>=0 && nums[preIndex] > currentValue){
nums[preIndex+gap]=nums[preIndex];
preIndex -= gap;
}
//当while循环结束时，说明找到了当前待排序数据的合适位置插入数据
nums[preIndex+gap] = currentValue;
}
System.out.println("本轮增量:"+gap+" 排序后的数组：");
PrintArray.print(nums);
System.out.println("----------");
gap/=2;
}
return nums;
}
public static void main(String[] args) {
int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};
ShellSort shellSort = new ShellSort();
shellSort.sortArray(array);
}
}
class PrintArray{
public static void print(int[] nums){
System.out.println(Arrays.toString(nums));
}
}
- 算法特点
时间复杂度:n和d的函数：O（n^1.25）~ O（1.6n^1.25）
空间复杂度: O（1）
希尔排序每一趟移动，移动位置较大，跳跃式地接近排序后的最终位置
增量序列必须是递减的，最后一个必须是1（对整体进行直接插入排序）
希尔排序是一种不稳定的排序方法，且不宜在链式存储结构上实现
希尔排序通过降低比较次数和移动次数来提高排序的效率
" 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！
原文链接: https://blog.csdn.net/chenchenchencl/article/details/126613755