排序算法总结

JS 十大排序算法

冒泡排序

作为最简单的排序算法之一，冒泡排序感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值或最小值。

最好：O(n)，只需要冒泡一次数组就有序了。
最坏：O(n²)
平均：O(n²)

冒泡排序动图演示：

单向冒泡

function bubbleSort(nums) {for(let i=0, len=nums.length; i<len-1; i++) {// 如果一轮比较中没有需要交换的数据，则说明数组已经有序。主要是对[5,1,2,3,4]之类的数组进行优化let mark = true;for(let j=0; j<len-i-1; j++) {if(nums[j] > nums[j+1]) {[nums[j], nums[j+1]] = [nums[j+1], nums[j]];mark = false;}}if(mark)  return;}
}

双向冒泡

普通的冒泡排序在一趟循环中只能找出一个最大值或最小值，双向冒泡则是多一轮循环既找出最大值也找出最小值。

function bubbleSort_twoWays(nums) {let low = 0;let high = nums.length - 1;while(low < high) {let mark = true;// 找到最大值放到右边for(let i=low; i<high; i++) {if(nums[i] > nums[i+1]) {[nums[i], nums[i+1]] = [nums[i+1], nums[i]];mark = false;}}high--;// 找到最小值放到左边for(let j=high; j>low; j--) {if(nums[j] < nums[j-1]) {[nums[j], nums[j-1]] = [nums[j-1], nums[j]];mark = false;}}low++;if(mark)  return;}
}

选择排序

选择排序须知：
在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

和冒泡排序相似，区别在于选择排序是将每一个元素和它后面的元素进行比较和交换。

最好：O(n²)
最坏：O(n²)
平均：O(n²)

选择排序动图演示：

代码演示：

function selectSort(nums) {for(let i=0, len=nums.length; i<len; i++) {for(let j=i+1; j<len; j++) {if(nums[i] > nums[j]) {[nums[i], nums[j]] = [nums[j], nums[i]];}}}
}

插入排序

以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

最好：O(n)，原数组已经是升序的。
最坏：O(n²)
平均：O(n²)

插入排序动图演示：

代码演示：

function insertSort(nums) {for(let i=1, len=nums.length; i<len; i++) {let temp = nums[i];let j = i;while(j >= 0 && temp < nums[j-1]) {nums[j] = nums[j-1];j--;}nums[j] = temp;}
}

快速排序

选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。

最好：O(n * logn)，所有数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。
最坏：O(n²)，所有数都分布在基数的一边，此时划分左右序列就相当于是插入排序。
平均：O(n * logn)

快速排序动图演示：

归并排序

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）

1. 自下而上的迭代
2. 递归将数组分为两个序列，有序合并这两个序列。

最好：O(n * logn)
最坏：O(n * logn)
平均：O(n * logn)

归并排序动图演示：

桶排序

取 n 个桶，根据数组的最大值和最小值确认每个桶存放的数的区间，将数组元素插入到相应的桶里，最后再合并各个桶。

最好：O(n)，每个数都在分布在一个桶里，这样就不用将数插入排序到桶里了(类似于计数排序以空间换时间)。
最坏：O(n²)，所有的数都分布在一个桶里。
平均：O(n + k)，k表示桶的个数。

function bucketSort(nums) {// 桶的个数，只要是正数即可let num = 5;let max = Math.max(...nums);let min = Math.min(...nums);// 计算每个桶存放的数值范围，至少为1，let range = Math.ceil((max - min) / num) || 1;// 创建二维数组，第一维表示第几个桶，第二维表示该桶里存放的数let arr = Array.from(Array(num)).map(() => Array().fill(0));nums.forEach(val => {// 计算元素应该分布在哪个桶let index = parseInt((val - min) / range);// 防止index越界，例如当[5,1,1,2,0,0]时index会出现5index = index >= num ? num - 1 : index;let temp = arr[index];// 插入排序，将元素有序插入到桶中let j = temp.length - 1;while(j >= 0 && val < temp[j]) {temp[j+1] = temp[j];j--;}temp[j+1] = val;})// 修改回原数组let res = [].concat.apply([], arr);nums.forEach((val, i) => {nums[i] = res[i];})
}

基数排序

使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。但只能排列正整数，因为遇到负号和小数点无法进行比较。

最好：O(n * k)，k表示最大值的位数。
最坏：O(n * k)
平均：O(n * k)

基数排序动图演示：

代码演示：

function radixSort(nums) {// 计算位数function getDigits(n) {let sum = 0;while(n) {sum++;n = parseInt(n / 10);}return sum;}// 第一维表示位数即0-9，第二维表示里面存放的值let arr = Array.from(Array(10)).map(() => Array());let max = Math.max(...nums);let maxDigits = getDigits(max);for(let i=0, len=nums.length; i<len; i++) {// 用0把每一个数都填充成相同的位数nums[i] = (nums[i] + '').padStart(maxDigits, 0);// 先根据个位数把每一个数放到相应的桶里let temp = nums[i][nums[i].length-1];arr[temp].push(nums[i]);}// 循环判断每个位数for(let i=maxDigits-2; i>=0; i--) {// 循环每一个桶for(let j=0; j<=9; j++) {let temp = arr[j]let len = temp.length;// 根据当前的位数i把桶里的数放到相应的桶里while(len--) {let str = temp[0];temp.shift();arr[str[i]].push(str);}}}// 修改回原数组let res = [].concat.apply([], arr);nums.forEach((val, index) => {nums[index] = +res[index];}) 
}

计数排序

以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。

最好：O(n + k)，k是最大值和最小值的差。
最坏：O(n + k)
平均：O(n + k)

计数排序动图演示：

代码演示：

function countingSort(nums) {let arr = [];let max = Math.max(...nums);let min = Math.min(...nums);// 装桶for(let i=0, len=nums.length; i<len; i++) {let temp = nums[i];arr[temp] = arr[temp] + 1 || 1;}let index = 0;// 还原原数组for(let i=min; i<=max; i++) {while(arr[i] > 0) {nums[index++] = i;arr[i]--;}}
}