js实现常见的三种排序方法（冒泡排序、快速排序、归并排序）

发表于 | 分类于

1、冒泡排序(升序): 比较相邻的数,依次找出较大的数往后放；具体原理：冒泡排序原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function popSort(arr){
  let length = arr.length;
  if(length>1){
    //n个数的数组需要排序（n-1）轮
    for(let i=0;i<length-1;i++){
       //每一轮比较的次数逐次递减
       for(let j=0;j<length-1-i;j++){
         let a =0;
         if(arr[j]>arr[j+1]){
           a =arr[j]; 
           arr[j] =arr[j+1]; 
           arr[j+1] =a; 
         }
       }
    } 
  }
  return arr; 
}

2、快速排序步骤：找基准数（随机数找）=>遍历数组，小于基准数放左边，大于放右边=>对左右两边的子序列重复上述操作； 具体原理：快速排序原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function quickSort(arr){
 let length =arr.length;
 if(length<=1){ return arr;}
 //找到基准点并删除该数
 let index = Math.floor(length/2), base= arr.splice(index,1)[0],left=[],right=[];
 //把数组按基准点分成两个子数组
 for(let i=0;i<arr.length;i++){
   let val = arr[i];
   if(val>base){ right.push(val);} 
   else{ left.push(val);} 
 } 
 //递归
 return quickSort(left).concat([base],quickSort(right));
}

3、归并排序：将数组分为两个子数组，重复此操作直到所有的子数组都只含有一个元素，然后从底部开始两两合并；合并与分割同时进行；具体原理：归并排序原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 function mergeSort(arr){
  let length = arr.length;
  if(length<=1|| (!Array.isArray(arr))){return arr;}
  //分割数组
  let mid = Math.floor(length/2);
  let left = arr.slice(0,mid);
  let right = arr.slice(mid);
  return mergeArr(mergeSort(left),mergeSort(right)) ;
}
 //合并数组
 function mergeArr(left,right){
 let result =[];
 while(left.length>0&&right.length>0){
   if(left[0]<right[0]){
    result.push(left.shift());
   }else{
    result.push(right.shift());
   } 
  }
  return result.concat(left,right);
}

let array1 = [10,2,1,7,12,5,9,0];
console.log(mergeSort(array1))//返回[0, 1, 2, 5, 7, 9, 10, 12]