const selectionSort =(nums: number[])=>{ for(let i = 0; i < nums.length - 1; i++){ let k = i for(let j = i + 1; j < nums.length; j++){ if(nums[j]< nums[k]){ k = j}} swap(nums, i, k)}}
const insertionSort =(nums: number[])=>{ for(let i = 1; i < nums.length; i++){ const base = nums[i] let j = i - 1 while(j >= 0 && nums[j]> base){ nums[j + 1]= nums[j] j--} nums[j + 1]= base}}
// 堆的长度为 len，从节点 i 开始，从顶至底堆化const ajustHeap =(nums: number[], i: number, len: number)=>{ while(true){ const[l, r]=[2 * 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)// 以根节点为起点，从顶至底进行堆化}}
const countingSort =(nums: number[])=>{ // 找到最大值 const max = Math.max(...nums) // 统计各数字的出现次数 const counter = new Array<number>(max + 1).fill(0) 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]}
// 获取元素 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)=>{ 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)}