【算法】希尔排序(Shell Sort)(四)
2024-09-07 10:57:23
希尔排序(Shell Sort)
1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
1.算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
- 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
- 按增量序列个数k,对序列进行k 趟排序;
- 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
2.动图演示
3.代码实现
//javascript实现
function shellSort(arr) {
for(var gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
// 内层循环与插入排序的写法基本一致,只是每次移动的步长变为 gap
var preIndex, current;
for (var i = gap; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
}
return arr;
}
//java实现
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}
4.算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。
最新文章
- Android的Kotlin秘方(I):OnGlobalLayoutListener
- ASP.NET Core的配置(5):配置的同步[设计篇]
- js中原型的概念
- solr集成mmseg4j分词
- centos 关闭不使用的服务
- C#运算除法和求整
- Quartz中Cron表达式使用方法
- JavaWeb项目开发案例精粹-第3章在线考试系统-003Dao层
- UVA 125 Numbering Paths
- 【GDOI2014 DAY2】Beyond (扩展KMP)
- ZOJ 3939The Lucky Week<;模拟/暴力>;
- 【Java学习笔记之三十】详解Java单例(Singleton)模式
- 原生nodejs在线聊天系统
- 小白必读:闲话HTTP短连接中的Session和Token
- 【Java深入研究】4、fail-fast机制
- January 29th, 2018 Week 05th Monday
- c#特性学习(1)
- Java Hex 16进制的 byte String 转换类
- jmeter控制器(一)
- java Web监听器实现定时发送邮件