各种排序

快速排序

思路就是获取一个基准值，小于基准值的到左边， 大于的到右边，然后把结果拼起来即可， 下面的题解可能空间复杂度略高

function quickSort(arr) {
	if (arr.length <= 1) return arr
	// 获取基准值， 比如获取中间值
	// var pivotIndex = Math.floor(arr.length / 2)
	var pivotIndex = 0
	// 获取中间值
	var pivot = arr.splice(pivotIndex, 1)[0]
	var left = []
	var right = []
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i])
		} else {
			right.push(arr[i])
		}
	}
	return quickSort(left).concat([pivot], quickSort(right))
}

console.log(quickSort([6, 5, 4, 3, 1, 2, 9, 10, 12]))

下面是空间复杂度相对低的实现， 思路是一致的， 找一个基准值，对向指针遍历

function sort(arr, left, right) {
  // 左指针
  let i = left;
  // 右指针
  let j = right;
  // 存放基准值
  let pivot = arr[i];
  while (i < j) {
    // j从右往左找到第一个小于基准的值
    while (arr[j] > pivot && i < j) {
      j--;
    }
    if (i < j) {
      // 将小于基准的值赋值给位置i
      arr[i] = arr[j];
      i++;
    }
    // i从左往往找到第一个小于基准的值
    while (arr[i] < pivot && i < j) {
      i++;
    }
    if (i < j) {
      arr[j] = arr[i];
      j--;
    }
  }
  arr[i] = pivot;
  if (left < i - 1) {
    sort(arr, left, i - 1);
  }
  if (i + 1 < right) {
    sort(arr, i + 1, right);
  }
}

归并排序

（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

function sort(arr) {
  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(sort(left), sort(right));
}

function merge(left, right) {
  console.log(left, right);
  let result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }
  return result;
}

看图应该更好理解， 时间复杂度为O(nlog(n))

插入排序

每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

function insertSort(arr) {
	if (!arr || arr.length === 1) {
		return arr || []
	}
	let result = []
	result.push(arr[0])
	for (let i = 1; i < arr.length; i++) {
		insert(arr[i])
	}

	function insert(val) {
		if (val <= result[0]) {
			result.unshift(val)
			return
		}
		if (val >= result[result.length - 1]) {
			result.push(val)
			return
		}
		for (let i = 0, len = result.length; i < len - 1; i++) {
			if (result[i] < val && val < result[i + 1]) {
				result.splice(i + 1, 0, val)
				break
			}
		}
	}
	return result
}

冒泡之类的就不说了

冒泡排序的实现和优化

function bubbleSort(arr) {
	let i = arr.length - 1
	while (i > 0) {
		let pos = 0
		for (let j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				pos = j
				const temp = arr[j]
				arr[j] = arr[j + 1]
				arr[j + 1] = temp
			}
    }
		i = pos
	}
}