©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>1、递归排序法 (性能消耗低)：
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document
</title> </head> <body> <script> let arr = [1,4,2,6,7,9,11,5,8,10,3]; //let arr
= [1,4,2,3]; //可以拿这个演示更好理解 //划分 function mergeSort(arr){ let len = arr.length;
//起初为两个两个进行比较 if(len < 2){ return arr; } //以mid作为分界线 let mid = Math.floor(len/2)
; //拆分成left于right两个数组 let left = arr.slice(0,mid); let right = arr.slice(mid);
//递归 逆向思考最后一次 mergeSort(left)于mergeSort(right)长度都为1的情况 return merge(mergeSort(
left),mergeSort(right)); } //排序 function merge(left,right){ let result = [];
while(left.length >0 && right.length >0){ if(left[0] <= right[0]){
//删除left数组第一项push到result内 result.push(left.shift()); }else{ result.push(right.
shift()); } } //此时如果还有一个数组内有值就将它push到result数组里面 while(left.length){ result.push(
left.shift()); } while(right.length){ result.push(right.shift()); } //返回排序好的数组
return result; } let newArr = mergeSort(arr); console.log(newArr); //[1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11] </script> </body> </html>
<>2、快速排序法：
//快速排序 let arr = [1,4,2,6,7,9,11,5,8,10,3]; function quickSort(arr){ let len =
arr.length; quick(arr,0,len-1); } function quick(arr,left,right){ let point =
left; //第一项 let index = point + 1; //遍历起点 let len = arr.length;
//以arr[point]作为参照物 起点开始遍历到终点 将比arr[point]小的值放左边 for(let i=index; i<=right; i++){
if(arr[i] < arr[point]){ swap(arr,i,index); //换位置 index++; //交换点往前移一位 } } //最后让
第一项 与 arr[index-1]作交换 swap(arr,point,index-1); index--; //arr左右的分割点 let leftE =
index-1; //left的终点 let rightB = index+1; //right的起点 //每边大于2个数才需要递归 直到每边只有一个数 if(
leftE> left){ quick(arr,point,leftE); } if(rightB < right){ quick(arr,rightB,
right); } } //换位置 function swap(arr,i,j){ let tmp = arr[i]; arr[i] = arr[j]; arr
[j] = tmp; } quickSort(arr) console.log(arr) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11]
<>3、堆排序法：
let arr = [1,4,2,6,7,9,11,5,8,10,3]; //堆排序 function heapSort(arr){ let len =
arr.length; //初始化堆调整 for(let j=Math.floor(len/2)-1; j>=0; j--){ heap(arr,j,len);
} for(let i =len-1; i>0; i--){ swap(arr,0,i); len --; heap(arr,0,len); } }
function heap(arr,i,len){ //从第i个开始一层一层逆向得出最大的数 let left = 2*i+1, //得出左边子集 right
= 2*i+2; //得出右边子集 max = arr[i], //设最后一个为最大值 maxIndex = i; //和最大值比较 并更新最大值的max
Index if(left<len && arr[left]>max){ maxIndex = left; } if(right<len && arr[
right]>max){ maxIndex = right; } if(maxIndex !== i){ //最大值交换 swap(arr,i,maxIndex
); heap(arr,maxIndex,len); } } //交换 function swap(arr,i,j){ let tmp = arr[i];
arr[i] = arr[j]; arr[j] = tmp; } heapSort(arr) console.log(arr) //[1, 2, 3, 4,
5, 6, 7, 8, 9, 10, 11]
<>4、基数排序法: (低消耗)
//基数排序法 function redixSort(arr){ let len = arr.length; //找出数组中最大数的位数 let maxNum
= arr[0]; let redixArr = []; for(let i=1; i<len; i++){ if(arr[i] > maxNum){
maxNum= arr[i]; } } let x=10,y=1; let maxDigit = maxNum.toString().length;
//最大位数 for(let i=0; i<maxDigit; i++){ for(let j=0; j<len; j++){ let v = Math.
floor(arr[j] % x/y); if(!redixArr[v])redixArr[v] = []; redixArr[v].push(arr[j]);
//个位 十位 百位...排序 } x *=10; y *=10; let index =0; //排序好的遍历回arr数组内 for(let j=0,len=
redixArr.length;j<len; j++){ let item = redixArr[j]; if(!item)continue; item.
forEach(v=>{ arr[index ++] = v; }); } //最后将redixArr排序清空等待下一次排序 redixArr = []; }
} arr = [233,434,565,23,78,2,54,56,9]; redixSort(arr); console.log(arr); //[2,
9, 23, 54, 56, 78, 233, 434, 565]