数据结构中的各种排序方法小结(JS实现)
更新时间:2016年7月29日 10:00 点击:2250
新技术一直在不断变化,掌握一些基础是未来学习不断更新的技术的坚实基础。近来闲来无事,为了温习一下从前学的数据结构,将数据结构中的排序算法用JS实现了一遍,并在本文末尾处嵌入了DEMO。
简单排序
冒泡排序
冒泡排序是最简单排序算法,时间复杂度为n的平方,代码如下:
function bubbleSort(array) { for (var i = 0; i < array.length; i++) { for (var j = array.length; j > 0; j--) { if (array[j] < array[j - 1]) { var temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; } } /* 输出结果 */ document.write("这是第 + (i + 1) + "次循环·,结果为:"); for (var k = 0; k < array.length; k++) { document.write(array[k] + ","); } document.write("<br />"); /* 输出结果结束 */ } }
直接插入排序
直接插入排序也属于简单排序算法,时间复杂度也为n的平方,但性能略好于冒泡排序,代码如下:
function insertSort(array) { var temp; for (var i = 1; i < array.length; i++) { var temp = array[i]; for (var j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } array[j] = temp /* 输出结果 */ document.write("第? + i + "遍排序的结果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 输出结果结束 */ } }
选择排序
选择排序也属于简单排序算法,时间复杂度也为n的平方,性能同样略微好于冒泡排序,代码如下:
function selectSort(array) { var min, temp; ; for (var i = 0; i < array.length; i++) { min = i; for (var j = i + 1; j < array.length; j++) { if (array[min] > array[j]) min = j; } if (min != i) { temp = array[i]; array[i] = array[min]; array[min] = temp; } /* 输出结果 */ document.write("第 + i + "遍排序的结果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 输出结果结束 */ } }
复杂排序
希尔排序
希尔排序是插入排序的升级,1959年希尔通过将简单排序中两两比较改为设置步长跳跃式比较而突破了n的平方的时间复杂度,希尔排序根据步长的不同时间复杂度由最好的nlogn到最坏的n的平方。代码如下:
function shallSort(array) { var increment = array.length; var i var temp; //暂存 var count = 0; do { increment = Math.floor(increment / 3) + 1; for (i = increment; i < array.length; i++) { if (array[i] < array[i - increment]) { temp = array[i]; for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) { array[j + increment] = array[j]; } array[j + increment] = temp; /* 输出结果 */ count++; document.write("<br />第 + count + "遍排序的结果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 输出结果结束 */ } } } while (increment > 1) }
堆排序
堆排序是选择排序的升级,通过不断构建大顶堆或者小顶堆来选择最大或者最小的值放入队列前端进行排序,堆排序任何情况下的时间复杂度都为nlogn,代码如下:
function heapSort(array) { var temp; var i; for (i = Math.floor(array.length / 2); i >= 0; i--) { heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆 } for (i = array.length - 1; i >= 0; i--) { /*把根节点交换出去*/ temp = array[i]; array[i] = array[0]; array[0] = temp; /*余下的数组继续构建成大顶堆*/ heapAdjust(array, 0, i - 1); /* 输出结果 */ document.write("<br />第 + (array.length - i).toString() + "遍排序的结果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 输出结果结束 */ } } //要调整的子树 //start为数组开始下标 //max是数组结束下标 function heapAdjust(array, start, max) { var temp, j; temp = array[start];//temp是根节点的值 for (j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标 ++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; }
归并排序
归并排序是复杂排序中唯一一个稳定排序,通过将待排序数组进行分拆再合并来进行排序,归并排序时间复杂度为n的平方,代码如下:
//source源数组 //dest目标数组 //s起始下标 //t目标下标 function mSort(source, dest, s, t) { var m; //取中间值 var dest2 = new Array(); if (s == t) { dest[s] = source[s]; } else { m = Math.floor((s + t) / 2); mSort(source, dest2, s, m); mSort(source, dest2, m+1 , t); merge(dest2, dest, s, m, t); /* 输出结果 */ document.write("<br />第 + ++count + "遍排序的结果是:") for (var n = 0; n < dest.length; n++) { document.write(array[n] + ","); } /* 输出结果结束 */ } } //将两个数组按照从小到大的顺序融合 //source原数组 //dest排序后的数组 //s第一个下标 //m第二个数组下标 //总长度 function merge(source, dest, s, m, n) { for (var j = m+1, k = s; j <= n && s <= m; k++) { if (source[s] < source[j]) { dest[k] = source[s++]; } else { dest[k] = source[j++]; } } //将剩余排不完的有序数组加入到dest的末端 if (s <= m) { for (var l = 0; l <= m - s; l++) { dest[k + l] = source[s+l]; } } if (j <= n) { for (var l = 0; l <= n - j; l++) { dest[k + l] = source[j+l]; } } }
快速排序
快速排序是目前已知的速度最快的排序,时间复杂度为nlogn,代码如下:
var count = 0; function quickSort(array, low, high) { var temp; if (low < high) { var keypoint = QuickSortHelp(array, low, high); count++; document.write("<br />第台? + count + "遍括?排?序ò的?结á果?是?:") for (var l = 0; l < array.length; l++) { document.write(array[l] + ","); } quickSort(array, low, keypoint - 1); quickSort(array, keypoint + 1, high); } } function QuickSortHelp(array, low, high) { while (low < high) { while (low < high && array[low] <= array[high]) { high--; } temp = array[low]; array[low] = array[high]; array[high] = temp; while (low < high && array[low] <= array[high]) { low++ } temp = array[low]; array[low] = array[high]; array[high] = temp; } return low; }
以上这篇数据结构中的各种排序方法小结(JS实现)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持脚本之家。
相关文章
- 本篇文章主要分享了通过window.navigator来判断浏览器及其版本信息的实例代码。具有一定的参考价值,下面跟着小编一起来看下吧...2017-01-23
- 这篇文章主要介绍了js如何实现浏览器打印功能,文中示例代码非常详细,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-07-15
- 下面小编就为大家带来一篇利用JS实现点击按钮后图片自动切换的简单方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-10-25
- 作为前端,一直以来都知道HTTP劫持与XSS跨站脚本、CSRF跨站请求伪造。防御这些劫持最好的方法是从后端入手,前端能做的太少。而且由于源码的暴露,攻击者很容易绕过防御手段。但这不代表我们去了解这块的相关知识是没意义的,本文的许多方法,用在其他方面也是大有作用。...2021-05-24
- 这篇文章主要给大家介绍了关于Nest.js参数校验和自定义返回数据格式的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-28
- 那么今天我就用JavaScript代码来实现这个效果吧,那么首先介绍一下整个的思路,首先我们先将确定输入密码的位数,我的需求是5位,那么就用一个div标签包住5个input标签...2016-01-02
- 这篇文章主要为大家详细介绍了js+css实现回到顶部按钮back to top回到顶部按钮,感兴趣的小伙伴们可以参考一下...2016-03-03
- 这篇文章主要为大家详细介绍了js实现上传图片及时预览的相关资料,具有一定的参考价值,感兴趣的朋友可以参考一下...2016-05-09
- 这篇文章主要给大家介绍了一个关于JS正则匹配的踩坑记录,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-13
- 这篇文章主要介绍了js实现调用网络摄像头及常见错误处理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-07
- 这篇文章主要为大家详细介绍了JS实现随机生成验证码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-06
- 这篇文章主要介绍了如何使用JavaScript实现“无缝滚动 自动播放”轮播图效果,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-08-20
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了基于JavaScript实现文字超出部分隐藏 的相关资料,需要的朋友可以参考下...2016-03-01
- 这篇文章主要介绍了js组件SlotMachine实现图片切换效果制作抽奖系统的相关资料,需要的朋友可以参考下...2016-04-19
- Vue.js通过简洁的API提供高效的数据绑定和灵活的组件系统.这篇文章主要介绍了vue.js 表格分页ajax 异步加载数据的相关资料,需要的朋友可以参考下...2016-10-20
- 为了网站的安全性,很多朋友都把密码设的比较复杂,但是如何密码不能明显示,不知道输的是对是错,为了安全起见可以把密码显示的,那么基于js代码如何实现的呢?下面通过本文给大家介绍JavaScript实现表单密码的隐藏和显示,需要的朋友参考下...2016-03-03
- 这篇文章主要介绍了JS实现响应鼠标点击动画渐变弹出层效果代码,具有非常自然流畅的动画过度效果,涉及JavaScript针对鼠标事件的响应及页面元素样式的动态操作相关技巧,需要的朋友可以参考下...2016-03-28
- 这次文章要给大家介绍的是node.JS md5加密中文与php结果不一致怎么办,不知道具体解决办法的下面跟小编一起来看看。 因项目需要,需要Node.js与PHP做接口调用,发现nod...2017-07-06
- 系统的学习了一下angularjs,发现angularjs的有些思想根php的模块smarty很像,例如数据绑定,filter。如果对smarty比较熟悉的话,学习angularjs会比较容易一点,这篇文章给大家介绍angularjs filter用法详解,感兴趣的朋友一起学习吧...2015-12-29