JS实现十大排序

1 冒泡排序

思想：让相邻的两个数一直作比较，直到完成排序。
时间复杂度：O( n² )
稳定度：稳定

代码实现：
	var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
	for(var i =0 ; i < arr.length ; i++ ){ // i用来判断当前冒泡排序从位置几开始的
		for(var j = 0 ; j < arr.length ; j++){ // j用来判断相邻两个数位置是否交换
			if(arr[j] > arr[j+1]){
				var temp = arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = temp
			}
		}
	} 

2 选择排序

思想：假设第一个数为minNum，其下标为minIndex，用这个minNum和剩余的所有数比较，找出比第一个数还小的minNum，记录其minIndex；然后将其找出的minNum的minIndex与第一个默认的minNum的minIndex做交换；循环每个位置，直到完成排序
时间复杂度：O( n² )
稳定度：稳定

代码实现：
	var brr= [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
	var minIndex, temp
	function selectionSort (arr) {
		for(var i = 0 ; i < arr.length - 1 ; i++){
			minIndex = i // 默认第一个数为minNum，并记录它的minIndex
			for(var j = i + 1 ; j < arr.length ; j++){
				if(arr[j] < arr[minIndex]){ // 如果arr[j] < 默认的minNum
					minIndex = j // 记录这个新的minNum的minIndex
				}
			}
			// 找到一趟下来的最小minNum及其minIndex，并交换位置
			temp = arr[i]
			arr[i] = arr[minIndex]
			arr[minIndex] = temp
		}
		return arr
	} 
	selectionSort(brr)

3 插入排序

思想：从第二数开始，和前面已排好的序作比较，是否插入（>前  ， <后）
时间复杂度：O( n² )
稳定性：稳定

    // 直接比较前后的两个值
	var brr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
	var temp
	function insertSort (arr) {
	 for(var i = 1 ; i < arr.length ; i++){ // i用来判断当前循环做插入的是哪一个值的下标
	  for(j = i ; j - 1 >= 0 ; j--){// j用来判断当前当前的值和前一个值，是否做交换
	    if(arr[j] < arr[j-1]){ // 如果当前值小于前一个值，则进行交换
	     temp = arr[j]
	     arr[j] = arr[j-1]
	     arr[j-1] = temp
	    }
	  }
	 }
	 return arr
	}
	insertSort(brr)
	
或者：
    // 利用下标比较值
	var brr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
	var temp,curIndex
	function insertSort (arr) {
		for(var i = 1 ; i < arr.length ; i++){
			curIndex = i // 当前插入的值下标为i
			for(j = i - 1 ; j >= 0 ; j--){
				if(arr[curIndex] < arr[j]){ // 如果当前值小于它前面的值，则需要做交换
					temp = arr[j]
					arr[j] = arr[curIndex]
					arr[curIndex] = temp
					curIndex = j // 当两个值交换之后，当前做插入的这个值下标也随之改变成前一个
				}
			}
		}
		return arr
	}
	console.log(insertSort(brr)) 

4 快速排序

思想：
	 1. 取到mid = arr.length / 2的中间值
	 2. 将数组分为左右两个数组，以及取出来的中间值mid（splice方法）
	 3. 分别对左右数组进行递归排序
	 4. 将左右数组的递归跟中间值用concat函数返回
时间复杂度：O( nlogn )
稳定性：不稳定

var brr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
function quickSort (arr) {
	if(arr.length < 1){
		return arr
	}
	var left = []
	var right = []
	var index = Math.floor(arr.length / 2)
	var midNum = arr.splice(index, 1)[0]
	for(var i = 0 ; i < arr.length ; i++){
		if (arr[i] < midNum) {
			left.push(arr[i])
		} else{
			right.push(arr[i])
		}
	}
	return quickSort(left).concat(midNum, quickSort(right))
}
console.log(quickSort(brr))