js 实现排序算法 -- 希尔排序(Shell Sort)
2024-08-29 21:30:09
原文:
希尔排序
1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述:
将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
- 选择一个增量序列t1,t2,…,tk,其中t1>t2>...,tk=1;
- 按增量序列个数k,对序列进行k 趟排序;
- 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
图形解释:
代码实现:
function shellSort(arr) {
let len = arr.length;
// gap 即为增量
for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
let j = i;
let current = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
} var arr = [3,5,7,1,4,56,12,78,25,0,9,8,42,37];
shellSort(arr);
最新文章
- 【代码笔记】iOS-用户发布后能保存崩溃
- ios10 xcode8 适配的那些事
- LeetCode ";Design Twitter";
- Pair Project:电梯控制程序
- 利用YaHoo YUI实现Javascript CSS 压缩 分类: C# 2014-07-13 19:07 371人阅读 评论(0) 收藏
- python编写规范
- (六)u-boot2013.01.01 for TQ210:《精简u-boot文件目录,定制自己的目标板》
- 【转】给Winform的button等控件添加快捷键
- SpringMVC注册拦截器
- 17个提升iOS开发效率的必用工具
- SAP进度条
- codeforces——961C. Chessboard
- QPainter
- ElasticSearch简要总览
- php.ini 开发和线上配置的差异
- history新增方法
- Python-CSS高级 题目
- poj 2155(未完成)
- Tap 模拟手势点击坐标
- linux firefox 快捷方式
热门文章
- PAT Basic 1034 有理数四则运算(20) [数学问题-分数的四则运算]
- SVN提交时忽略不必提交的文件夹和文件,如node_modules
- java添加后台缓存
- Linux中PATH、 LIBRARY_PATH、 LD_LIBRARY_PATH和ROS_PACKAGE_PATH
- D - Daydreaming Stockbroker Gym - 101550D
- Qt 使用QGraphicsPixmapItem、QGraphicsScene、QMatrix 的QGraphicsView的显示,缩放
- 为什么使用 document.write 需要将<;/script>;拆分开
- vue中axios的post请求使用form表单格式发送数据
- CondaHTTPError: HTTP 000 CONNECTION FAILED for url <;https://repo.anaconda.com/pkgs/main/win-64/repodata.json.bz2>; Elapsed: -
- CCP 协议