@[toc]
已经有很多排序算法的文章了，这里主要是做一个自己的总结。 内容大部分整合自《算法第四版》，图示大部分来自菜鸟教程网。语言选择的当然是JavaScript啦~ 代码可以直接在LeetCode的912.排序数组 (opens new window)题目上运行
在此之前先定义一个交换数组中两个元素的函数
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
# 1. 冒泡排序 （简单）
# 流程
- 比较相邻的元素。如果前者大于后者就交换
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
# 图示
# 代码
参考代码1
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length - i -1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
return nums;
};
参考代码2 优化冒泡排序
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
for (let i = 0; i < nums.length; i++) {
let flag = true;
for (let j = 0; j < nums.length - i -1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;
}
}
if(flag) {
return;
}
}
return nums;
};
# 复杂度分析
时间复杂度：$O(N^2)$，这里 $N$是数组的长度； 空间复杂度：$O(1)$，使用到常数个临时变量。
# 2. 选择排序（简单）
一种最简单的排序算法：首先找到数组中最小的元素，将它和数组中的第一个元素交换位置，然后在剩下的元素中找到最小的，与第二个元素交换位置，直到整个数组排序。（不断选择剩余数组中最小的元素）
# 流程
- 首先在未排序序列中找到最小元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
- 重复第二步，直到所有元素均排序完毕
# 图示
# 代码
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
for (let i = 0; i < nums.length; i++) {
let min = i;
// 已排序区间 [0, i) ，未排序区间 [i+1 , len)
// 遍历 i+1 之后的元素找到最小元素的索引
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
swap(nums, i, min);
}
return nums;
};
# 复杂度分析
- 对于长度为N的数组，选择排序需要大约$N^2/2$次比较和$N$次交换。
- 有两个特点：①运行时间和输入无关 ②数据移动是最少的，交换次数和数组的大小是线性关系
时间复杂度：$O(N^2)$，这里 $N$ 是数组的长度； 空间复杂度：$O(1)$，使用到常数个临时变量。
# 3. 插入排序（重点）
# 流程
每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组，有限次操作以后，数组整体有序
# 图示
# 代码
参考代码1（交换元素）（算法第四版的思路）
/**
* 插入排序
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
// 已排序区间 [0, i) ，未排序区间 [i , len)
// 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for (let i = 1; i < nums.length; i++) {
// 从右往左遍历
for (let j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
// 只要nums[j]比前一个元素nums[j-1]小，就交换这两个元素
swap(nums, j, j - 1);
}
}
return nums;
};
参考代码2（移动元素）
/**
* 插入排序
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
for (let i = 1; i < nums.length; i++) {
// 已排序区间 [0, i) ，未排序区间 [i , len)
// 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
// 先暂存这个元素，然后之前元素逐个后移，留出空位
let temp = nums[i];
let j = i;
while(j > 0 && temp < nums[j - 1]) {
// 只要nums[j]比前一个元素nums[j-1]小，将nums[j-1]移动到nums[j]
nums[j] = nums[j - 1];
j--;
}
// 找到位置j，将i的值放在j上
nums[j] = temp;
}
return nums;
};
# 复杂度分析
插入排序对部分有序的数组和“短数组”很有效
时间复杂度：$O(N^2)$，这里 $N$ 是数组的长度； 空间复杂度：$O(1)$，使用到常数个临时变量。
# 4. 希尔排序（了解）
对插入排序的改进！插入排序效率低的原因是它只会交换相邻的元素 希尔排序的思想是使数组中任意间隔为h的元素都是有序的，即带间隔地使用插入排序
# 流程
设置增量序列是一个超参数，需要经验。下面的代码给出了两种定义方式
# 图示
# 代码
设置增量序列是一个超参数，需要经验。下面的代码给出了两种定义方式
参考代码1（交换元素）
var shellSortArray = function (nums) {
const N = nums.length;
// 使用 Knuth 增量序列
let h = 1;
while (h < N / 3) {
h = 3 * h + 1; // 动态定义间隔序列
}
while (h >= 1) {
for (let i = h; i < N; i++) {
for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
swap(nums, j, j - h);
}
}
h = Math.floor(h / 3)
}
};
参考代码2（移动元素）
var shellSortArray2 = function (nums) {
const N = nums.length;
for (let gap = N / 2; gap > 0; gap = Math.floor(gap/2)) {
for (let i = gap; i < N; i++) {
let temp = nums[i];
let j = i;
while(j >= gap && nums[j - gap] > temp){
nums[j] = nums[j - gap];
j -= gap;
}
nums[j] = temp;
}
}
return nums;
};
# 复杂度分析
在输入随机排序数组的情况下，我们在数学上还不知道希尔排序所需要的平均比较次数
# 5. 归并排序（重点）
将两个有序的数组归并成一个更大的有序数组
# 流程
分治算法、递归调用
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。
# 图示
# 代码
使用JavaScript中数组的队列方法，使得归并排序实现起来异常简单，不用涉及过多的指针问题
/**
* 归并排序算法
* @param {*} arr 数组
* @returns 有序数组
*/
function mergeSort(arr) {
// 采用自顶向下的递归方法
const N = arr.length;
if (N < 2) {
// 递归出口，数组只有一个元素，直接返回这个数组
return arr;
}
// x >> 1 是位运算中的右移运算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2)
// N >> 1 和 Math.floor(N / 2) 等价
let middle = N >> 1;
// 拆分为两个子数组
let left = arr.slice(0, middle);
let right = arr.slice(middle);
// 递归调用mergeSort
return merge(mergeSort(left), mergeSort(right));
}
/**
* 对两个有序数组进行合并操作
* @param {*} left left数组
* @param {*} right right数组
* @returns 一个有序数组temp
*/
function merge(left, right) {
// 临时数组存储归并后的数据
const temp = [];
// 两个数组都还没有遍历结束
while (left.length && right.length) {
// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
if (left[0] <= right[0]) {
// left[0]小，删除left数组中第一项left[0]，并将它放入temp数组中
temp.push(left.shift());
} else {
// 删除right数组中第一项，并将它放入temp数组中
temp.push(right.shift());
}
}
// left数组还有元素，right数组遍历完了
while (left.length) {
// 将left数组剩下的元素都放入temp数组中
temp.push(left.shift());
}
// right数组还有元素，left数组遍历完了
while (right.length) {
temp.push(right.shift());
}
// 返回排序好的数组
return temp;
}
我们不使用JavaScript中Array自带的一些方法，使用指针的方式按照《算法（第四版）》重写一遍
/**
* 排序数组
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
const N = nums.length;
let temp = new Array();
mergeSort(nums, 0, N - 1, temp);
return nums;
};
/**
* 归并排序 采用自顶向下的递归方法
* @param {number[]} nums
* @param {number} left
* @param {number} right
* @param {number[]} temp
* @returns
*/
var mergeSort = function (nums, left, right, temp) {
// 如果指针重叠了就返回
if (left >= right) {
return;
}
// let mid = Math.floor(left + (right - left) / 2);
let mid = (left + right) >> 1;
// 递归调用mergeSort
mergeSort(nums, left, mid, temp);
mergeSort(nums, mid + 1, right, temp);
// 归并两个有序数组
merge(nums, left, mid, right, temp);
};
/**
* 归并两个有序数组
* @param {number[]} nums
* @param {number} left
* @param {number} mid
* @param {number} right
* @param {number[]} temp
*/
var merge = function (nums, left, mid, right, temp) {
// 将nums复制到temp中去
for (let k = left; k <= right; k++) {
temp[k] = nums[k];
}
// 给两个数组分别定义一个指针
let i = left;
let j = mid + 1;
// 将temp中的元素按规则写回nums
for (let k = left; k <= right; k++) {
if (i > mid) {
// 左半边取尽，取右半边元素
nums[k] = temp[j];
j++;
} else if (j > right) {
// 右半边取尽，取左半边元素，左指针右移
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
// 谁小就取谁 ，左边小
nums[k] = temp[i];
i++;
} else {
// 右边小
nums[k] = temp[j];
j++;
}
}
};
# 复杂度分析
时间复杂度：$O(N \log N)$，这里 $N$ 是数组的长度； 空间复杂度：$O(N)$，辅助数组与输入数组规模相当。
# 优化
设置短数组长度阈值，使归并到短数组的时候用插入排序法
上面介绍的是一种自顶向下的递归方法，另外还有自底向上的递归方法，在这里就不做过多介绍，具体可以参考算法第四版的内容
# 6. 快速排序（重点）
# 流程
- 从数组中选择一个值作为主元（pivot），也就是数组中间的那个值。
- 创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分（partition）操作。
- 算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。
# 图示
# 代码
双指针法
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
const N = nums.length;
quickSort(nums, 0, N - 1);
return nums;
};
function quickSort(nums, left, right) {
if (right <= left) {
return;
}
let pIndex = partition(nums, left, right);
quickSort(nums, left, pIndex - 1);
quickSort(nums, pIndex + 1, right);
}
function partition(nums, left, right) {
let pivot = nums[left];
// 为两个数组分别定义一个指针
let i = left + 1;
let j = right;
while (true) {
while (i <= right && nums[i] <= pivot) {
i++;
}
while (j > left && nums[j] > pivot) {
j--;
}
if (i >= j) {
break;
}
swap(nums, i, j);
i++;
j--;
}
swap(nums, left, j);
return j;
}
# 复杂度分析
时间复杂度：$O(N \log N)$，这里 $N$ 是数组的长度； 空间复杂度：$O(\log N)$，这里占用的空间主要来自递归函数的栈空间。
# 7. 堆排序（重点）
# 概念
先来看看什么是堆
当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。 根结点是堆有序的二叉树中的最大结点 一棵大小为N的完全二叉树的高度为[lgN]
大顶堆：逻辑上是完全二叉树，对于树中任意节点，其关键字的值都不小于其孩子节点的关键字的值。
在堆上的一些操作
父节点位置为i，其左孩子节点位置为2i+1，右孩子节点位置为2i+2 最后一个非叶节点编号为 [n/2] - 1 （向下取整） 在一个堆中，位置k的结点的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1 从a[k]向上一层就令k等于k/2，向下一层则令k等于2k或2k+1
书上看的一个比较有意思的描述
我们把堆想象成一个严密的黑社会组织，每个子结点都表示一个下属（父结点则表示它的直接上级），那么这些操作就可以得到很有趣的解释。swim()【上浮】表示一个很有能力的新人加入组织并被逐级提升（将能力不够的上级踩在脚下），直到他遇到了一个更强的领导。sink()【下沉】则类似于整个社团的领导退休并被外来者取代之后，如果他的下属比他更厉害，他们的角色就会交换，这种交换会持续下去直到他的能力比其下属都强为止。
function swim(k){
while(k > 1 && nums[Math.floor(k/2)] < nums[k]){
swap(nums, Math.floor(k/2), k);
k = Math.floor(k/2);
}
}
function sink(k){
while(2*k <= N) {
let j = 2 * k;
if(j < N && nums[j] < nums[j+1]){
j++;
}
if(nums[k] >= nums[j]){
break;
}
swap(nums, k, j);
k = j;
}
}
# 1. 建堆
- 找出完全二叉树中最后一个非叶节点 [n/2] - 1
- 比较这个节点和其孩子节点的大小，如果小于孩子的最大值，就交换他们的值，交换后继续比较其与当前孩子的值的情况，进行同样的处理
- 指针不断上移（减一）循环步骤2
# 2. 插入节点
- 将要插入的节点放入所有节点的最后面
- 找到这个节点到根节点的一条路径，如果比父节点大，就交换，直到不大于父节点的大小
# 3. 删除节点
- 将要删除的节点拿出来
- 用堆中最后一个节点替换到待删除的节点的位置
- 对交换后的节点进行和【建堆步骤2】类似的调整
# 流程
堆排序可以分为两个阶段。在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。
- 将初始待排序关键字序列 $(R_1, R_2 .... R_n)$ 构建成大顶堆，此堆为初始的无序区；[堆的有序化（reheapifying）]
- 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区$(R_1, R_2 .... R_{n-1})$和新的有序区 $(R_n)$ ，且满足 $R[1, 2 ... n-1] <= R[n]$。
- 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 $(R_1, R_2 .... R_{n-1})$调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 $(R_1, R_2 .... R_{n-2})$和新的有序区$(R_{n-1}, R_n)$。不断重复此过程，直到有序区的元素个数为 $n - 1$，则整个排序过程完成。
# 图示
# 代码
/**
* 堆排序
* @param {*} nums
* @returns
*/
function sortArray(nums) {
const N = nums.length;
// 建堆 找到第一个非叶子节点，向上遍历
for (let i = Math.floor(N / 2 - 1); i >= 0; i--) {
// 对 i位置节点 调整堆
heapify(nums, i, N);
}
// 排序过程 每一次循环都找出当前最大值（根节点），数组长度减一
for (let i = N - 1; i > 0; i--) {
// 根节点与最后一个节点交换位置（将此时最大元素移动到数组末尾）
swap(nums, 0, i);
// 对 此时的根节点 调整堆 最后的元素不用参与调整
heapify(nums, 0, i);
}
return nums;
}
/**
* 对节点i进行 调整堆
* 满足：i节点以下的子堆是一个大顶堆
* 调整范围 [i, length)
* @param {*} nums
* @param {*} i
* @param {*} length
*/
function heapify(nums, i, length) {
// 将i节点的值保存，这个过程就是给temp找到一个合适的位置
let temp = nums[i]
// j指向i的左孩子节点
let j = 2 * i + 1;
// 循环遍历[i, length)
while (j < length) {
if (j + 1 < length && nums[j] < nums[j + 1]) {
// 父节点有右孩子 并且 左孩子小于右孩子 将j指向右孩子
j++;
}
// 此时 j 指向 i 的孩子节点中较大的那个节点
if (temp < nums[j]) {
// 如果 父节点小于 j节点
// 交换i，j的元素
swap(nums, i, j);
// 将i和j都下移一位
i = j;
j = 2 * i + 1;
} else {
// 父节点 大于 孩子节点中最大的元素，就退出循环
break;
}
}
}
# 复杂度分析
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 $O(N)$，排序过程的时间复杂度是 $O(N \log N)$，所以，堆排序整体的时间复杂度是 $O(N \log N)$。
# 8. 计数排序（了解）
# 流程
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
# 图示
# 代码
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
# 9. 基数排序（了解）
# 图示
# 代码
//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
# 10. 桶排序（了解）
# 代码
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
//利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值；
# 11. 总结
