聊聊几种排序算法

Javascript API实现排序

let arr = [72, 45, 62, 12, 23, 67, 80, 56, 90, 6, 9];
arr.sort((a,b)=>a-b);

冒泡排序

基本思路：每次执行循环就把一个最大的数放到最后，就像气泡一样一个一个的冒；第一个循环遍历数组所有元素，第二个循环遍历是找出最大数值然后放在最后，时间复杂度为O(n2)。

function bubbleSort(arr) {
	let arrLength = arr.length
	for (let i = 0; i < arrLength; i++) {
		//两个数比较，i表示数组总个数，j代表第一个数（索引较前）最大就是倒数第二个数
		for (let j = 0; j < arrLength - 1 - i; j++) {
			if (arr[j + 1] < arr[j]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] //交换两个数值
			}
		}
	}
}

选择排序

基本思路：

• 每次执行循环找出最小值的索引值，并把这个最小放到前面，索引i前面的数组是依次排好的，时间复杂度为O(n2)。
• 与冒泡排序比较，冒泡排序是每次找出最大值放到最后而选择排序这是每次找出最小值放到前面。每次循环都会从乱序数组中找出最大（最小）值排到有序数组中。

function selectSort(arr){
	let arrLength = arr.length
	for (let i = 0; i < arrLength; i++) {
		let minIndex = i
		//每次循环找出最小值索引
		for(let j = i;j<arrLength;j++){
			if(arr[j]<arr[minIndex]){
				minIndex = j
			}
		}
		//把最小值放到前面数组
		[arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
	}
}

插入排序

基本思路：在已有排序的数组中找出自己位置，插入其中；

function insertSort(arr){
	let arrLength = arr.length
	let preIndex,current
	for(let i = 1;i<arrLength;i++){
		preIndex = i - 1 
		current = arr[i]
		//这个循环就是找出自己的位置，然后跳出，比较这个原始和current的大小，大则移后
		while(preIndex >= 0 && arr[preIndex] > current){
			arr[preIndex + 1] = arr[preIndex]
			45,72,72
			preIndex --;
		}
		//插入
		arr[preIndex + 1] = current;
	}
}

归并排序

基本思路：该算法是采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

function mergeSort(arr){
	let len = arr.length
	if(len<2){
		return arr
	}
	//把长度为n的输入序列分成两个长度为n/2的子序列
	let mid = Math.floor(len/2)
	let left = arr.slice(0,mid)
	let right = arr.slice(mid)
	//对这两个子序列分别采用归并排序
	return merge(mergeSort(left),mergeSort(right))
}
//将两个排序好的子序列合并成一个最终的排序序列。
function merge(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())
		}
	}
	while(left.length){
		result.push(left.shift())
	}
	while(right.length){
		result.push(right.shift())
	}
	return result
}

快速排序

基本思路：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
  (1)

  function quickSort(arr,left,right){
  	var len = arr.length,
  		partitionIndex,
  		left = typeof left != 'number' ? 0 : left,
  		right = typeof right != 'number' ? len - 1 : right;
  	if(left < right){
  		partitionIndex = partition(arr, left ,right)
  		quickSort(arr, left, partitionIndex-1)
  		quickSort(arr, partitionIndex+1, right)
  	}
  	return arr
  }
  //分区操作
  function partition(arr, left ,right){
  	var pivot = left,
  		index =pivot + 1;
  	for(var i = index;i <= right; i++){
  		if(arr[i] < arr[pivot]){
  			[arr[i],arr[index]] = [arr[index],arr[i]]
  			index++
  		}
  	}
  	[arr[pivot],arr[index-1]] = [arr[index-1],arr[pivot]]
  	return index-1
  }

  (2)

  function getStandard(arr,left,right){
  	var pivot = arr[left]
  		while(left < right){
  			while(left < right && arr[right] >= pivot){
  				right--  //找到的数都比pivot大，right--即可
  			} 
  			if(left < right){
  				arr[left] = arr[right] //如果找到比队首元素小，把后面的值赋值给arr[left]
  			} 
  			while(left < right && arr[left] <= pivot){
  				left++  //找到的数都比pivot小，left++即可
  			} 
  			if(left < right){
  				arr[right] = arr[left] //如果找到比队首元素大，把后面的值赋值给arr[right]
  			} 
  		}
  		arr[left] = pivot  //数组left右边的数都比pivot小，左边都比pivot大
  		return left; //返回基准
  }
  function quickSort(arr,low,high){
  	if(low < high) {
  		var standard = getStandard(arr,low,high)
  		quickSort(arr,low,standard -1)  //递归pivot右边数组
  		quickSort(arr,standard + 1,high) //递归pivot左边数组
  	}
  }