冒泡排序

排序的效果图

解法

当前解法为升序

冒泡排序的特点，是一个个数进行处理。第i个数，需要与后续的len-i-1个数进行逐个比较。

为什么是 `len-i-1`个数？

因为数组末尾的i个数，已经是排好序的，确认位置不变的了。

为什么确认位置不变，因为它们固定下来之前，已经和前面的数字都一一比较过了。

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

	return arr;
}
复制代码

快速排序

概要

快速排序，使用的是分治法的思想。
通过选定一个数字作为比较值，将要排序其他数字，分为 >比较值 和 <比较值，两个部分。并不断重复这个步骤，直到只剩要排序的数字只有本身，则排序完成。

效果图

解法

function quickSort(arr){

	sort(arr, 0, arr.length - 1);
	return arr;


	function sort(arr, low, high){
		if(low >= high){
			return;
		}
	
		let i = low;
		let j = high;
		const x = arr[i]; // 取出比较值x，当前位置i空出，等待填入
		while(i < j){
			// 从数组尾部，找出比x小的数字
			while(arr[j] >= x && i < j){
				j--;
			}
			// 将空出的位置，填入当前值， 下标j位置空出
			// ps：比较值已经缓存在变量x中
			if(i < j){
				arr[i] = arr[j]
				i++;
			}

			// 从数组头部，找出比x大的数字
			while(arr[i] <= x && i < j){
				i++;
			}
			// 将数字填入下标j中，下标i位置突出
			if(i < j){
				arr[j] = arr[i]
				j--;
			}
			// 一直循环到左右指针i、j相遇，
			// 相遇时，i==j, 所以下标i位置是空出的
		}

		arr[i] = x; // 将空出的位置，填入缓存的数字x，一轮排序完成

		// 分别对剩下的两个区间进行递归排序
		sort(arr, low, i - 1);
		sort(arr, i+1, high);
	}
}
复制代码

希尔排序

概要

希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。由希尔（Donald Shell）于1959年提出。
特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。
由于增量是从大到小，逐次递减，所以也称为缩小增量排序。

效果图

解法

注意点
插入排序时，并不是一个分组内的数字一次性用插入排序完成，而是每个分组交叉进行。

执行插入时，使用交换法

function shellSort(arr){
	// 分组规则 gap/2 递减
	for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
		for(let i = gap; i < arr.length; i++){
			let j = i;
			// 分组内数字，执行插入排序，
			// 当下标大的数字，小于 下标小的数字，进行交互
			// 这里注意，分组内的数字，并不是一次性比较完，需要i逐步递增，囊括下个分组内数字
			while(j - gap >= 0 && arr[j] < arr[j - gap]){
				swap(j, j-gap);
				j = j - gap;
			}
		}
	}

	return arr;

	function swap(a, b){
		const tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}
复制代码

执行插入时，使用移动法

function shellSort(arr){

	for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
		for(let i = gap; i < arr.length; i++){
			let j = i;
			const x = arr[j]; // 缓存数字，空出位置

			while(j - gap >= 0 && x < arr[j-gap]){
				arr[j] = arr[j - gap]; // 将符合条件的数字，填入空出的位置
				j = j - gap;
			}
			arr[j] = x; // 最后，将缓存的数字，填入空出的位置
		}
	}

	return arr;
}
复制代码