JS常见算法小总结

大家好，又见面了，我是你们的朋友全栈君。

首先我们创建一个含有十万个数字的数组：

let array = [];
for (let i = 0; i < 100000; i++) { 
   
	array.push(i)
}

接下来我们一起分析各个算法的性能：

首先来测试冒泡排序：

function bubbleSort(arr) { 
   
	for(let i = 0; i < arr.length; i++) { 
   
		for(let j = 0; j < arr.length - i - 1; j++) { 
   
			if(arr[j] > arr[j+1]) { 
   
				let temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}
console.time()
bubbleSort(array);
console.timeEnd()

可以看到冒泡排序的性能很差。

接下来再来测试选择排序的性能：

function selectionSort(arr) { 
   
	let len = arr.length;
	let minIndex, temp;
	for(let i = 0; i < len - 1; i++) { 
   
		minIndex = i;
		for(var j = i + 1; j < len; j++) { 
   
			if (arr[j] < arr[minIndex]) { 
   
				minIndex = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	return arr;
}
console.time()
selectionSort(array)
console.timeEnd()

可以看到比冒泡排序快了一倍。

我们再来测试一下插入排序的性能：

//插入排序 过程就像你拿到一副扑克牌然后对它排序一样
function insertionSort(arr) { 
   
	let len = arr.length;
	let preIndex, current;
	// 我们认为arr[0]已经被排序，所以i从1开始
	for (let i = 1; i < len; i++) { 
   
		preIndex = i - 1;
		current = arr[i];
		while (preIndex >= 0 && arr[preIndex] > current) { 
   
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = current;
	}
	return arr;
}
console.time()
insertionSort(array)
console.timeEnd()

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
才2.96ms？？？？
我弄错了？？？在测试一下！！！结果还是这个时间左右。如果你认为这个是最快其实就误解了，因为我们现在数组里面的值刚刚好是从小到大排序的所以它才会这么快，如果对我们的这个数组做个反转再来使用插入排序的话，插入排序就会很慢很慢。

当目标是升序排序，最好情况是序列本来已经是升序排序，那么只需比较n-1次，时间复杂度O(n)。最坏情况是序列本来是降序排序，那么需比较n(n-1)/2次，时间复杂度O(n^2)。所以平均来说，插入排序的时间复杂度是O(n^2)。显然，次方级别的时间复杂度代表着插入排序不适合数据特别多的情况，一般来说插入排序适合小数据量的排序。

二分查找

function binary_search(arr, l, r, v) { 
   
	if (l > r) { 
   
		return -1;
	}
	let m = parseInt((l + r) / 2);
	if (arr[m] == v) { 
   
		return m;
	} else if (arr[m] < v) { 
   
		return binary_search(arr, m + 1, r, v);
	} else { 
   
		return binary_search(arr, l, m - 1, v);
	}
}

将二分查找运用到之前的插入排序中，形成二分插入排序。

接下来是快速排序

function qSort(arr) { 
   
	//声名并初始化左边的数组和右边的数组
	let left = [], right = [];
	// 使用数组第一个元素作为基准值
	let base = arr[0];
	//当数组长度只有1或者为空时，直接返回数组，不需要排序
	if (arr.length <= 1) return arr;
	//进行遍历
	for (let i = 1, len = arr.length; i < len; i++) { 
   
		if (arr[i] <= base) { 
   
			//如果小于基准值，push到左边的数组
			left.push(arr[i])
		} else { 
   
		//如果大于基准值，push到右边的数组
			right.push(arr[i]);
		}
	}
	//递归并且合并数组元素
	return [...qSort(left), base, ...qSort(right)];
}

补充：

在这段代码中，我们可以看到，这段代码实现了通过pivot区分左右部分，然后递归的在左右部分继续取pivot排序，实现了快速排序的文本描述，也就是说该的算法实现本质是没有问题的。

虽然这种实现方式非常的易于理解。不过该实现也是有可以改进的空间，在这种实现中，我们发现在函数内定义了left/right两个数组存放临时数据。随着递归的次数增多，会定义并存放越来越多的临时数据，需要Ω(n)的额外储存空间。

因此，像很多算法介绍中，都使用了原地（in-place）分区的版本去实现快速排序，我们先介绍什么是原地分区算法。

原地(in-place)分区算法描述

1. 从数列中挑选一个元素，称为“基准”（pivot），数组第一个元素的位置作为索引。
2. 遍历数组，当数组数字小于或者等于基准值，则将索引位置上的数与该数字进行交换，同时索引+1。
3. 将基准值与当前索引位置进行交换。

通过以上3个步骤，就将以基准值为中心，数组的左右两侧数字分别比基准值小或者大了。这个时候在递归的原地分区，就可以得到已排序后的数组。

原地分区算法实现

//交换数组元素位置
function swap(array, i, j) { 
   
	let temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

function partition(array, left, right) { 
   
	let index = left;
	let pivot = array[right];  //取最后一个数字当做基准值，这样方便遍历
	for (let i = left; i < right; i++) { 
   
		if (array[i] <= pivot) { 
   
			swap(array, index, i);
			index++;
		}
	}
	swap(array, right, index);
	return index;
}

因为我们需要递归的多次原地分区，同时，又不想额外的地址空间所以，在实现分区算法的时候会有3个参数，分别是原数组array，需要遍历的数组起点left以及需要遍历的数组终点right
最后返回一个已经排好序的index值用于下次递归，该索引对应的值一定比索引左侧的数组元素小，比所有右侧的数组元素大。

再次基础上我们还是可以进一步的优化分区算法，我们发现 <=pivot可以改为<pivot,这样可以减少一次交换。

原地分区版快速排序实现

function quickSort(array) { 
   
	function swap(array, i, j) { 
   
		let temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	function partition(array, left, right) { 
   
		let index = left;
		let pivot = array[right];	//取最后一个数字当做基准值，这样方便遍历
		for (let i = left; i < right; i++) { 
   
			if (array[i] < pivot) { 
   
				swap(array, index, i);
				index++;
			}
		}
		swap(array, right, index);
		return index;
	}
	function sort(array, left, right) { 
   
		if (left > right) { 
   
			return;
		}
		let storeIndex = partition(array, left, right);
		sort(array, left, storeIndex - 1);
		sort(array, storeIndex + 1, right);
	}
	sort(array, 0, array.length - 1);
	return array;
}