浅谈排序算法
本文引至: 排序算法
计算机中两大主要的算法,一个是排序,一个是索引. 基于这两个基本的算法, 我们应该了解一下最基本的内容。 这里, 我们先介绍一下排序算法.
冒泡排序
冒泡排序(bubble sort) 是一种比较简单的排序方法, 但他的速度也是最慢的一种. 他是通过循环比较序列, 然后将大的移到后面, 小的放到前面. 更形象的理解, 可以参考 bubble sort 动态演示.
这里, 我们通过对数组的比较来实现一个简单的冒泡排序.
/ * 生成随机数组 */function randomArr() { let arr = []; for (var i = 0; i Math.random() - 0.5); return arr;}let arr = randomArr();/ * 冒泡排序 * @param {Array} arr 乱序数组 */function bubbleSort(arr){ for(var j=arr.length;j>=2;j--){ for(var i=0;iarr[i+1]){ // 交换数组值 [arr[i],arr[i+1]] = [arr[i+1],arr[i]]; } } } return arr;}arr = bubbleSort(arr);console.log(arr);我们可以看一下他的复杂度:
type
complexity
最坏情况的排序
O(n^2)
最好情况的排序
O(n)
平均性能
O(n^2)
空间复杂度
O(1)
实际上, 这只是很基础的一部分. 如果想需要计算机, 真的需要很多实战场景才行.
选择排序
他原理是, 从列表的第一个位置开始, 与剩余位置进行比较, 如果存在比第一个位置小的,那么和他进行交换. 这样,最小的元素就到第一个位置上去了. 然后从第二个位置开始, 又和剩余的元素比较, 接着第二小的元素,就到第二个位置上. 以此类推, 知道所有元素排序列完全. 动态内容请参考: selection sort
接着我们使用代码来模拟一下:
let arr = randomArr();/ * 选择排序 * @param {Array} arr 乱序排序的数组 * @return {Array} 返回新的排列数组 */function selectSort(arr){ for(var i=0;ii;j--){ if(arr[i]>arr[j]){ [arr[i],arr[j]] = [arr[j],arr[i]]; } } } return arr;}arr = selectSort(arr);console.log(arr);他的复杂度,很好理解: 时间上是O(n^2) 且不论任何情况. 空间上是O(1) 就相当于基本不会变的那种.
插入排序
插入排序的原理是: 从第二个位置开始, 与前一个元素进行比较,如果该元素比较小, 则将第一个元素移到第二个元素上, 然后将该元素插入到第一个元素。 然后到第三个位置（3ele）, 将3ele与前两个元素进行比较, 如果第二个元素比其大, 则往后移动移动一位,直到找到比3ele小的位置并插入. 最好还是看动态图:insert
我们使用算法来模拟一下:
/ * 插入排序 * @param {Array} arr 乱序排序的数组 * @return {Array} 返回新的排列数组 */function inertSort(arr){ for(var i=1,len=arr.length;i=0;j--){ if(target同样, 该算法的时间复杂度和算则排序类似为O(n^2),空间复杂度为O(1)typecomplexity最坏情况的排序O(n^2)最好情况的排序O(n)平均性能O(n^2)空间复杂度O(1)这里就是最基本的排序算法. 做一下总结:3中基本的算法,我们差不多了解了. 但他们之间孰优孰劣,我们还不太清楚, 我们可以写一个简单的测试类,来看看, 他们之间的速度.详细代码,我放在JSfiddler中了, 有兴趣的可以看一看,我这里只把结果列一下:基本结果如下:bubbleSort time is
1: 39.820ms
selectSort time is
2: 18.385ms
insertSort time is
3: 3.907ms
这是建立在1000个元素大小的arr上. 可见, size越大, 他们之前性能差别越大. 基本的速度是:insert > select > bubble主要是因为1. insert 是只要找到比其target小的就结束一轮循环. 并且,他的比较次数, 是由小到大的, 并且很大几率是小于最大长度.1. 而select的比较次数是从数组长度开始的(最大长度), 并且每一轮都会全部比较, 这就有点尴尬了.1. bubble 我就不啰嗦了. 太累人了所以, 最后我们可以总结一下:## 高级排序算法所谓的高级实际上是针对于大数据来说的. 上面简单的排序正对于10^4 量级的已经够了。 但是如果你想提高的话, 则可能就要上一个level了.### 希尔排序希尔是个人名, 我们也可以叫做ShellSort. 他实际上是基于插入排序的, 由于插入排序是3中基本排序中最快的, 所以, 如果想要提升效率和速度的话, 最快捷的办法就是基于他了. 插入排序 默认的比较间隔是1,如果他的目标值,刚好在比较范围的另外一端的话, 那么基本上,这就比较心累了. 所以, 为了解决在大数据中遇到的问题, Shell 提出了一种排序, 即, 指定序列间隔进行相关排序. 原来的插入排序比较间隔是1, 那么这里就可以改为[5,3,1],如果size更大, 序列间隔大小还可以改为[10,5,3,1]. Marcin Ciura 写过一篇论文论证过这个步长值, 一般取701, 301, 132, 57, 23, 10, 4, 1. 这几个, 希尔排序的性能会得到最大的提升.具体的动图为: 不过, 估计也没几个人看懂, 这个还是得多动手,才会有点感觉. 如果实在不懂, 可以参考插入排序.这里,直接上代码了:/
- shell排序
- @param {Array} arr 乱序数组
- @param {Array} gaps 步长数组
- @return {Array} 返回排序后的数组
*/
function shellSort(arr, gaps) {
for (var gap of gaps) {
// gap为每一次的步长值
// 将每次遍历的第一个值(i) 设为步长值
for (var i = gap, len = arr.length; i =gap && arr[j-gap] > target;j-=gap){
arr[j] = arr[j-gap]
}
// 比较完成后, 将target插入到适当位置
arr[j]=target;
}
}
return arr;
}另外, 还有一种动态ShellSort. 是动态计算步长值. 他的原理是根据你的arr.length来确定的.我们先看一下他生成步长序列的方法.(**这是 Robert Sedgewick 写的, 《算法》的合著者**)
// 生成随机数组 const produceGaps = function() { var N = arr.length, h = 1, gaps = []; while (h = gap && arr[j - gap] > target; j -= gap) { arr[j] = arr[j - gap] } // 比较完成后, 将target插入到适当位置 arr[j] = target; } } return arr; } return shellSort(arr,gaps);}实际上, 他们两者效率其实差不多, 动态的只是多出来一个生成随机数组而已. 相比于 对超大量数组排序来说, 这点还是不算什么的.
所以, 上面的两种方法, 你用哪种都差不多.该算法的复杂度为:
type
complexity
最坏情况的排序
O(O(nlog2 n)
最好情况的排序
O(n)
平均时间复杂度
取决于间隔值的大小, 越大则越小
空间复杂度
O(1)
归并排序(mergesort)
归并排序,不同于上述所有的排序方法, 他是一种以牺牲空间换效率的算法. 归并排序,有两种排序方向,一种为自顶向下(top-down),一种为至底向上(down-top). 两者其实没有什么太大的却别, 只是他们两者实现的方式是完全相反的.
top-down: 现将原来的list 一步一步切分为size为1的sublist. 并且每一次拆分,都对将要分开的sublist, 作相关的排序, 最后,得到size为1的list, 合并这些list 就得到sorted list. 但, 该方式可能会涉及递归, 比较困难, 对于js这种, 处理空间能力弱的, 该方式就不合适了.
down-top: 先将原来的list 直接切分为size为1的sublist, 然后逐步将两两sublist合并为一个list, 一层一层, 最后合并为一个完整有序的list.
具体,动图为; from wiki
如果, 还是不理解, 可以参考动图mergesort. 接下来, 我们还是照常的来实现一下归并排序的算法.(至顶向下)。 实际算法如图:
function mergerSort(arr) { let step = 1, len = arr.length; // 如果数组为1|0则直接返回 if (len JSfiddle中了.他的基本复杂度为:typecomplexity最坏情况的排序O(nlogn)最好情况的排序O(n)平均性能O(nlogn)空间复杂度O(n)### 快速排序(quick sort)快排是一种比较浪的排序方法, 他的思想很简单, 找到基准点, 分组. 通常情况下, QS(quick sort)对于归并排序和希尔排序可以说是碾压级的, 效率一般会高出1~2倍左右. why? 我们说一下快排的原理, 大家大概就会清楚了基本过程1. 找到基准点(pivot), 通常情况下以第一个, 当然, 也可以说数组中任意一个. 只是第一个比较方便1. 比较基准点. 小的放到基准点的左边, 大的放在右边1. 递归上述步骤, 直到全部比较完毕.从宏观上来说, 快排其实可以算3部分:1. 基准值1. 左边数组1. 右边数组这个就相当于我们的二分法了. so, 快排又叫做二分比较法(partition-exchange sort)摘自wiki的动图:感觉还是挺好懂的. 接下来我们使用代码来模拟一下:function QuickSort(arr){
if(arr.lengthpivot){
right_arr.push(arr[i])
}else{
left_arr.push(arr[i]);
}
}
return QuickSort(left_arr).concat([pivot],QuickSort(right_arr));
}
function randomArr() {
let arr = [];
for (var i = 0; i Math.random() - 0.5);
return arr;
}
let arr = randomArr();
console.log(QuickSort(arr));
快排的基本复杂度为:typecomplexity最坏情况的排序O(nlogn)最好情况的排序O(n)平均性能O(nlogn)空间复杂度O(logn)这里,3种高级的排序已经说完了。 Shell Sort && Merge Sort 相当于只是了解一下, 快排才是应该掌握并且要灵活运用的.最后,我们来总结一下吧：数据结构, 快速排序, 冒泡排序, arr,版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
