原文链接: https://interview.poetries.top/docs/excellent-docs/18-%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.html
冒泡排序
通过相邻元素比较和交换，使得每一趟循环都能找到未排序的子数组。
实现
function bubbleSort(list) {
var n = list.length
if(!n) return []
for(var i = 0; i < n; i++) {
for(var j = 0; j < n - i - 1; j++) {
if(list[j] > list[j + 1]) {
var temp = list[j + 1]
list[j + 1] = list[j]
list[j] = temp
}
}
}
return list
}
优化
单向冒泡
标记在一轮比较汇总中，如果没有需要交换的数据，说明数组已经是有序的，可以减少排序循环的次数。
function bubbleSort(list) {
var n = list.length
if(!n) return []
for(var i = 0; i < n; i++) {
let mark = true // 如果在一轮比较中没有出现需要交换的数据，说明数组已经是有序的
for(let j = 0; j < n - i - 1; j++) {
if(list[j] > list[j + 1]) {
var temp = list[j + 1]
list[j + 1] = list[j]
list[j] = temp
mark = false
}
}
if(mark) break
}
return list
}
双向冒泡
普通冒泡排序一轮只找到最大值或最小值其中之一，双向冒泡则多一轮筛选，既可以找到最大值，也可以找到最小值。
function bubbleSort(list) {
var low = 0
var high = list.length - 1
while(low < high) {
var mark = true
// 找到最大值放在右边
for(var i = low; i < high; i++) {
if(list[i] > list[i + 1]) {
var temp = list[i + 1]
list[i + 1] = list[i]
list[i] = temp
mark = false
}
}
high--
// 找到最小值放在左边
for(var j = high; j > low; j--) {
if(list[j] < list[j - 1]) {
var temp = list[j - 1]
list[j - 1] = list[j]
list[j] = temp
mark = false
}
}
low++
if(mark) break
}
return list
}
选择排序
依次找到剩余元素的最小值或者最大值，放置末尾或者开头。
实现
function selectSort(list) {
var n = list.length
var minIndex
for(var i = 0; i < n - 1; i++) {
minIndex = i
for(var j = i + 1; j < n; j++) {
if(list[j] < list[minIndex]) {
minIndex = j
}
}
var temp = list[i]
list[i] = list[minIndex]
list[minIndex] = temp
}
return list
}
插入排序
以第一个元素为有序数组，其后的元素通过在这个已有序的数组中找到合适的元素并插入。
实现
function insertSort(list) {
var n = list.length
var preIndex
var current
for(var i = 1; i < n; i++) {
preIndex = i - 1
current = list[i]
while(preIndex >=0 && list[preIndex] > current) {
list[preIndex + 1] = list[preIndex]
preIndex--
}
list[preIndex + 1] = current
}
return list
}
优化
拆半插入
function insertSort(list) {
var low
var high
var j
var temp
for (var i = 1; i < list.length; i++) {
if (list[i] < list[i - 1]) {
temp = list[i]
low = 0
high = i - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
if (temp > list[mid]) {
low = mid + 1
} else {
high = mid - 1
}
}
for (j = i; j > low; --j) {
list[j] = list[j - 1]
}
list[j] = temp
}
}
return list
}
希尔排序
通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。
function shellSort(list) {
var n = list.length
var gap = parseInt(n / 2) // 初始化步数
while(gap) { // 逐步缩小步数
for(var i = gap; i < n; i++) {
// 逐步和前面其他成员比较交换
for(var j = i - gap; j >=0; j -= gap) {
if(list[j] > list[j + gap]) {
var temp = list[j + gap]
list[j + gap] = list[j]
list[j] = temp
} else {
break
}
}
}
gap = parseInt(gap / 2)
}
}
归并排序
递归将数组分成两个序列，有序合并这两个序列。作为一种典型的分治法思想算法应用，归并排序的实现有两种方法：
- 自上而下的递归
- 自下而上的迭代
function mergeSort(list) {
var n = list.length
if(n < 2) return list
var mid = Math.floor(n / 2)
var left = list.slice(0, mid)
var right = list.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
var result = []
while(left.length && right.length) {
if(left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while(left.length) {
result.push(left.shift())
}
while(right.length) {
result.push(right.shift())
}
return result
}
快速排序
选择一个元素作为基数，把比基数小的元素放在它左边，比它大的放在右边（相当于二分），再不断递归基数左右的序列。快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，它是处理大数据最快的排序算法之一。
实现一
function quickSort(arr) {
if (arr.length<=1){
return arr;
}
var baseIndex = Math.floor(arr.length/2);//向下取整，选取基准点
var base = arr.splice(baseIndex,1)[0];//取出基准点的值，
// splice 通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。
// slice方法返回一个新的数组对象,不会更改原数组
//这里不能直接base=arr[baseIndex],因为base代表的每次都删除的那个数
var left=[];
var right=[];
for (var i = 0; i<arr.length; i++){
// 这里的length是变化的，因为splice会改变原数组。
if (arr[i] < base){
left.push(arr[i]);//比基准点小的放在左边数组，
}
}else{
right.push(arr[i]);//比基准点大的放在右边数组，
}
return quickSort(left).concat([base],quickSort(right));
}
实现二
function quickSort(list, left = 0, right = list.length - 1) {
var n = list.length
if(left < right) {
var index = left - 1
for(var i = left; i <= right; i++) {
if(list[i] <= list[right]) {
index++
var temp = list[index]
list[index] = list[i]
list[i] = temp
}
}
quickSort(list, left, index - 1)
quickSort(list, index + 1, right)
}
return list
}
堆排序
说到堆排序，首先需要了解一种数据结构--堆。堆是一种完全二叉树，这种结构通常可以用数组表示。在实际应用中，堆又可以分为最小堆和最大堆，两者区别如下：
- -max-heap property：对于所有除了根节点的节点i，A[Parent(i)] >= A[i]
- -min-heap property：对于除了根节点的节点i，A[Parent(i)] <= A[i]
堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排序；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排序。
实现
function heapSort(list) {
buildHeap(list)
// 循环 n-1 次，每次循环后交换堆顶元素和堆底元素并重新调整堆结构
for(var i = list.length - 1; i > 0; i--) {
[nums[i], nums[0]] = [nums[0], nums[i]]
adjustHeap(nums, 0, i)
}
return list
}
function buildHeap(nums) {
// 注意这里的头节点是从0开始的，所以最后一个非叶子节点结果是 parseInt(nums.length / 2) - 1
var start = parseInt(nums.length / 2) - 1
var size = nums.length
// 从最后一个非叶子节点开始调整，直至堆顶
for(var i = start; i >= 0; i--) {
adjustHeap(nums, i, size)
}
}
function adjustHeap(nums, index, size) {
// 交换后可能会破坏堆结构，需要循环使得每一个父节点都大于左右节点
while(true) {
var max = index
var left = index * 2 + 1 // 左节点
var right = index * 2 + 2 // 右节点
if(left < size && nums[max] < nums[left]) max = left
if(right < size && nums[max] < nums[right]) max = right
// 如果左右节点大雨当前节点则交换，并在循环一遍判断交换后是否破坏堆结构
if(index !== max) {
[nums[index], nums[max]] = [nums[max], nums[index]]
index = max
} else {
break
}
}
}
计数排序
以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JS 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但是不可以排列小数。
实现
function countingSort(nums) {
var list = []
var max = Math.max(...nums)
var min = Math.min(...nums)
for(var i = 0; i < nums.length; i++) {
var temp = nums[i]
list[temp] = list[temp] + 1 || 1
}
var index = 0
for(var i = min; i <= max; i++) {
while(list[i] > 0) {
nums[index++] = i
list[i]--
}
}
return list
}
桶排序
取 n 个桶，根据数组的最大值和最小值确认每个桶存放的数的区间，将元素插入到相应的桶里，最后再合并各个桶。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量。
- 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中。
function bucketSort(nums) {
// 桶的个数，只要是正数都行
var num = 5
var max = Math.max(...nums)
var min = Math.min(...nums)
// 计算每个桶存放的数值范围，至少为 1
var range = Math.ceil((max - min) / num) || 1
// 创建二维数组，第一维表示第几个桶，第二维表示桶里放的数
var 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会出现5
index = 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;
});
// 修改回原数组
var res = [].concat.apply([], arr);
nums.forEach((val, i) => {
nums[i] = res[i];
});
return nums;
}
基数排序
使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。但只能排列正整数，因为遇到负号和小数点无法进行比较。
基数排序有两种方法：
- MSD 从高位开始进行排序
- LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
function radixSort(nums) {
// 计算位数
function getDigits(n) {
var sum = 0;
while (n) {
sum++;
n = parseInt(n / 10);
}
return sum;
}
// 第一维表示位数即0-9，第二维表示里面存放的值
var arr = Array.from(Array(10)).map(() => Array());
var max = Math.max(...nums);
var maxDigits = getDigits(max);
for (var i = 0, len = nums.length; i < len; i++) {
// 用0把每一个数都填充成相同的位数
nums[i] = (nums[i] + '').padStart(maxDigits, 0);
// 先根据个位数把每一个数放到相应的桶里
var temp = nums[i][nums[i].length - 1];
arr[temp].push(nums[i]);
}
// 循环判断每个位数
for (var i = maxDigits - 2; i >= 0; i--) {
// 循环每一个桶
for (var j = 0; j <= 9; j++) {
var temp = arr[j]
var len = temp.length;
// 根据当前的位数i把桶里的数放到相应的桶里
while (len--) {
var str = temp[0];
temp.shift();
arr[str[i]].push(str);
}
}
}
// 修改回原数组
var res = [].concat.apply([], arr);
nums.forEach((val, index) => {
nums[index] = +res[index];
});
return nums;
}
阅读全文