算法笔记本：十大基础排序算法
第一篇算法笔记
一、导读
本文示例代码使用：JavaScript
本文基础数据结构：JavaScript Array
1、排序定义
- 对一序列对象根据某种策略进行排序。
2、术语说明
- 时间复杂度： 一个算法执行所耗费的时间。
- 空间复杂度： 运行完一个程序所需内存的大小。
3、排序分类
4、复杂度小结
| 算法名称 | 最佳时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) |
| 插入排序 | O(n) | O(n2) | O(n2) | O(1) |
| 希尔排序 | O(n) | O(nlogn) | O(nlogn) | O(1) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(nlogn) |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) |
| 桶排序 | O(n+k) | O(n+k) | O(n2) | O(n+k) |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) |
| 基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n+k) |
二、基于比较的简单排序
冒泡排序、选择排序、插入排序，三者都是基于比较的排序原理，实现都非常易懂。所以笔者在复习排序算法时，都将这三者归为一类。
1、冒泡排序：
算法原理
（1）它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
（2）直到重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
代码实现
/**
* @desc 冒泡排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function bubble ( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let len = arr.length;
// 外层循环负责控制排序的趟数
for (let i = 0; i < len - 1; i++) {
// 内层循环负责执行一趟排序
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j + 1] < arr[j]) {
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
};
};
};
return arr;
}; 算法分析
最佳时间复杂度：O(n)
平均时间复杂度：O(n2)
最差时间复杂度：O(n2)
空间复杂度：O(1)
2、选择排序
算法原理
（1）将数组划分为已排序和未排序两部分，将未排序的元素最小元素一个个取出然后按顺序放置已排序的尾部。
（2）重复进行步骤1，直到未排序部分清空。
代码实现
/**
* @desc 选择排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function select( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let len = arr.length;
// 外层循环需要进行 len - 1 趟排序
for (let i = 0; i < len - 1; i++) {
let min = i;
// 内层循环从未排序的数组元素中比较出最小的一个
for (let j = i + 1; j < len; j++) {
if (arr[min] > arr[j]) {
min = j;
};
};
// 将其放在排序后的数组元素的最后
[arr[min], arr[i]] = [arr[i], arr[min]];
};
return arr;
}; 算法分析
最佳时间复杂度：O(n2)
平均时间复杂度：O(n2)
最差时间复杂度：O(n2)
空间复杂度：O(1)
3、插入排序
算法原理
（1）它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，通过比较，找到相应位置并插入。
代码实现
/**
* @desc 插入排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function insert ( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let len = arr.length;
for (let i = 1; i < len; i++) {
let tmp = arr[i];
let j;
for (j = i - 1; j >= 0; j--) {
if (tmp < arr[j]) {
arr[j+1] = arr[j];
} else {
break;
};
};
// 插入取出的数组元素
arr[j+1] = tmp;
};
return arr;
} 算法分析
最佳时间复杂度：O(n)
平均时间复杂度：O(n2)
最坏时间复杂度：O(n2)
空间复杂度：O(1)
三、基于比较的复杂排序
希尔排序、快速排序、归并排序、堆排序，都是基于比较的排序原理，但实现略有复杂。所以笔者在复习排序算法时，都将这三者归为一类。
1、希尔排序
算法原理：插入排序的改良版本
（1）希尔排序是按一定步长（间隔）将待排序数组分组，对每组使用直接插入排序算法排序；
（2）随着步长逐渐减少，当步长减至1时，排序终止。
代码实现：
/**
* @desc 插入排序
* @sort 升序排序
* @param {Array} arr
* @param {Number} gap
* @return {Array}
*/
function insert (arr, gap) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let len = arr.length;
for (let i = gap; i < len; i++) {
let tmp = arr[i];
for (var j = i - gap; j >= 0; j -= gap) {
if (tmp < arr[j]) {
arr[j+gap] = arr[j];
} else {
break;
};
};
arr[j+gap] = tmp;
};
return arr;
};
/**
* @desc 希尔排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function shell( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let len = arr.length;
let gap = 0;
while (gap < len/3) {
gap = 3 * gap + 1;
};
for (; gap > 0; gap = Math.floor((gap-1)/3)) {
console.log(gap);
arr = insert(arr, gap);
};
return arr;
} 算法分析
最佳时间复杂度：O(n)
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
空间复杂度：O(1)
2、快速排序
算法原理
（1）从原始数组中随机取出基准，然后，把比这个数小的放在这个数左边，比这个数大的放在这个数右边，一样大的和这个数放在一起
（2）基准的左右两边各自重复上述过程，直到左边或右边只剩下一个数（或零个数）无法继续为止。
递归实现
/**
* @desc 快速排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function quick( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let less = [];
let pivotList = [];
let more = [];
let result = [];
let length = arr.length;
let pivot = arr[0];
for (let i = 0; i < length; i++) {
if (arr[i] < pivot) {
less.push(arr[i]);
} else if (arr[i] > pivot) {
more.push(arr[i]);
} else {
pivotList.push(arr[i]);
};
};
less = quick(less);
more = quick(more);
result = result.concat(less, pivotList, more);
return result;
}; 迭代实现：同递归版本的显著区别在于，使用 stack 显式维护中间状态
/**
* @desc 分片
* @param {Array} arr 待分片的数组
* @param {Number} low 分片比较的下界
* @param {Number} high 分片比较的上界
* @return {Array}
*/
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
};
};
[arr[i+1], arr[high]] = [arr[high], arr[i+1]];
return i+1;
};
/**
* @desc 快速排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function quick( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let low = 0;
let high = arr.length - 1;
let pivot;
let stack = [low, high];
while (stack.length) {
high = stack.pop();
low = stack.pop();
pivot = partition(arr, low, high);
if (low < pivot - 1) {
stack.push(low);
stack.push(pivot - 1);
};
if (pivot + 1 < high) {
stack.push(pivot + 1);
stack.push(high);
};
};
return arr;
}; 算法分析
最佳时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差时间复杂度：O(n2)
空间复杂度：O(nlogn)
3、归并排序
算法原理
（1）将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
（2）将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
（3）重复步骤2，直到所有元素排序完毕
递归实现
/**
* @desc 归并
* @param {Array} left
* @param {Array} right
* @return {Array}
*/
function mergeArray( left, right ) {
let result = [];
while ( left.length > 0 && right.length > 0 ) {
if ( left[0] < right[0] ) {
result.push(left.shift());
} else {
result.push(right.shift());
};
};
return result.concat(left,right);
};
/**
* @desc 归并排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function merge( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
let length = arr.length;
if ( length <= 1 ) {
return arr;
};
let middle = Math.floor(length/2);
let left = merge(arr.slice(0,middle));
let right = merge(arr.slice(middle,length));
return mergeArray(left, right);
}; 迭代实现
/**
* @desc 归并
* @param {Array} left
* @param {Array} right
* @return {Array}
*/
function mergeArray( left, right ) {
let result = [];
while ( left.length > 0 && right.length > 0 ) {
if ( left[0] < right[0] ) {
result.push(left.shift());
} else {
result.push(right.shift());
};
};
return result.concat(left,right);
};
/**
* @desc 归并排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function merge( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
// 构造待归并的二维数组
let work = arr.map(item => [item]);
if (arr.length % 2 === 1) {
work.push([]);
};
for (let i = arr.length; i > 1; i = (i+1)/2) {
let j = 0;
for (let k = 0; k < i; j++, k+=2) {
work[j] = mergeArray(work[k], work[k+1]);
};
work[j] = [];
};
return work[0];
}; 算法分析
最佳时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
4、堆排序
算法原理
（1）将数组构建成大顶堆，将堆顶节点取出放入有序数组中。
（2）重复步骤 1。
代码实现
/**
* @desc 堆化：将数组构建成堆的形态
* @param {Array} arr 待调整的数组
* @param {Number} i 待调整二叉树的顶部节点
* @param {Number} len 待调整的数组大小
* @return {void}
*/
function heapify(arr, i, len) {
// 先取出当前元素 i
let tmp = arr[i];
// 从 i 节点的左子节点开始，也就是 2i+1 处开始
for(let k = i * 2 + 1; k < len; k = k * 2 + 1){
// 找出左子节点、右子节点中的最大值的下标
if (k + 1 < len && arr[k] < arr[k + 1]) {
k++;
}
// 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
if (arr[k] > tmp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
// 将 tmp 值放到最终的位置
arr[i] = tmp;
}
/**
* @desc 堆排序
* @sort 升序排序
* @param {Array} arr 待调整的数组
* @return {Array}
*/
function heapSort(arr) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
// 构建大顶堆
for (let i = parseInt(arr.length/2 - 1); i >= 0; i--) {
// 从第一个非叶子节点从下至上，从右至左调整结构
heapify(arr, i, arr.length);
}
// 堆排序
for (let j = arr.length - 1; j > 0; j--) {
// 交换堆顶元素与末尾元素
[arr[0], arr[j]] = [arr[j], arr[0]];
// 重新对堆进行调整
heapify(arr, 0, j);
}
return arr;
} 算法分析
最佳时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
空间复杂度：O(1)
四、基于统计的排序算法
桶排序、计数排序、基数排序，三者都是基于统计的排序原理。所以笔者在复习排序算法时，都将这三者归为一类。
1、桶排序
算法原理
（1）将待排序数组中的数，按照一定策略分组，依次放入大小不一的桶中。
（2）然后对每个桶内的元素进行排序。
（3）输出排序结果。
代码实现
/**
* @desc 桶排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function bucket ( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
let max = Math.max.apply(Math, arr);
let min = Math.min.apply(Math, arr);
let len = arr.length
let bucket = [];
let result = [];
// 遍历原数组，将数组元素归入相应桶内
for(let k = 0; k < len; k++){
index = parseInt(( arr[k] - min ) / len );
bucket[index] = !bucket[index] ? [] : bucket[index];
bucket[index].push( arr[k] );
};
// 根据计数数组输出排序后的数组
for(let l = 0; l < bucket.length; l++){
if (!!bucket[l]) {
// 桶排序内部需要使用其他排序来给桶排列
bucket[l].sort((a, b) => a - b);
result = result.concat( bucket[l] );
};
};
return result;
}; 算法分析
最佳时间复杂度：O(n)
平均时间复杂度：O(n+k)
最差时间复杂度：O(n2)
空间复杂度：O(n+k)
2、计数排序
算法原理
（1）将待排序数组中的数，生成计数分布数组。
（2）利用数组的有序性，从头遍历数组，输出排序结果。
代码实现
/**
* @desc 计数排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function count ( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
// 计数排序使用数组建立频率分布表，对负数进行排序，需要特殊处理一下。
let min = Math.min.apply(Math, arr);
if (min < 0) {
arr = arr.map(item => item + 1 - min);
};
let max = Math.max.apply(Math, arr);
let count = [];
let result = [];
// 建立计数数组
for(let j = 0; j < max + 1; j++){
count.push(0);
};
// 遍历原数组，形成原数组元素的频数分布
arr.forEach((item) => count[item] += 1);
// 根据计数数组输出排序后的数组
for (let l = 0; l < count.length; l++) {
for (let m = 0; m < count[l]; m++) {
result.push(l);
};
};
if (min < 0) {
result = result.map(item => item + min - 1);
};
return result;
}; 算法分析
待排序的数据范围很大（0 ～ k），计数排序需要大量内存，是典型的以空间换时间的排序算法。
最佳时间复杂度：O(n+k)
平均时间复杂度：O(n+k)
最差时间复杂度：O(n+k)
空间复杂度：O(n+k)
3、基数排序
算法原理
（1）将待排序数组中的数，根据二进制基数，从高位或低位，迭代生成桶大小不一致的桶。
（2）然后从小到大遍历各个桶，输出排序结果。
代码实现
/**
* @desc 基数排序
* @sort 升序排序
* @param {Array} arr
* @return {Array}
*/
function base( arr ) {
// 检验：非数组、空数组直接结束函数调用。
if (Object.prototype.toString.call(arr) !== '[object Array]' || arr.length === 0) {
return [];
}
if (arr.length === 1) {
return arr;
};
// 基数排序使用数组建立频率分布表，对零和负数进行排序，需要特殊处理一下。
let min = Math.min.apply(Math, arr);
if (min <= 0) {
arr = arr.map(item => item + 1 - min);
};
let maxDigit = Math.max.apply(Math, arr).toString().length;
let quenes = [];
let mod = 10;
let dev = 1;
for(let b = 0; b < maxDigit; b++, dev *= 10, mod *= 10){
// 将对应元素分配到对应的桶内
for(let i = 0, len = arr.length; i < len; i++){
let bucket = parseInt( (arr[i] % mod) / dev );
quenes[bucket] = !quenes[bucket] ? [] : quenes[bucket];
quenes[bucket].push( arr[i] );
};
// 输出本趟排序结果
let index = 0;
for(let j = 0; j < quenes.length; j++){
if (!!quenes[j]) {
for(let k = 0, len = quenes[j].length; k < len; k++){
arr[index++] = quenes[j].shift();
};
};
};
};
if (min <= 0) {
arr = arr.map(item => item + min - 1);
};
return arr;
}; 算法分析
k 为数组中的最大数的二进制位数。
最佳时间复杂度：O(n * k)
平均时间复杂度：O(n * k)
最差时间复杂度：O(n * k)
空间复杂度：O(n+k)
