十大排序详解js实现（冒泡，插入，选择，快排，归并，希尔，计数，堆，桶，基数）

一、冒泡排序

主要是相邻的两个元素进行比较，当左边元素大于右边元素时，对这两个元素进行交换位置；对于一个数组长度为n的数组，每一趟比较都会归位好一个元素，因此需要比较n趟；每一趟的比较流程就是：

• 第一趟：【下标1的元素】和【下标2的元素】比较并交换位置，【下标2的元素】和【下标3的元素】比较并交换位置。。。。。。【下标n-2的元素】和【下标n-1的元素】比较并交换位置。
• 第二趟：【下标1的元素】和【下标2的元素】比较并交换位置，【下标2的元素】和【下标3的元素】比较并交换位置。。。。。。【下标n-3的元素】和【下标n-2的元素】比较并交换位置。
• 。。。。。。。

注意：每一趟比较的次数，都会随着归位的元素个数增加而递减，因为已归位的元素将无需再进行比较了

function BubbleSort(arr){
	for(let i=0; i<arr.length-1; i++){  //比较趟数，每一趟都会将大的元素排到最后边，即每一趟都会产生一个有序的元素，后面的比较只需比到有序元素之前就好
		for(let j=0; j<arr.length-i-1; j++){	 //j
			if(arr[j]>arr[j+1]){  //两两比较，若左边大于右边则交换位置，即大的元素后移
				let temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12

二、插入排序

类似于整理扑克牌的排序，将数组第一个元素看做有序，从第二个元素开始依次看当前元素的前面所有元素中，【1】是否有比当前元素大的元素，有插入其（比当前元素大【从左到右看第一个比当前元素大的元素】）前边，没有则看下一个元素，然后重复【1】的操作。直至到数组最后一个元素。菜鸟教程动画演示链接

function InsertionSort(arr,index){	
	//递归退出条件，最后一个元素操作完毕
	if(index==arr.length){
		return arr;
	}
	//根据当前元素进行的操作
	for(let i=0; i<index; i++){			
		//找到了比当前下标元素大的元素arr[i]，将当前元素arr[index]插入到arr[i]前边；
		if(arr[i]>arr[index]){
			//arr.slice(0,i) 截取元素arr[i]之前的所有元素，不包括arr[i]
			//arr[index]放的位置为arr[i]之前一个下标
			//arr.slice(i,index) 截取元素arr[i]到arr[index]之间所有元素，不包括rr[index]
			//arr.slice(index+1,arr.length)截取当前元素arr[index]之后的所有元素
			//拼接组成新数组（即插入完成之后的数组）
			arr = [...arr.slice(0,i),arr[index],...arr.slice(i,index),...arr.slice(index+1,arr.length)]	
			//找到了比当前元素大的元素，退出for循环		
			break;
		}	
	}
	//递归调用，操作下一个元素
	return InsertionSort(arr,index+1);	
}
console.log(InsertionSort([33,0,2,32,1,9,11,2,32],1))	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、选择排序

最简单易理解的排序，每一次都找出最小或者最大的那个元素，然后依次进行放置，走n-1次即可完成排序，时间复杂度固定为O(n²)
（升序排列）步骤：

第一次：找出数组中最小的元素，放在第一个位置
第二次：找出剩下的元素中最小的元素，放在第二个位置
第三次：找出剩下的元素中最小的元素，放在第三个位置
。。。。。。。

每一次都将归位好一个元素，因此最后一个元素将自动归位，只需走n-1次

function selectionSort(arr){
	let minIndex;
	//排序位置（0~n-1是排好序的元素依次放入的位置）
	for(let i=0; i< arr.length-1;i++){
		//默认剩下的元素中第一个元素为最小值，记录其下标
		minIndex = i;
		//在剩下元素中的找出了比默认最小值更小的元素，将其下标存入minIndex 
		for(let k=i; k<arr.length; k++){		
			if(arr[k]<arr[minIndex]){
				minIndex = k;
			}
		}
		//for循环走完，找出剩余元素中的最小元素，交换位置，使找出的最小元素放入应该放的位置
		let temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

四、快速排序

实现步骤：

1.选择任意一个基准元素；从左到右搜索，
2.比基准小的元素放左边；
3.比基准大的元素放右边；
4.基准元素放中间；然后对基准左边和右边元素分别进行递归操作【上述四步操作】。

function quikSort(arr){
	//递归出口，数组元素小于等于1个时不用比较，直接返回数组
	if(arr.length <=1) return arr;
	//这里每次都选择第一个数为基准元素
	let point = arr[0];
	let leftArr = [] ,rightArr=[];
	for(let i=1; i<arr.length; i++){
		//比基准大放右数组，否则放左数组
		if(arr[i] > point){
			rightArr.push(arr[i]);
		}else{		
			leftArr.push(arr[i]);
		}
	}
	//构造新数组，对左右数组分别进行递归调用（重复【找基准元素，大放右小放左，基准元素放中间】这一操作）
	return [...quikSort(leftArr), point, ...quikSort(rightArr)];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

五、归并排序

未完待续。。。。。。