本文引至:
计算机中两大主要的算法,一个是排序,一个是索引. 基于这两个基本的算法, 我们应该了解一下最基本的内容。 这里, 我们先介绍一下排序算法.
冒泡排序
冒泡排序(bubble sort) 是一种比较简单的排序方法, 但他的速度也是最慢的一种. 他是通过循环比较序列, 然后将大的移到后面, 小的放到前面. 更形象的理解, 可以参考 动态演示.
这里, 我们通过对数组的比较来实现一个简单的冒泡排序./** * 生成随机数组 */function randomArr() { let arr = []; for (var i = 0; i < 50; i++) { arr.push(i); } arr.sort(() => 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;i arr[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) |
实际上, 这只是很基础的一部分. 如果想需要计算机, 真的需要很多实战场景才行.
选择排序
他原理是, 从列表的第一个位置开始, 与剩余位置进行比较, 如果存在比第一个位置小的,那么和他进行交换. 这样,最小的元素就到第一个位置上去了. 然后从第二个位置开始, 又和剩余的元素比较, 接着第二小的元素,就到第二个位置上. 以此类推, 知道所有元素排序列完全. 动态内容请参考:
接着我们使用代码来模拟一下:
let arr = randomArr();/** * 选择排序 * @param {Array} arr 乱序排序的数组 * @return {Array} 返回新的排列数组 */function selectSort(arr){ for(var i=0;i i;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小的位置并插入. 最好还是看动态图:
我们使用算法来模拟一下:/** * 插入排序 * @param {Array} arr 乱序排序的数组 * @return {Array} 返回新的排列数组 */function inertSort(arr){ for(var i=1,len=arr.length;i =0;j--){ if(target 看一下动图: from wiki
同样, 该算法的时间复杂度和算则排序类似为O(n^2),空间复杂度为O(1) | type | complexity |
|---|---|
| 最坏情况的排序 | O(n^2) |
| 最好情况的排序 | O(n) |
| 平均性能 | O(n^2) |
| 空间复杂度 | O(1) |
这里就是最基本的排序算法. 做一下总结:
3中基本的算法,我们差不多了解了. 但他们之间孰优孰劣,我们还不太清楚, 我们可以写一个简单的测试类,来看看, 他们之间的速度.
详细代码,我放在中了, 有兴趣的可以看一看,我这里只把结果列一下:基本结果如下:bubbleSort time is1: 39.820msselectSort time is2: 18.385msinsertSort time is3: 3.907ms
这是建立在1000个元素大小的arr上. 可见, size越大, 他们之前性能差别越大. 基本的速度是:
insert > select > bubble
主要是因为
insert 是只要找到比其target小的就结束一轮循环. 并且,他的比较次数, 是由小到大的, 并且很大几率是小于最大长度.
而select的比较次数是从数组长度开始的(最大长度), 并且每一轮都会全部比较, 这就有点尴尬了.
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 < len; i++) { // 插入排序标准flag, 存储比较值 let target = arr[i]; // 在for循环中比较, 如果比较值较大, 则将比较值右移动 for (var j = i; j>=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 < N / 3) { gaps.push(h); h = 3 * h + 1; } return gaps; } 最后, 实际的动态ShellSort为
function DyShellSort(arr) { // 生成随机数组 const produceGaps = function() { var N = arr.length, h = 1, gaps = []; while (h < N / 3) { gaps.push(h); h = 3 * h + 1; } return gaps; } let gaps = produceGaps(); function shellSort(arr, gaps) { for (var gap of gaps) { // gap为每一次的步长值 // 将每次遍历的第一个值(i) 设为步长值 for (var i = gap, len = arr.length; i < len; i++) { // 插入排序标准flag, 存储比较值 let target = arr[i]; // 在for循环中比较, 如果比较值较大, 则将比较值右移动 for (var j = i; j >= 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
如果, 还是不理解, 可以参考. 接下来, 我们还是照常的来实现一下归并排序的算法.(至顶向下)。 实际算法如图:
function mergerSort(arr) { let step = 1, len = arr.length; // 如果数组为1|0则直接返回 if (len < 2) return arr; let left_start, right_start; while (step < len) { left_start = 0; right_start = step; //当数组长度为偶数时,并且小于数组总长度,执行循环 while (right_start + step <= len) { // 分开对数组进行相关排序 sortArr(arr,left_start,left_start+step,right_start,right_start+step); left_start = right_start+step; right_start = left_start+step; } // 当数组长度为奇数时, 再进行一次排序 if(right_start < len){ sortArr(arr,left_start,left_start+step,right_start,len); } step *= 2; } return arr;}/** * 对指定两个子数组数组进行排序 */function sortArr(arr, left_start, left_end, right_start, right_end) { // 生成左右两个数组 let left_len = left_end - left_start, right_len = right_end - right_start, left_arr = new Array(left_len+1), right_arr = new Array(right_len+1); // 添加两个数组的数据 let k = left_start; for(var i=0;i 基本注释已经写的很清楚了, 具体demo代码,放在中了.
他的基本复杂度为:| type | complexity |
|---|---|
| 最坏情况的排序 | O(nlogn) |
| 最好情况的排序 | O(n) |
| 平均性能 | O(nlogn) |
| 空间复杂度 | O(n) |
快速排序(quick sort)
快排是一种比较浪的排序方法, 他的思想很简单, 找到基准点, 分组. 通常情况下, QS(quick sort)对于归并排序和希尔排序可以说是碾压级的, 效率一般会高出1~2倍左右. why?
我们说一下快排的原理, 大家大概就会清楚了基本过程
找到基准点(pivot), 通常情况下以第一个, 当然, 也可以说数组中任意一个. 只是第一个比较方便
比较基准点. 小的放到基准点的左边, 大的放在右边
递归上述步骤, 直到全部比较完毕.
从宏观上来说, 快排其实可以算3部分:
基准值
左边数组
右边数组
这个就相当于我们的二分法了. so, 快排又叫做二分比较法(partition-exchange sort)
摘自wiki的动图:
感觉还是挺好懂的. 接下来我们使用代码来模拟一下:
function QuickSort(arr){ if(arr.length<2){ return arr; } let pivot = arr[0], left_arr = [], right_arr = []; for(var i=1,len=arr.length;i pivot){ 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 < 50; i++) { arr.push(i); } arr.sort(() => Math.random() - 0.5); return arr;}let arr = randomArr();console.log(QuickSort(arr)); 快排的基本复杂度为:
| type | complexity |
|---|---|
| 最坏情况的排序 | O(nlogn) |
| 最好情况的排序 | O(n) |
| 平均性能 | O(nlogn) |
| 空间复杂度 | O(logn) |
这里,3种高级的排序已经说完了。 Shell Sort && Merge Sort 相当于只是了解一下, 快排才是应该掌握并且要灵活运用的.
最后,我们来总结一下吧：
