functionmergeSort(arr){var len = arr.length;if(len <2){return arr;}var middle = Math.floor(len /2),
left = arr.slice(0, middle),
right = arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left, right){var result =[];while(left.length>0&& right.length>0){if(left[0]<= right[0]){
result.push(left.shift());}else{
result.push(right.shift());}}while(left.length)
result.push(left.shift());while(right.length)
result.push(right.shift());return result;}
6.快速排序
定义:
将第一个元素作为基准值,遍历数组,比基准小的放在左边,最后将第一个元素与最后一个左边元素调换位置
以此类推,在左边以及右边的数组中重复该操作直至全部数组排序完成
代码实现:
functionquickSort(arr, left, right){var len = arr.length,
partitionIndex,
left =typeof left !='number'?0: left,
right =typeof right !='number'? len -1: right;if(left < right){
partitionIndex =partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);}return arr;}functionpartition(arr, left ,right){// 分区操作var pivot = left,// 设定基准值(pivot)
index = pivot +1;for(var i = index; i <= right; i++){if(arr[i]< arr[pivot]){swap(arr, i, index);
index++;}}swap(arr, pivot, index -1);return index-1;}functionswap(arr, i, j){var temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}