原文来自 我的个人博客
1. 认识排序算法
排序算法就是研究如何对一个集合进行高效排序的算法，也是在面试时非常常见的面试题型之一。
下面是维基百科堆排序算法的解释：
在计算机科学与数学中，一个 排序算法（Sorting algorithm） 是一种能将 一串资料依照特定排序方式排列的算法。
在计算机科学所使用的排序算法通常依以下标准分类：
- 计算的时间复杂度：使用大 O 表示法，也可以实际测试消耗的时间；
- 内存使用量：比如外部排序，使用磁盘来存储排序的数据
- 稳定性：稳定排序算法会让原本相等键值的记录维持相对次序
- 排序的方法：插入、交换、选择、合并等等
常见的排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- ...
2. 冒泡算法（Bubble Sort）
冒泡排序可以说是最简单的排序算法了。
冒泡排序的基本思路：
- 通过两两比较相邻的元素并交换它们的位置，从而使整个序列按照顺序排列
- 一趟排序后，最大值总会移动到数组最后面，那么接下来就不用再考虑这个最大值了。
- 一直重复这样的操作，最终就可以得到排序完成的数组
冒泡排序图解：
代码实现：
function bubbleSort(arr: number[]): number[] {
const n = arr.length;
// 外层循环：0 ~ n-1
for (let i = 0; i < n; i++) {
// 内层循环找到最大值
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
// 交换两个数据
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
}
}
}
return arr;
}冒泡排序的复杂度分析：
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
总结：
- 冒泡排序适用于数据规模较小的情况，因为它的时间复杂度为 O(n2)，对于大数据量的排序会变得很慢。
- 同时，它的实现简单，代码实现也容易理解，适用于学习排序算法的初学者
- 但是，在实际的应用中，冒泡排序并不常用，因为它的效率很低
- 因此，在实际应用中，冒泡排序通常被更高效的排序算法代替，如快速排序、归并排序等
3. 选择排序（Selection Sort）
选择排序也是一种简单的排序算法。
它的基本思想：
- 首先在未排序的数列中找到最小（大）元素，然后将其存放到数列的起始位置；
- 接着，再从剩余未排序的元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕
选择排序的主要优点与数据移动有关
- 如果某个元素位于正确的最终位置，则它不会被移动。
- 选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对
n个元素的表进行排序总共进行 至多n-1次交换。 - 在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种
代码实现：
function selectionSort(arr: number[]): number[] {
const n = arr.length;
// 外层循环作用：经过多少轮的找最小值
for (let i = 0; i < n; i++) {
let minIndex = i;
// 内存循环作用：每次找到最小值
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
}
return arr;
}复杂度分析：
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
选择排序的总结：
- 虽然选择排序的实现非常简单，但是它的时间复杂度较高，对于大规模的数据排序效率较低
- 总的来说，选择排序适用于小规模数据的排序和排序算法的入门学习，对于需要高效排序的场合，可以选择其他更为高效的排序算法
4. 插入排序（Insertion Sort）
插入排序就像我们打扑克牌时，摸到一张新牌需要插入到手牌中的合适位置一样。
- 我们会将新牌和手牌中已有的牌进行比较，找一个合适的位置插入新牌。
- 如果新牌比某张牌小，那么我们就把这张牌向后移动一位，为新牌腾出位置。
- 一直比较直到找到一个合适的位置将新牌插入，这样就完成了一次插入操作。
而插入排序的实现方式就是与打牌类似的。
插入排序的图解：
、
代码实现：
function insertionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 1; i < n; i++) {
// 内层循环
const newNum = arr[i];
let j = i - 1;
while (arr[j] > newNum && j >= 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = newNum;
}
return arr;
}复杂度分析：
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
总结：
- 插入排序是一种简单直观的排序算法，它的基本思想就是将待排序数组分为已排序部分和未排序部分，然后将未排序部分的每个元素插入到已排序部分的合适位置。
- 插入排序的时间复杂度为 O(n2)，虽然这个复杂度比较高，但是插入排序的实现非常简单，而且在某些情况下性能表现也很好（待排数组的带部分元素已经排序好）
- 总之，插入排序虽然没有 快速排序 和 归并排序 等高级排序算法的复杂性和高效性，但是它的实现非常简单，而且在一些特定的场景下表现也很好
5. 归并排序（Merge Sort）
归并排序是一种典型的分而治之思想的算法，它的算法复杂度为 O(nlogn)，是一种比较高效的排序算法。
它的基本思想：
- 将待排序数组分成若干个子数组
- 然后将相邻的子数组归并成一个有序数组
- 最后再将这些有序数组归并（
merge）成一个整体有序的数组
归并排序的图解：
代码实现：
const mergeSort = function (arr: number[]) {
if (arr.length === 1) return arr;
// 1. 分解(divide)：对数组进行分解（分解成链各个小数组）
// 1.1 递归地切割数组得到左边的数组left 和 右边的数组right
const mid = arr.length >> 1;
const left: number[] = mergeSort(arr.slice(0, mid));
const right: number[] = mergeSort(arr.slice(mid));
// 2. 合并（merge）：将两个子数组进行合并（双指针）
// 2.1 定义双指针
const result: number[] = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result[leftIndex + rightIndex] = left[leftIndex++];
} else {
result[leftIndex + rightIndex] = right[rightIndex++];
}
}
// 2.2 判断是否一个数组中海油剩余元素
// 循环完左边还有剩余
while (leftIndex < left.length) {
result[leftIndex + rightIndex] = left[leftIndex++];
}
// 循环完右边还有剩余
while (rightIndex < right.length) {
result[leftIndex + rightIndex] = right[rightIndex++];
}
return result;
};复杂度分析：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
总结：
- 归并排序是一种非常高效的排序算法，它的核心思想是分治，即将待排序数组分成若干个子数组，分别对这些子数组进行排序，最后将排好序的子数组合并成一个有序数组。
- 归并排序的时间复杂度为O(nlogn)
- 虽然归并排序看起来比较复杂，但是只要理解了基本思路，实现起来并不困难，而且它是一种非常高效的排序算法。
6. 快速排序（Quick Sort）
快速排序是一种经典基于分治思想的排序算法
它的基本思想：
- 将一个大数组分成两个小数组，然后递归地对两个小数组进行排序。
- 具体实现方式是通过选择一个基准元素（pivot），将数组分成左右两部分，左部分的元素都小于或等于基准元素，右部分的元素都大于基准元素。
- 然后，对左右两部分分别进行递归调用快速排序，最终将整个数组排序
快速排序是一种原地排序算法，不需要额外的数组空间，同时它的时间复杂度为O(nlogn)。
快速排序图解：
代码实现：
const quickSort = function (arr: number[]): number[] {
partition(0, arr.length - 1);
function partition(left: number, right: number) {
if (left >= right) return;
// 1. 找到基准元素（pivot轴心）
const pivot = arr[right];
// 2. 双指针进行交换操作（左边都是比 pivot 小的数字，右边都是比 pivot 大的数字）
let i: number = left;
let j: number = right - 1;
while (i <= j) {
// 找到一个比 pivot 大的元素
while (arr[i] < pivot) {
i++;
}
// 找到一个比 pivot 小的元素
while (arr[j] > pivot) {
j--;
}
// 说明我们已经找到了 比pivot大的元素arr[i] 和 比pivot小的元素arr[j]
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
console.log({ arr });
}
// 将 pivot 放在正确的位置
[arr[i], arr[right]] = [arr[right], arr[i]];
// 左右继续划分区域(partition)
partition(left, j);
partition(i + 1, right);
}
return arr;
};总结：
- 快速排序的性能优于许多其他排序算法，因为它具有良好的局部性和使用原地排序的优点。
- 快速排序是一种高效的排序算法，在实践中被广泛使用
7. 堆排序（Heap Sort）
堆排序是一种基于比较的排序算法，它的核心思想是使用二叉堆来维护一个有序序列
- 首先我们会构建一个最大堆
- 然后，在我们将堆的根节点（也就是最大值）与堆的最后一个元素交换，这样最大值就被放在了正确的位置上。
- 接着，我们将堆的大小减小一，并将剩余的元素重新构建成一个最大堆
- 我们不断重复这个过程，直到堆的大小为
1 - 这样，我们就得到了一个有序序列
堆排序的图解：
代码实现：
function heapSort(arr: number[]): number[] {
// 1. 获取数组的长度
const n = arr.length;
// 2. 对 arr 进行原地建堆
// 2.1 从第一个非叶子节点开始进行下滤操作
const start = Math.floor(n / 2 - 1);
for (let i = start; i >= 0; i--) {
// 2.2 进行下滤操作
heapifyDown(arr, n, i);
}
// 3. 对最大堆进行排序
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapifyDown(arr, i, 0);
}
return arr;
}
function heapifyDown(arr: number[], n: number, index: number) {
while (2 * index + 1 < n) {
// 1. 获取左右子节点的索引
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
// 2. 找出左右子节点较大的值
let largerIndex = leftChildIndex;
if (rightChildIndex < n && arr[rightChildIndex] > arr[leftChildIndex]) {
largerIndex = rightChildIndex;
}
// 3. 判断 index 位置的值比更大的子节点，直接 break
if (arr[index] >= arr[largerIndex]) {
break;
}
// 4. 和更大位置的进行交换
[arr[index], arr[largerIndex]] = [arr[largerIndex], arr[index]];
index = largerIndex;
}
}时间复杂度：O(nlogn)
- 堆的建立过程：堆的建立过程包括
n/2次堆的向下调整操作，因此它的时间复杂度为O(n)。 排序过程
- 排序过程需要执行
n次堆的删除的最大值操作，每次操作都需要将堆的最后一个元素与堆顶元素交换，然后向下调整堆。 - 每次向下调整操作的时间复杂度为
O(logn)，因此整个排序过程的时间复杂度为O(nlogn)
- 排序过程需要执行
空间复杂度：O(1)
堆排序的总结：
- 堆排序是一种高效的排序算法，它利用堆这种数据结构来实现排序
- 堆排序具有时间复杂度
O(logn)的优秀性能，并且由于它只使用了常数个辅助变量来存储堆的信息，因此空间复杂度为O(1)。 - 但是，由于堆排序的过程是不稳定的，即相同元素的相对位置可能会发生变化，因此在某些情况下可能会导致排序结果不符合要求
