冒泡排序、选择排序与插入排序复杂度都是二次方级别的,放在一起说吧。
介绍一些学习这三个排序方法的比较好的资料。冒泡排序看《学习JavaScript数据结构与算法》介绍的冒泡排序,选择排序看《计算机科学概论(第三版)》里介绍的选择排序,插入排序看《计算机科学概论(第11版)》里介绍的插入排序,
通过这三份资料弄明白实现原理之后,最后看《学习JavaScript数据结构与算法》一书里的JS实现代码。
嗯,《学习JavaScript数据结构与算法》这本书里都有现成代码,是用ES5写的,就不在这儿写了,关键是弄清楚原理,然后JS代码每天写两遍,就OK了。
我在这儿用ES6来写一下。
冒泡排序:
var bubbleSort = arr => { let length = arr.length; for (let i = 0; i < length; i++) { for (let j = 0; j < length-1-i; j++) { if (arr[j] > arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; } } } }
ES6的解构好酸爽,都不用辅助函数了,几行代码就实现了冒泡排序。验证一下正确性吧。
var array = [7, 3, 9, 6, 11, 2, 4, 5]; var bubbleSort = arr => { let length = arr.length; for (let i = 0; i < length; i++) { for (let j = 0; j < length-1-i; j++) { if (arr[j] > arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; } } } } bubbleSort(array); console.log(array);
OK,chrome浏览器没问题,接下来用ES6实现选择排序。
选择排序:
var selectSort = arr => { let length = arr.length, indexMin; for (var i = 0; i < length - 1; i++) { indexMin = i; for (var j = i; j < length; j++) { if (arr[j] < arr[indexMin]) { indexMin = j; } } if (i !== indexMin) { [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]; } } }
验证过程与冒泡排序一样,就不在这儿写了。下面实现最后一个插入排序。
插入排序:
var insertSort = arr => { let length = arr.length, j, temp; for (var i = 1; i < length; i++) { j = i; temp = arr[i]; while (j > 0 && arr[j-1] > temp) { arr[j] = arr[j-1]; j--; } arr[j] = temp; } };
验证过程与冒泡排序一样。OK,三个速度较慢的排序算法完成了,下次写速度快的排序算法,也是各大浏览器实现sort时用的算法。
说好用ES6语法,我怎么忘记了箭头函数,赶紧补上。。。今后业务代码里,要强迫自己使用箭头函数,不然怎么提升自己呢。