插排快排

插入排序

概念： 一个数组中，把未排序的元素在已排序的元素中比较，插入到合适的位置，直至数组结尾，开始时默认第一个元素是已经排好序的，从第二个开始拿出来比较，需要有一个标记以排好序的位置坐标，开始时的坐标为1（此为数组索引），每排好一个元素索引后移一位，当索引值为数组长度时表示排完了

	// 升序为例：
	function insertSort(arr){
		if(!arr.length || arr.length == 1) return arr
		let curVal  // 当前的带排序数据，该元素之前的元素已经排好了
		for(let i = 0 ； i < arr.length - 1 ; i++){
			let preIndex = i  // 数组从头开始遍历的，但前拿到的就是以排好序的左右一个元素，用索引标记
			// 拿到剩下未排序的第一个元素，和之前排好序的开始比对
			curVal = arr[i+1]
			// preIndex : 是标记索引最小为0，此处为倒序比较 ， 升序排列，注意循环进入的条件判断
			while(preIndex >= 0  && curVal < arr[preIndex]){
				arr[preIndex + 1] = arr[preIndex] // 逐个后移元素
				prevIndex--
			}
			// 循环结束，此时的prevIndex为要插入的位置，插入时在这个位置之后，索引+1
			arr[prevIndex+1] = curval
		}
		return arr
	}

插入排序适用于，数组中部分元素以排好序，小规模的排序

快排

冒泡的有一个改进，分治法的典型应用
概念： 选取数组中的一个元素作为排序的基数（一般选取第一个元素、最后一个元素，或者第一个，最后一个，加数组中间元素的中位数），将数组中小于、大于基数的元素划分在统一边
实现： 双指针法，一个指针记录数组遍历的位置，另一个指针记录分区位置（初始值为-1 ）。 做两个操作：
1， 比较遍历位置的元素和基数的大小，如果小于等于基数，分区指针后移一位，
2，然后比较分区和遍历两个指针的索引大小，如果遍历索引大于分区索引，则交换连个指针位置的元素。
3，如果遍历元素大于基数，分区指针不变，遍历后移，继续进行下一轮比较

	// 主函数，接受排序数组，排序分区索引，默认是原数组的开始和结束位置
	function quickSort(arr , left = 0 , right = arr.length -1){
		if(arr.length == 1 || !arr.length) return arr
		if(left < right){
			let partitionIndex = partition(arr , left , right) // 获取当前排序后分区排序后，基数索引位置
			quickSort(arr , left , partitionIndex-1) // 递归的排基数左边的值
			quickSort(arr , partitionIndex+1 , right) // 排右边的元素
		}
		return arr
	}
	
	// 寻找基准值索引
	function partition(arr , left , right){
		let standard = arr[right] // 拿最后一个元素作为基准数
		let subarea = left - 1  // 分区指针，当前分区左区间的索引减一
		for(let i = left ; i<= right ; i++){
			if(arr[i] <= standard){
				subarea++ // 遍历的元素小于等于基数，分区指针索引后移
				if(subarea < i){
					[arr[subarea] , arr[i]] = [arr[i] , arr[subarea]] // 利用解构，交换元素
				}
			}
		}
		return subarea
	}

简单说下为什么要创建分区索引并根据大小交换两个指针的元素位置，可以把分区指针理解为记录所有小于等于基数元素区间的最右面区间，分区索引之后的元素都是大于基数的元素，从第一次交换开始，就是找到了第一个小于基数的元素，并放在数组的开头，之后的每次交换也都是小于的，等于就是为了最后把末尾的基数交换到中间，此时的分区索引也就是 partition 方法找的分区索引，交换前分区索引加一，为了拿到第一个大于基数的元素