[数据结构与算法]常见的排序算法

常见的排序算法

排序中通用的函数

//判对应的值是否为空
function checkArray(array) {
    if (!array) return
}
//交换两个位置的值
function swap(array, left, right) {
    let rightValue = array[right]
    array[right] = array[left]
    array[left] = rightValue
}

冒泡排序

? 从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 2 的位置。

function bubble(array){
	checkArray(array);
	for (var i = array.length - 1; i > 0; i--) {
		for (var j = 0; j < i; j++) {
			if (array[j]>array[j+1]) {
				swap(array,j,j+1);
			}
		}
	}
	return array;
}

插入排序

? 第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

function insertion(array){
	checkArray(array);
	for (let i = 1; i < array.length; i++) {
		for (let j = i - 1;j >= 0 && array[j] > array[j+1]; j--) {
			swap(array, j, j+1);
		}
	}
	return array;
}

选择排序

? 遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

function choose(array){
	checkArray(array);
	for (let i = 0; i < array.length-1; i++) {
		let minIndex = i;
		for (let j = i + 1; j < array.length; j++) {
			minIndex = array[j] < array[minIndex] ? j : minIndex;
		}
		swap(array, i, minIndex);
	}
	return array;
}

归并排序

? 递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组。假设我有一组数组 [3, 1, 2, 8, 9, 7, 6] ，中间数索引是 3，先排序数组 [3, 1, 2, 8] 。在这个左边数组上，继续拆分直到变成数组包含两个元素（如果数组长度是奇数的话，会有一个拆分数组只包含一个元素）。然后排序数组 [3, 1] 和 [2, 8] ，然后再排序数组 [1, 3, 2, 8] ，这样左边数组就排序完成，然后按照以上思路排序右边数组，最后将数组 [1, 2, 3, 8] 和 [6, 7, 9] 排序。

function sort(array){
	checkArray(array);
	mergeSort(array, 0, array.length-1);
	return array;
}
function mergeSort(array, left, right) {
	// 左右索引相同说明已经只有一个数
	if (left === right) return;
	// 等同于 `left + (right - left) / 2`
	// 相比 `(left + right) / 2` 来说更加安全，不会溢出
	// 使用位运算是因为位运算比四则运算快
	let mid = parseInt(left + ((right - left) >> 1));
	mergeSort(array, left, mid);
	mergeSort(array, mid + 1, right);

	let help = [];
	let i = 0;
	let p1 = left;
	let p2 = mid + 1;
	while(p1 <= mid && p2 <= right){
		help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
	}
	while (p1 <= mid) {
		help[i++] = array[p1++];
	}
	while (p2 <= right) {
		help[i++] = array[p2++];
	}
	for (let i = 0; i < help.length; i++) {
		array[left + i] = help[i];
	}
	return array;

}

快排

? 随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作。

function sort(array) {
	checkArray(array);
	quickSort(array, 0, array.length - 1);
	return array;
}
function quickSort(array, left, right) {
	if (left < right) {
		swap(array, , right)
		// 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低
		let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right);
		quickSort(array, left, indexs[0]);
		quickSort(array, indexs[1] + 1, right);
	}
}
function part(array, left, right) {
	let less = left - 1;
	let more = right;
	while (left < more) {
		if (array[left] < array[right]) {
			// 当前值比基准值小，`less` 和 `left` 都加一
			++less;
			++left;
		} else if (array[left] > array[right]) {
			// 当前值比基准值大，将当前值和右边的值交换
			// 并且不改变 `left`，因为当前换过来的值还没有判断过大小
			swap(array, --more, left);
		} else {
			// 和基准值相同，只移动下标
			left++;
		}
	}
	// 将基准值和比基准值大的第一个值交换位置
	// 这样数组就变成 `[比基准值小, 基准值, 比基准值大]`
	swap(array, right, more);
	return [less, more];
}