推荐学习网址：
fucking-algorithm (opens in a new tab)
学习算法的可视化网站 (opens in a new tab)
快速排序
快速排序的步骤
快速排序是一种分而治之的排序算法。它的基本思路是：
-
选择基准值（Pivot）：从数组中选择一个元素作为基准值，通常选择第一个元素或者最后一个元素。
-
分区操作（Partitioning）：重新排列数组，比基准值小的所有元素摆放在基准前面，比基准值大的所有元素摆放在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
-
递归排序：递归地将小于基准值的子序列和大于基准值的子序列排序。
快速排序算法的性能通常比其他 O(n log n)算法更好，因为它的内部循环可以在大部分的架构上很高效地被实现出来。在平均情况下非常高效，空间效率高，但最坏情况性能较差，最坏情况下时间复杂度为 O(n^2)。以 Leetcode 912 (opens in a new tab) 为例，用这种方式会在最后一例时会超时。
function sortArray(nums: number[]): number[] {
function partition(l: number, r: number): number {
const tmp = nums[r];
let i = l;
for (let j = l; j < r; j++) {
if (nums[j] <= tmp) {
[nums[i], nums[j]] = [nums[j], nums[i]];
++i;
}
}
[nums[i], nums[r]] = [nums[r], nums[i]];
return i;
}
function quicksort(l: number, r: number): void {
if (r <= l) return;
const q = partition(l, r);
quicksort(l, q - 1);
quicksort(q, r);
}
quicksort(0, nums.length - 1);
return nums;
}三路快排(快速排序的优化)
快速排序的优化主要是针对于数组中有大量重复元素的情况，这种情况下，快速排序会退化成 O(n^2) 的算法。三路快排的思路是将数组分为三部分，分别是小于基准值的部分、等于基准值的部分和大于基准值的部分。这样，优化了处理含有大量重复元素的数组，能提供接近线性的性能。
三路快排对比经典的快速排序的区别：
- 划分方式：
- 经典快速排序：基于基准值进行划分，小于基准值的放在左边，大于基准值的放在右边。
- 三路快速排序：基于基准值进行划分，小于基准值的放在左边，大于基准值的放在右边，等于基准值的放在中间。
- 递归方式：
- 经典快速排序：对左右两边的子序列分别递归排序。
- 三路快速排序：对左右两边的子序列分别递归排序，对等于基准值的子序列不再进行排序。
function sortArray(nums: number[]): number[] {
function quicksort(l: number, r: number): void {
if (l >= r) return;
const val = nums[l];
let left = l;
let right = r;
let i = left + 1;
while (i <= right) {
if (nums[i] < val) {
// 小于基准的部分
[nums[i], nums[left]] = [nums[left], nums[i]];
++left;
++i;
} else if (nums[i] > val) {
// 大于基准的部分
[nums[right], nums[i]] = [nums[i], nums[right]];
--right;
} else {
// 等于基准的部分
++i;
}
}
// 对小于基准值的元素排序
quicksort(l, left - 1);
// 对大于基准值的元素排序
quicksort(right + 1, r);
}
quicksort(0, nums.length - 1);
return nums;
}快速排序的不稳定性
快速排序之所以被认为是不稳定的，是因为在分区操作过程中，相等的元素可能会因为分区的交换操作而改变它们的相对位置。举个例子：
假设有一个数组 [4a, 2, 3, 4b]（这里 4a 和 4b 是相等的元素，我们用 a 和 b 来区分它们原始的位置）。如果我们选择第一个元素作为基准进行快速排序，分区操作可能会产生这样的结果：[2, 3, 4a, 4b]。现在假设我们选择最后一个元素作为基准，分区操作可能会产生这样的结果：[2, 3, 4b, 4a]。可以看出，4a 和 4b 的相对顺序改变了，即快速排序操作可能会打乱相等元素的原有顺序，因此它是不稳定的。
归并排序
归并排序的步骤
归并排序也是一种分而治之的排序算法。它的基本思路是：
- 分解：将数组分解成两个尽可能相等大小的子序列，分别对两个子序列进行排序。
- 递归：递归地对两个子序列进行归并排序。
- 合并：将两个已经排好序的子序列合并成一个有序的序列。
归并排序算法的性能是稳定的，时间复杂度为 O(n log n)，空间复杂度为 O(n)。提供了最好的最坏情况性能保证，对非随机访问数据结构和外部排序也很有效，但需要额外的存储空间，也就是空间换时间。归并排序的典型应用是给链表排序，因为链表只能顺序访问，归并排序最关键的操作是合并操作，而合并操作恰好是顺序操作，所以归并排序非常适合给链表排序。
function sortArray(nums: number[]): number[] {
function mergeSort(nums: number[], l: number, r: number): void {
if (r - l <= 1) return;
const mid = Math.floor((l + r) / 2);
mergeSort(nums, l, mid);
mergeSort(nums, mid, r);
merge(nums, l, mid, r);
}
function merge(nums: number[], l: number, m: number, r: number): void {
const left = nums.slice(l, m);
const right = nums.slice(m, r);
// 设置哨兵，当某一个数组读到尽头后，另一个数组依然可以继续读取
left.push(Infinity);
right.push(Infinity);
let i = 0,
j = 0,
k = l;
while (k !== r) {
if (left[i] <= right[j]) {
nums[k] = left[i];
++i;
} else {
nums[k] = right[j];
++j;
}
++k;
}
}
mergeSort(nums, 0, nums.length);
return nums;
}归并排序的稳定性
归并排序能够保证排序的稳定性，因为在合并两个已经排序的子序列时，如果遇到相等的元素，它总是先取左边子序列的元素，这样就保留了相等元素的初始相对位置。再次使用上面的数组 [4a, 2, 3, 4b] 作为例子：
- 归并排序先将数组分成 [4a] 和 [2, 3, 4b]，然后递归地对它们进行排序。
- 接下来，它将 [2, 3, 4b] 分成 [2] 和 [3, 4b]，然后再递归排序。
- 最后，归并排序将这些子序列合并回去。当合并 [4a] 和 [2, 3, 4b] 时，如果遇到 4a 和 4b 相等的情况，它会首先取出 4a（因为 4a 来自左侧子序列），保持 4a 和 4b 的相对顺序。
由于归并排序的这种合并机制，它能够确保相等元素的原有顺序不变，因此归并排序是稳定的。