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]