推荐学习网址:
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 的相对顺序。
由于归并排序的这种合并机制,它能够确保相等元素的原有顺序不变,因此归并排序是稳定的。