排序 | SkyBlog排序
经典排序算法
这篇文章发布于 2024年01月02日，星期二，06:29，归类于 算法。阅读 ? 次，0 条评论
下面都是将整数数组排序为升序
// 使用到的原地交换方法
const swap = (nums: number[], i: number, j: number) => {
;[nums[i], nums[j]] = [nums[j], nums[i]]
}
冒泡排序（Bubble Sort）
通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。
const bubbleSort = (nums: number[]) => {
for (let i = nums.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++)
选择排序（Selection Sort）
从未排序区间查找最小的元素，将其放到已排序区间的末尾。
const selectionSort = (nums: number[]) => {
for (let i = 0; i < nums.length - 1; i++) {
let k = i
for (let j = i +
插入排序（Insertion Sort）
逐个将元素插入已排序部分，形成新的有序列表。
const insertionSort = (nums: number[]) => {
for (let i = 1; i < nums.length; i++) {
const base = nums[i]
let j = i - 1
快速排序（Quick Sort）
选择一个基准元素，将列表分为两个子列表，小于基准的放在左边，大于基准的放在右边，然后对两个子列表递归地应用相同的方法。
// 交换元素使返回索引 i 满足 nums[a] <= nums[i] <= nums[b] (a∈[left,i]; b∈[i,right]; nums[i]==nums[left])
const partition = (nums: number[], left: number, right: number): number => {
// 以 nums[left] 为基准数；优化可以先选择几个数把中位数交换到 left 位置上，使交换后左右数量尽可能平均
let [i, j] = [left, right]
while (i <
三路快排
const partition = (nums: number[], left: number, right: number): [number, number] => {
let [l, r, i] = [left, right, left + 1]
const pivot
归并排序（Merge Sort）
一种基于分治策略的排序算法：
- 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
- 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。
const merge = (nums: number[], left: number, mid: number, right: number) => {
const tmp = new Array<number>(right - left + 1)
let [
堆排序（Heap Sort）
利用堆数据结构，将列表转换为最大堆（最小堆），然后每次从堆顶取出最大（最小）元素，重新调整堆结构。
// 堆的长度为 len，从节点 i 开始，从顶至底堆化
const ajustHeap = (nums: number[], i: number, len: number) => {
while (true) {
const [l, r] = [2 *
前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序，此类排序算法的时间复杂度无法超越 O(nlogn)。下面几种“非比较排序算法”，它们的时间复杂度可以在理想情况下达到线性阶。
桶排序（Bucket Sort）
它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据分配到各个桶中；然后在每个桶内部分别执行排序（语言自带的排序方法）；最终按照桶的顺序将所有数据合并。
桶排序适用于处理体量很大的数据。桶排序的时间复杂度理论上可以达到 O(n)，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。
计数排序（Counting Sort）
统计每个元素的出现次数，然后按照统计信息重建排序后的列表。适用于数据量大但数据范围较小的整数数组。
const countingSort = (nums: number[]) => {
// 找到最大值
const max = Math.max(...nums)
// 统计各数字的出现次数
const counter = new Array<number>(max + 1).fill(0)
基数排序（Radix Sort）
核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。
// 获取元素 num 的第 k 位，其中 exp = 10^(k-1)，传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
const digit = (num: number, exp: number) => Math.floor(num / exp) % 10
// 计数排序（根据 nums 第 k 位排序）
const countingSortDigit = (nums: number[], exp: number)
{
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1)
}
}
}
}
1
; j
<
nums.
length
; j
++
)
{
if (nums[j] < nums[k]) {
k = j
}
}
swap(nums, i, k)
}
}
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]
j--
}
nums[j + 1] = base
}
}
j
)
{
while (i < j && nums[j] >= nums[left]) j-- // 这两个 while 在这种含等号循环条件下不能交换顺序；
while (i < j && nums[i] <= nums[left]) i++ // 因为外层 while 循环结束时（i==j)，还会交换 nums[left] 与 nums[i]，需满足 nums[i] <= nums[left] 才行
swap(nums, i, j)
}
swap(nums, left, i)
return i
}
const quickSort = (nums: number[], left: number, right: number) => {
if (left >= right) return
const pivot = partition(nums, left, right)
quickSort(nums, left, pivot - 1)
quickSort(nums, pivot + 1, right)
}
=
nums
[
left
]
while (i <= r) {
if (nums[i] < pivot) swap(nums, i++, l++)
else if (nums[i] > pivot) swap(nums, i, r--)
else i++
}
return [l, r]
}
const quickSort3Way = (nums: number[], left: number, right: number) => {
if (left >= right) return
const [l, r] = partition(nums, left, right)
quickSort3Way(nums, left, l - 1)
quickSort3Way(nums, r + 1, right)
}
i, j, k
]
=
[
left, mid
+
1
,
0
]
while (i <= mid && j <= right) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++]
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) tmp[k++] = nums[i++]
while (j <= right) tmp[k++] = nums[j++]
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.length; k++) nums[left + k] = tmp[k]
}
const mergeSort = (nums: number[], left: number, right: number) => {
if (left >= right) return
const mid = (left + right) >> 1
mergeSort(nums, left, mid)
mergeSort(nums, mid + 1, right)
merge(nums, left, mid, right)
}
i
+
1
,
2
*
i
+
2
]
// 左右节点索引
let max = i // 记录根与左右子节点中最大值的索引
if (l < len && nums[l] > nums[max]) max = l
if (r < len && nums[r] > nums[max]) max = r
// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
if (max == i) break
swap(nums, i, max)
i = max
}
}
const heapSort = (nums: number[]) => {
for (let i = (nums.length >> 1) - 1; i >= 0; i--) ajustHeap(nums, i, nums.length) // 建堆操作（从树的倒数第二层最后一个元素开始）
for (let i = nums.length - 1; i > 0; i--) {
swap(nums, 0, i)
ajustHeap(nums, 0, i) // 以根节点为起点，从顶至底进行堆化
}
}
for (const num of nums) counter[num]++
// 求 counter 的前缀和，将“出现次数”转换为“尾索引”；即 counter[num]-1 是 num 在 ans 中最后一次出现的索引
for (let i = 0; i < max; i++) counter[i + 1] += counter[i]
// 倒序遍历 nums ，将各元素填入结果数组 ans。倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。
const ans = new Array<number>(nums.length)
for (let i = nums.length - 1; i >= 0; i--) {
const num = nums[i]
ans[--counter[num]] = num
}
// 使用结果数组 ans 覆盖原数组 nums
for (let i = 0; i < nums.length; i++) nums[i] = ans[i]
}
=
>
{
const counter = new Array(10).fill(0)
for (let i = 0; i < nums.length; i++) counter[digit(nums[i], exp)]++
for (let i = 1; i < counter.length; i++) counter[i] += counter[i - 1]
const ans = new Array<number>(nums.length)
for (let i = nums.length - 1; i >= 0; i--) {
const d = digit(nums[i], exp)
ans[--counter[d]] = nums[i]
}
for (let i = 0; i < nums.length; i++) nums[i] = ans[i]
}
const radixSort = (nums: number[]) => {
const max = Math.max(...nums)
for (let exp = 1; exp <= max; exp *= 10) countingSortDigit(nums, exp)
}