前端的排序算法总结
参考lianjie
冒泡排序
典型的排序方法,命名来自鱼呼吸时吹出的气泡,上层的气泡总是最大的。
思路:两层循环,内层循环对比相邻两个数据(j,j+1),假设j > j + 1则交换元素位置。
外层循环为长度限制,在内层第一次循环完成后减少长度1(因为最后一个泡已经固定,为这个数组的最大值)
function bubbleSort(arr){ for(let i = 0; i < arr.length - 1; i++){ let flag = false; for(let j = 0; j < arr.length - i - 1; j++){ if(arr[j] > arr[j + 1]){ let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;; flag = true; } } if(!flag){ break; } } return arr; }
加一个标志位flag,如果没有进行交换,将标志位置为false,表示排序完成。
- 时间复杂度O(n^2),最优情况下是O(n)
- 空间复杂度O(1)
选择排序
顾名思义,每次都选择最小的,然后交换位置
思路:两层循环,内层循环为选取第一个位置的值,然后将它与剩下的值作对比,得到比它小的则交换位置。外层循环为控制第一位值的固定(一次循环后,第一位则为该数组最小的值,下一次循环不必带上)。
function selectionSort(arr){ for(let i = 0; i < arr.length - 1; i++){ let index = i; for(let j = i+1; j < arr.length; j++){ //判断是否有小于当前值,有则交换位置 if(arr[index] > arr[j]){ index = j; } } let temp = arr[i]; arr[i] = arr[index ]; arr[index] = temp; } return arr; }
- 时间复杂度:O(n^2),属于不稳定的算法(每次交换之后,它都改变了后续数组的顺序)
- 空间复杂度:O(1)
快速排序
思路:二分法,先找一个基数,分隔出以基数为界的左右两个数组,然后递归重复这个步骤,直到分组剩余一个数,则我们认为已经排列完成。
function quickSort(arr){ if(arr.length <= 1){ return arr; } let temp = arr[0]; const left = []; const right = []; for(var i = 1; i < arr.length; i++){ if(arr[i] > temp){ right.push(arr[i]); }else{ left.push(arr[i]); } } return quickSort(left).concat([temp], quickSort(right)); }
- 时间复杂度:O(n*logn),属于不稳定的算法,特殊情况下会是O(n^2)
- 空间复杂度:辅助空间是logn,所以空间复杂度为O(logn)
相关推荐
Oudasheng 2020-05-29
shawsun 2020-01-12
lixiaotao 2019-11-15
风和日丽 2019-11-03
HeavyIndustry 2014-11-25
风吹夏天 2014-04-07
WalkMoreSlowly 2012-10-25
算法改变人生 2019-06-27
代码之神 2019-06-27
代码之神 2019-06-25
韦一笑 2011-04-20
hang0 2011-04-20
WindChaser 2011-04-20
hugebawu 2011-04-20
RememberMePlease 2011-04-20
MrA 2011-04-20