牛客网编程初学者入门训练题解JavaScript版本

• JavaScript_基本排序算法
• 1.冒泡排序
• 2.选择排序
• 3.快速排序
• 4.归并排序 空间复杂度o(n)
• 5.js内置排序sort()

JavaScript_基本排序算法

1.冒泡排序

时间换空间 空间复杂度是o(1) 时间复杂度是o(n^2)
最坏n2,最好n，平均n2,稳定排序算法，比较简单
使用范围：n比较小的时候
缺点：复杂度过大

function bubble(arr){for(var i=0;i<arr.length;i++){for(var j=0;j<arr.length-1-i;j++){if(arr[j]>arr[j+1]){[arr[j],arr[j+1]]= [arr[j+1],arr[j]]}}}return arr}

2.选择排序

最好O(n) 最坏O(n^2) 平均o(n^2）空间O(1) 不稳定
使用范围数据n少的时候，占内存少
不稳定，复杂度高

function select(arr){for(var i=0;i<arr.length;i++){for(var j=i+1;j<arr.length;j++){if(arr[i]>arr[j]){[arr[i],arr[j]]= [arr[j],arr[i]]}}}return arr;}

3.快速排序

空间负复杂度o(logn) 时间复杂度o(nlogn)
最坏是n^2,最好nlogn,平均nlogn,不稳定排序算法，复杂
使用范围：n大的时候效率高
缺点：n越大容易占内存，不稳定

function quick(arr){if(arr.length==0) return [];var left = []var right = []var base = arr[0]for(var i=1;i<arr.length;i++){if(arr[i]<base){left.push(arr[i])}else{right.push(arr[i])}}return quick(left).concat(base,quick(right))}

4.归并排序 空间复杂度o(n)

最坏，最好，平均都是nlogn ,稳定排序算法
优点：n大时好，效率高且稳定的排序算法。
缺点：归并比较占用内存，内存随n的增大而增大，

function merge(arr){if(arr.length<=1) return arr;var mid=Math.floor(arr.length/2);// 递归调用自身，拆分的数组都是排好序的，最后传入merge合并处理return mergeSort(merge(arr.slice(0,mid)),merge(arr.slice(mid)));}// 将两个排好序的数组合并成一个顺序数组function mergeSort(left,right){var res=[];while(left.length>0 && right.length>0){// 不断比较left和right数组的第一项，小的取出存入resif(left[0]<right[0]){res.push(left.shift())}else{res.push(right.shift())}}return res.concat(left,right);}

5.js内置排序sort()

arr.sort(function(a,b){return a-b});//a-b是升序排列//函数返回值小于0认为是第一个元素小于第二个元素，等于0是两个元素相等，大于0是第一个元素大于第二个元素,则交换两个元素//b-a是降序排列//函数返回值大于0认为是第一个元素小于第二个元素，等于0是两个元素相等，大于0是第一个元素小于第二个元素,则交换两个元素