下面都是将整数数组排序为升序
// 使用到的原地交换方法
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 ++ ) {
if ( nums [ j ] > nums [ j + 1 ] ) {
swap ( nums, j, j + 1 )
}
}
}
}
选择排序(Selection Sort)
从未排序区间查找最小的元素,将其放到已排序区间的末尾。
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 )
}
}
插入排序(Insertion Sort)
逐个将元素插入已排序部分,形成新的有序列表。
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
}
}
快速排序(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 < 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 )
}
三路快排
const partition = ( nums : number [ ] , left : number , right : number ) : [ number , number ] = > {
let [ l, r, i ] = [ left, right, left + 1 ]
const pivot = 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 )
}
归并排序(Merge Sort)
一种基于分治策略的排序算法:
划分阶段 :通过递归不断地将数组从中点处分开,将长数组的排序问题转换为短数组的排序问题。
合并阶段 :当子数组长度为 1 时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束。
const merge = ( nums : number [ ] , left : number , mid : number , right : number ) = > {
const tmp = new Array < number > ( right - left + 1 )
let [ 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 )
}
堆排序(Heap Sort)
利用堆数据结构,将列表转换为最大堆(最小堆),然后每次从堆顶取出最大(最小)元素,重新调整堆结构。
// 堆的长度为 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 ) // 以根节点为起点,从顶至底进行堆化
}
}
前述几种排序算法都属于“基于比较的排序算法”,它们通过比较元素间的大小来实现排序,此类排序算法的时间复杂度无法超越 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 )
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 ]
}
基数排序(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 ) = > {
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 )
}