文章目录912.排序数组题目1. 冒泡排序时间复杂度O(n²)空间复杂度O(1)稳定性稳定2. 简单选择排序时间复杂度O(n²)空间复杂度O(1)稳定性不稳定3. 插入排序时间复杂度O(n²)空间复杂度O(1)稳定性稳定4. 快速排序时间复杂度 O(n log n)空间复杂度 O(log n)稳定性不稳定5. 归并排序时间复杂度 O(n log n)空间复杂度 O(n)稳定性稳定6. 堆排序时间复杂度 O(n log n)空间复杂度 O(1)稳定性不稳定小顶堆1. 海量数据找 最大的 K 个数2. 最小优先队列大顶堆海量数据找 最小的 K 个数912.排序数组题目给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为O(nlog(n))并且空间复杂度尽可能小。示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。提示1 nums.length 5 * 10^4-5 * 10^4 nums[i] 5 * 10^4优先使用快速排序随机 pivot平均时间复杂度 O(n log n)空间复杂度 O(log n)原地排序实际性能最好需要稳定排序 → 归并排序需要时间复杂度严格稳定无最坏情况→ 堆排序插冒归 —— 稳定快堆选 —— 不稳定1. 冒泡排序从头开始两两相邻比较前面比后面大就交换大的往后挪每一轮走完最大的数会像气泡一样“冒”到最后面重复这个过程直到整个数组有序荐2packagemainimportfmt// 冒泡排序对数组进行升序排序funcbubbleSort(nums[]int)[]int{n:len(nums)// 外层循环控制排序的总轮数n 个数字只需要排 n-1 轮就够了fori:0;in-1;i{// 内层循环每一轮两两比较把大的元素往后移每一轮结束最后面 i 个数字已经排好序了不用再比forj:0;jn-i-1;j{// 升序前一个元素 后一个元素 则交换// 降序前一个元素 后一个元素 则交换ifnums[j]nums[j1]{// 交换两个元素的位置nums[j],nums[j1]nums[j1],nums[j]}}}// 返回排序完成的数组returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(bubbleSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最好、最坏、平均都是O(n²)空间复杂度O(1)没有开辟新数组/切片只使用了临时变量交换原地排序稳定性稳定稳定性 相等的元素在排序后前后顺序保持不变冒泡排序可以通过增加一个标志位判断某一轮是否发生交换如果没有交换说明数组已经有序可以提前结束。这个优化不会改变最坏时间复杂度仍然是 O(n²)但可以将最好情况优化到O(n)空间复杂度仍然是 O(1)。packagemainimportfmt// bubbleSort 冒泡排序 优化版本// 增加了交换标记数组提前有序时可以直接退出提升效率funcbubbleSort(nums[]int)[]int{n:len(nums)// 外层循环控制排序轮数最多执行 n-1 轮fori:0;in-1;i{swapped:false// 标记本轮是否发生过交换// 内层循环两两比较将大元素向后交换// 每轮结束后最后 i 个元素已确定位置无需再比较forj:0;jn-i-1;j{// 升序排列前一个 后一个 则交换ifnums[j]nums[j1]{nums[j],nums[j1]nums[j1],nums[j]swappedtrue// 发生了交换标记为 true}}// 如果本轮一次交换都没发生 → 数组已经完全有序// 直接跳出循环不用继续排序if!swapped{break}}returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(bubbleSort(arr))// 输出[1 2 3 4 5]}2. 简单选择排序一开始整个数组都是未排序的从第一个位置开始认为当前位置是要放“最小值”的位置在当前位置后面的所有元素中找到最小值把这个最小值交换到当前位置然后移动到下一个位置重复这个过程直到所有位置都处理完数组就有序了packagemainimportfmt// 选择排序对数组进行升序排序funcselectionSort(nums[]int)[]int{n:len(nums)// 外层循环控制每一轮要放“最小值”的位置// 外层循环i 走到 n-1 就够了最后一个元素自动有序fori:0;in-1;i{// 先假设当前位置是最小值下标minIndex:i// 内层循环在未排序区找到真正的最小值forj:i1;jn;j{// 升序找到更小的值就更新最小值下标// 降序找到更大的值就更新最大值下标ifnums[j]nums[minIndex]{minIndexj}}// 找到最小值后与当前位置交换ifminIndex!i{// 小优化避免自己和自己交换nums[i],nums[minIndex]nums[minIndex],nums[i]}}// 返回排序完成的数组returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(selectionSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最好、最坏、平均都是O(n²)空间复杂度O(1)没有开辟新数组/切片只使用了临时变量交换原地排序稳定性不稳定3. 插入排序把数组分成左边有序区、右边无序区最开始第一个元素自己就是有序区剩下的都是无序区每次从无序区拿第一个元素当成要插入的数把这个数从后往前和有序区的元素比较如果有序区的元素更大升序就把它往后挪一位直到找到比它小的元素或走到有序区开头通过元素后移腾出位置把要插入的数放到空出来的位置重复直到无序区为空数组就有序了packagemainimportfmt// 插入排序对数组进行升序排序funcinsertionSort(nums[]int)[]int{n:len(nums)// 外层循环从第二个元素开始第一个默认有序fori:1;in;i{// 保存当前要插入的元素cur:nums[i]// 从 i 的前一个位置开始往前比较j:i-1// 内层循环往前遍历有序区比 cur 大的元素往后挪// 升序nums[j] cur// 降序nums[j] curforj0nums[j]cur{nums[j1]nums[j]// 元素后移j--// 继续往前比较}// 循环结束j1 就是插入的正确位置nums[j1]cur}returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(insertionSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最坏/平均O(n²)最好数组已经有序O(n)空间复杂度O(1)原地排序只使用了临时变量没有开辟新数组稳定性稳定4. 快速排序选定一个基准值 pivot固定选区间第一个元素使用左右双指针在当前区间内遍历右指针向左找找到小于基准的元素停下左指针向右找找到大于基准的元素停下交换左右指针指向的元素让小的靠左、大的靠右双指针相遇时将基准值交换到指针位置基准永久就位递归处理基准左侧区间和右侧区间递归终止区间长度 ≤1 时天然有序随机基准随机选一个元素当 pivot避免有序数组退化packagemainimport(fmt// math/rand // 随机基准需要打开生成随机数// time // 随机基准需要打开设置随机种子)// 格式func quickSort(nums []int) []int// 原地排序 双指针交换法 固定基准默认funcquickSort(nums[]int)[]int{// 关键 Go 语法讲解 // 第一步先声明函数变量 sort// 作用告诉编译器“有一个叫 sort 的函数”为递归做准备// 因为 Go 中函数不能直接在定义时调用自己必须先声明再赋值// varsortfunc(arr[]int,leftint,rightint)// 关键 Go 语法讲解 // 第二步给 sort 变量赋值真正实现函数逻辑// 此时函数已经声明过了内部可以安全递归调用 sort// sortfunc(arr[]int,leftint,rightint){// 递归终止条件区间长度 1天然有序直接返回ifleftright{return}// 基准选择 // 版本1固定基准pivot:arr[left]// 版本2随机基准加分项避免有序数组退化// 打开注释即可使用记得同时打开上方 import 包/* rand.Seed(time.Now().UnixNano()) // 初始化随机种子 randomIdx : left rand.Intn(right-left1) // 在 [left, right] 随机选下标 arr[left], arr[randomIdx] arr[randomIdx], arr[left] // 交换到最左边 pivot arr[left] // 更新基准 */// // 初始化左右双指针i,j:left,right// 双指针分区核心逻辑forij{// 右指针向左找第一个 小于 pivot 的元素forijarr[j]pivot{j--}// 左指针向右找第一个 大于 pivot 的元素forijarr[i]pivot{i}// 指针未相遇 → 交换ifij{arr[i],arr[j]arr[j],arr[i]}}// 指针相遇将基准放到最终正确位置// 循环结束i 和 j 已经相遇i j// 相遇位置 i 就是基准 pivot 的最终正确位置// 因为基准取自 arr[left]所以将基准与相遇位置交换arr[left],arr[i]arr[i],arr[left]// 递归排序左区间sort(arr,left,i-1)// 递归排序右区间sort(arr,i1,right)}// 启动递归对整个数组排序sort(nums,0,len(nums)-1)// 返回排序后的数组returnnums}funcmain(){// 测试用例 1nums1:[]int{5,2,3,1}fmt.Println(quickSort(nums1))// 输出: [1 2 3 5]// 测试用例 2nums2:[]int{5,1,1,2,0,0}fmt.Println(quickSort(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)固定基准平均O(n log n)每次划分均匀效率最高最坏O(n²)数组完全有序/逆序划分极度不平衡最好O(n log n)每次划分完美均匀随机基准平均O(n log n)最坏O(n log n)最坏时间复杂度仍然是 O(n²)但通过随机选择 pivot使这种情况出现的概率极低因此期望时间复杂度为 O(n log n) 【降低“出现最坏情况的概率”】最好O(n log n)空间复杂度 O(log n)平均O(log n)递归调用栈深度平衡划分最坏O(n)划分极度不平衡递归退化为链表原地排序无额外数组空间开销稳定性不稳定5. 归并排序采用分治法把数组从中间分成左右两半递归地把左右两半分别排好序把两个已经有序的子数组合并成一个大的有序数组重复直到整个数组有序归并排序永远是 O(n log n)不会退化缺点是需要额外辅助空间packagemainimportfmt// mergeSort 归并排序funcmergeSort(nums[]int)[]int{// 递归终止条件// 数组长度 1天然有序直接返回iflen(nums)1{returnnums}// 1. 拆分从中间分成左右两半mid:len(nums)/2// 找到中间位置left:mergeSort(nums[:mid])// 递归处理左半边right:mergeSort(nums[mid:])// 递归处理右半边// 2. 合并将两个有序的数组合并成一个有序数组returnmerge(left,right)}// merge 合并两个【已经有序】的数组 → 返回新的有序数组funcmerge(left,right[]int)[]int{// 创建一个空的结果切片// 长度 0容量预先分配为 左右 总长度避免自动扩容更高效result:make([]int,0,len(left)len(right))// 双指针i 遍历 leftj 遍历 righti,j:0,0// 3. 双指针同时遍历谁小就先把谁放进结果forilen(left)jlen(right){ifleft[i]right[j]{resultappend(result,left[i])i// 左指针后移}else{resultappend(result,right[j])j// 右指针后移}}// 4. 处理 left 剩下的元素如果有// 此时 left 剩下的一定都比结果里的大forilen(left){resultappend(result,left[i])i}// 5. 处理 right 剩下的元素如果有// 此时 right 剩下的一定都比结果里的大forjlen(right){resultappend(result,right[j])j}// 返回最终合并好的有序数组returnresult}funcmain(){nums:[]int{5,2,3,1}fmt.Println(mergeSort(nums))// 输出: [1 2 3 5]nums2:[]int{5,1,1,2,0,0}fmt.Println(mergeSort(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)最好O(n log n)最坏O(n log n)平均O(n log n)不会像快排那样退化永远稳定高效空间复杂度 O(n)O(n)需要额外数组存储合并结果递归调用栈O(log n)总空间O(n)稳定性稳定6. 堆排序把数组变成一个大顶堆根节点最大把堆顶最大值和数组最后一位交换→ 最大值就位把剩下的元素重新调整成堆重复以上步骤直到整个数组有序时间复杂度永远O(n log n)原地排序不需要额外空间packagemainimportfmt// sortArray 堆排序对外接口funcsortArray(nums[]int)[]int{n:len(nums)// 1. 构建大顶堆从最后一个非叶子节点向上调整fori:n/2-1;i0;i--{heapify(nums,n,i)}// 2. 一个个交换堆顶到末尾并调整剩余元素fori:n-1;i0;i--{// 将堆顶最大值 与 当前数组末尾交换nums[0],nums[i]nums[i],nums[0]// 交换后剩余元素重新调整为大顶堆heapify(nums,i,0)}returnnums}// heapify 调整堆让以 i 为根的子树变成大顶堆// n堆的长度i当前要调整的根节点funcheapify(nums[]int,nint,iint){largest:i// 最大值初始化为根节点left:2*i1// 左孩子节点下标right:2*i2// 右孩子节点下标// 如果左孩子更大更新最大值下标ifleftnnums[left]nums[largest]{largestleft}// 如果右孩子更大更新最大值下标ifrightnnums[right]nums[largest]{largestright}// 如果最大值不是根节点说明需要交换iflargest!i{nums[i],nums[largest]nums[largest],nums[i]// 交换后递归调整受影响的子树heapify(nums,n,largest)}}funcmain(){// 测试用例 1nums1:[]int{5,2,3,1}fmt.Println(sortArray(nums1))// 输出: [1 2 3 5]// 测试用例 2nums2:[]int{5,1,1,2,0,0}fmt.Println(sortArray(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)建堆 O(n) 每次调整堆 O(log n)初始化建堆的时间复杂度为 O(n)建完堆以后需要进行 n−1 次调整一次调整的时间复杂度为 O(logn)那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。因此总时间复杂度为 O(nnlogn)O(nlogn)。空间复杂度 O(1)原地排序没有额外开辟数组只需要常数的空间存放若干变量稳定性不稳定小顶堆特点堆顶是整个堆里最小的值核心逻辑快速获取当前堆的最小值1. 海量数据找 最大的 K 个数用途数据太大无法全加载内存找最大 K 个为什么用小顶堆我们要保留大的淘汰小的小顶堆能O(1) 拿到堆里最小的那个只要新数 堆顶就替换堆顶我们要留大的扔小的那我就把当前最小的放堆顶新来一个数只要比最小的大就把最小的踢走最后剩下的自然就是最大的 K 个原理维护一个大小固定为 K的小顶堆遍历所有数据新数 堆顶 → 删堆顶插入新数最终堆里就是全局最大 K 个数2. 最小优先队列用途每次要取最小元素原理小顶堆保证堆顶最小每次出队都是最小值时间 O(logn)想拿最小值 → 直接拿堆顶拿走后堆会自动调整新堆顶又是新的最小值永远能最快拿到最小这就是 “最小优先队列”。大顶堆特点堆顶是整个堆里最大的值核心逻辑快速获取当前堆的最大值海量数据找 最小的 K 个数用途有限内存找最小 K 个原理维护大小为 K的大顶堆新数 堆顶 → 替换最终堆里就是全局最小 K 个数为什么用大顶堆快速拿到堆里最大的方便淘汰大的保留小的
【Day47】912. 排序数组【6 种排序】
发布时间：2026/7/25 9:16:19
文章目录912.排序数组题目1. 冒泡排序时间复杂度O(n²)空间复杂度O(1)稳定性稳定2. 简单选择排序时间复杂度O(n²)空间复杂度O(1)稳定性不稳定3. 插入排序时间复杂度O(n²)空间复杂度O(1)稳定性稳定4. 快速排序时间复杂度 O(n log n)空间复杂度 O(log n)稳定性不稳定5. 归并排序时间复杂度 O(n log n)空间复杂度 O(n)稳定性稳定6. 堆排序时间复杂度 O(n log n)空间复杂度 O(1)稳定性不稳定小顶堆1. 海量数据找 最大的 K 个数2. 最小优先队列大顶堆海量数据找 最小的 K 个数912.排序数组题目给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为O(nlog(n))并且空间复杂度尽可能小。示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。提示1 nums.length 5 * 10^4-5 * 10^4 nums[i] 5 * 10^4优先使用快速排序随机 pivot平均时间复杂度 O(n log n)空间复杂度 O(log n)原地排序实际性能最好需要稳定排序 → 归并排序需要时间复杂度严格稳定无最坏情况→ 堆排序插冒归 —— 稳定快堆选 —— 不稳定1. 冒泡排序从头开始两两相邻比较前面比后面大就交换大的往后挪每一轮走完最大的数会像气泡一样“冒”到最后面重复这个过程直到整个数组有序荐2packagemainimportfmt// 冒泡排序对数组进行升序排序funcbubbleSort(nums[]int)[]int{n:len(nums)// 外层循环控制排序的总轮数n 个数字只需要排 n-1 轮就够了fori:0;in-1;i{// 内层循环每一轮两两比较把大的元素往后移每一轮结束最后面 i 个数字已经排好序了不用再比forj:0;jn-i-1;j{// 升序前一个元素 后一个元素 则交换// 降序前一个元素 后一个元素 则交换ifnums[j]nums[j1]{// 交换两个元素的位置nums[j],nums[j1]nums[j1],nums[j]}}}// 返回排序完成的数组returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(bubbleSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最好、最坏、平均都是O(n²)空间复杂度O(1)没有开辟新数组/切片只使用了临时变量交换原地排序稳定性稳定稳定性 相等的元素在排序后前后顺序保持不变冒泡排序可以通过增加一个标志位判断某一轮是否发生交换如果没有交换说明数组已经有序可以提前结束。这个优化不会改变最坏时间复杂度仍然是 O(n²)但可以将最好情况优化到O(n)空间复杂度仍然是 O(1)。packagemainimportfmt// bubbleSort 冒泡排序 优化版本// 增加了交换标记数组提前有序时可以直接退出提升效率funcbubbleSort(nums[]int)[]int{n:len(nums)// 外层循环控制排序轮数最多执行 n-1 轮fori:0;in-1;i{swapped:false// 标记本轮是否发生过交换// 内层循环两两比较将大元素向后交换// 每轮结束后最后 i 个元素已确定位置无需再比较forj:0;jn-i-1;j{// 升序排列前一个 后一个 则交换ifnums[j]nums[j1]{nums[j],nums[j1]nums[j1],nums[j]swappedtrue// 发生了交换标记为 true}}// 如果本轮一次交换都没发生 → 数组已经完全有序// 直接跳出循环不用继续排序if!swapped{break}}returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(bubbleSort(arr))// 输出[1 2 3 4 5]}2. 简单选择排序一开始整个数组都是未排序的从第一个位置开始认为当前位置是要放“最小值”的位置在当前位置后面的所有元素中找到最小值把这个最小值交换到当前位置然后移动到下一个位置重复这个过程直到所有位置都处理完数组就有序了packagemainimportfmt// 选择排序对数组进行升序排序funcselectionSort(nums[]int)[]int{n:len(nums)// 外层循环控制每一轮要放“最小值”的位置// 外层循环i 走到 n-1 就够了最后一个元素自动有序fori:0;in-1;i{// 先假设当前位置是最小值下标minIndex:i// 内层循环在未排序区找到真正的最小值forj:i1;jn;j{// 升序找到更小的值就更新最小值下标// 降序找到更大的值就更新最大值下标ifnums[j]nums[minIndex]{minIndexj}}// 找到最小值后与当前位置交换ifminIndex!i{// 小优化避免自己和自己交换nums[i],nums[minIndex]nums[minIndex],nums[i]}}// 返回排序完成的数组returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(selectionSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最好、最坏、平均都是O(n²)空间复杂度O(1)没有开辟新数组/切片只使用了临时变量交换原地排序稳定性不稳定3. 插入排序把数组分成左边有序区、右边无序区最开始第一个元素自己就是有序区剩下的都是无序区每次从无序区拿第一个元素当成要插入的数把这个数从后往前和有序区的元素比较如果有序区的元素更大升序就把它往后挪一位直到找到比它小的元素或走到有序区开头通过元素后移腾出位置把要插入的数放到空出来的位置重复直到无序区为空数组就有序了packagemainimportfmt// 插入排序对数组进行升序排序funcinsertionSort(nums[]int)[]int{n:len(nums)// 外层循环从第二个元素开始第一个默认有序fori:1;in;i{// 保存当前要插入的元素cur:nums[i]// 从 i 的前一个位置开始往前比较j:i-1// 内层循环往前遍历有序区比 cur 大的元素往后挪// 升序nums[j] cur// 降序nums[j] curforj0nums[j]cur{nums[j1]nums[j]// 元素后移j--// 继续往前比较}// 循环结束j1 就是插入的正确位置nums[j1]cur}returnnums}funcmain(){arr:[]int{4,2,5,1,3}fmt.Println(insertionSort(arr))// 输出[1 2 3 4 5]}时间复杂度O(n²)两层循环最坏/平均O(n²)最好数组已经有序O(n)空间复杂度O(1)原地排序只使用了临时变量没有开辟新数组稳定性稳定4. 快速排序选定一个基准值 pivot固定选区间第一个元素使用左右双指针在当前区间内遍历右指针向左找找到小于基准的元素停下左指针向右找找到大于基准的元素停下交换左右指针指向的元素让小的靠左、大的靠右双指针相遇时将基准值交换到指针位置基准永久就位递归处理基准左侧区间和右侧区间递归终止区间长度 ≤1 时天然有序随机基准随机选一个元素当 pivot避免有序数组退化packagemainimport(fmt// math/rand // 随机基准需要打开生成随机数// time // 随机基准需要打开设置随机种子)// 格式func quickSort(nums []int) []int// 原地排序 双指针交换法 固定基准默认funcquickSort(nums[]int)[]int{// 关键 Go 语法讲解 // 第一步先声明函数变量 sort// 作用告诉编译器“有一个叫 sort 的函数”为递归做准备// 因为 Go 中函数不能直接在定义时调用自己必须先声明再赋值// varsortfunc(arr[]int,leftint,rightint)// 关键 Go 语法讲解 // 第二步给 sort 变量赋值真正实现函数逻辑// 此时函数已经声明过了内部可以安全递归调用 sort// sortfunc(arr[]int,leftint,rightint){// 递归终止条件区间长度 1天然有序直接返回ifleftright{return}// 基准选择 // 版本1固定基准pivot:arr[left]// 版本2随机基准加分项避免有序数组退化// 打开注释即可使用记得同时打开上方 import 包/* rand.Seed(time.Now().UnixNano()) // 初始化随机种子 randomIdx : left rand.Intn(right-left1) // 在 [left, right] 随机选下标 arr[left], arr[randomIdx] arr[randomIdx], arr[left] // 交换到最左边 pivot arr[left] // 更新基准 */// // 初始化左右双指针i,j:left,right// 双指针分区核心逻辑forij{// 右指针向左找第一个 小于 pivot 的元素forijarr[j]pivot{j--}// 左指针向右找第一个 大于 pivot 的元素forijarr[i]pivot{i}// 指针未相遇 → 交换ifij{arr[i],arr[j]arr[j],arr[i]}}// 指针相遇将基准放到最终正确位置// 循环结束i 和 j 已经相遇i j// 相遇位置 i 就是基准 pivot 的最终正确位置// 因为基准取自 arr[left]所以将基准与相遇位置交换arr[left],arr[i]arr[i],arr[left]// 递归排序左区间sort(arr,left,i-1)// 递归排序右区间sort(arr,i1,right)}// 启动递归对整个数组排序sort(nums,0,len(nums)-1)// 返回排序后的数组returnnums}funcmain(){// 测试用例 1nums1:[]int{5,2,3,1}fmt.Println(quickSort(nums1))// 输出: [1 2 3 5]// 测试用例 2nums2:[]int{5,1,1,2,0,0}fmt.Println(quickSort(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)固定基准平均O(n log n)每次划分均匀效率最高最坏O(n²)数组完全有序/逆序划分极度不平衡最好O(n log n)每次划分完美均匀随机基准平均O(n log n)最坏O(n log n)最坏时间复杂度仍然是 O(n²)但通过随机选择 pivot使这种情况出现的概率极低因此期望时间复杂度为 O(n log n) 【降低“出现最坏情况的概率”】最好O(n log n)空间复杂度 O(log n)平均O(log n)递归调用栈深度平衡划分最坏O(n)划分极度不平衡递归退化为链表原地排序无额外数组空间开销稳定性不稳定5. 归并排序采用分治法把数组从中间分成左右两半递归地把左右两半分别排好序把两个已经有序的子数组合并成一个大的有序数组重复直到整个数组有序归并排序永远是 O(n log n)不会退化缺点是需要额外辅助空间packagemainimportfmt// mergeSort 归并排序funcmergeSort(nums[]int)[]int{// 递归终止条件// 数组长度 1天然有序直接返回iflen(nums)1{returnnums}// 1. 拆分从中间分成左右两半mid:len(nums)/2// 找到中间位置left:mergeSort(nums[:mid])// 递归处理左半边right:mergeSort(nums[mid:])// 递归处理右半边// 2. 合并将两个有序的数组合并成一个有序数组returnmerge(left,right)}// merge 合并两个【已经有序】的数组 → 返回新的有序数组funcmerge(left,right[]int)[]int{// 创建一个空的结果切片// 长度 0容量预先分配为 左右 总长度避免自动扩容更高效result:make([]int,0,len(left)len(right))// 双指针i 遍历 leftj 遍历 righti,j:0,0// 3. 双指针同时遍历谁小就先把谁放进结果forilen(left)jlen(right){ifleft[i]right[j]{resultappend(result,left[i])i// 左指针后移}else{resultappend(result,right[j])j// 右指针后移}}// 4. 处理 left 剩下的元素如果有// 此时 left 剩下的一定都比结果里的大forilen(left){resultappend(result,left[i])i}// 5. 处理 right 剩下的元素如果有// 此时 right 剩下的一定都比结果里的大forjlen(right){resultappend(result,right[j])j}// 返回最终合并好的有序数组returnresult}funcmain(){nums:[]int{5,2,3,1}fmt.Println(mergeSort(nums))// 输出: [1 2 3 5]nums2:[]int{5,1,1,2,0,0}fmt.Println(mergeSort(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)最好O(n log n)最坏O(n log n)平均O(n log n)不会像快排那样退化永远稳定高效空间复杂度 O(n)O(n)需要额外数组存储合并结果递归调用栈O(log n)总空间O(n)稳定性稳定6. 堆排序把数组变成一个大顶堆根节点最大把堆顶最大值和数组最后一位交换→ 最大值就位把剩下的元素重新调整成堆重复以上步骤直到整个数组有序时间复杂度永远O(n log n)原地排序不需要额外空间packagemainimportfmt// sortArray 堆排序对外接口funcsortArray(nums[]int)[]int{n:len(nums)// 1. 构建大顶堆从最后一个非叶子节点向上调整fori:n/2-1;i0;i--{heapify(nums,n,i)}// 2. 一个个交换堆顶到末尾并调整剩余元素fori:n-1;i0;i--{// 将堆顶最大值 与 当前数组末尾交换nums[0],nums[i]nums[i],nums[0]// 交换后剩余元素重新调整为大顶堆heapify(nums,i,0)}returnnums}// heapify 调整堆让以 i 为根的子树变成大顶堆// n堆的长度i当前要调整的根节点funcheapify(nums[]int,nint,iint){largest:i// 最大值初始化为根节点left:2*i1// 左孩子节点下标right:2*i2// 右孩子节点下标// 如果左孩子更大更新最大值下标ifleftnnums[left]nums[largest]{largestleft}// 如果右孩子更大更新最大值下标ifrightnnums[right]nums[largest]{largestright}// 如果最大值不是根节点说明需要交换iflargest!i{nums[i],nums[largest]nums[largest],nums[i]// 交换后递归调整受影响的子树heapify(nums,n,largest)}}funcmain(){// 测试用例 1nums1:[]int{5,2,3,1}fmt.Println(sortArray(nums1))// 输出: [1 2 3 5]// 测试用例 2nums2:[]int{5,1,1,2,0,0}fmt.Println(sortArray(nums2))// 输出: [0 0 1 1 2 5]}时间复杂度 O(n log n)建堆 O(n) 每次调整堆 O(log n)初始化建堆的时间复杂度为 O(n)建完堆以后需要进行 n−1 次调整一次调整的时间复杂度为 O(logn)那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。因此总时间复杂度为 O(nnlogn)O(nlogn)。空间复杂度 O(1)原地排序没有额外开辟数组只需要常数的空间存放若干变量稳定性不稳定小顶堆特点堆顶是整个堆里最小的值核心逻辑快速获取当前堆的最小值1. 海量数据找 最大的 K 个数用途数据太大无法全加载内存找最大 K 个为什么用小顶堆我们要保留大的淘汰小的小顶堆能O(1) 拿到堆里最小的那个只要新数 堆顶就替换堆顶我们要留大的扔小的那我就把当前最小的放堆顶新来一个数只要比最小的大就把最小的踢走最后剩下的自然就是最大的 K 个原理维护一个大小固定为 K的小顶堆遍历所有数据新数 堆顶 → 删堆顶插入新数最终堆里就是全局最大 K 个数2. 最小优先队列用途每次要取最小元素原理小顶堆保证堆顶最小每次出队都是最小值时间 O(logn)想拿最小值 → 直接拿堆顶拿走后堆会自动调整新堆顶又是新的最小值永远能最快拿到最小这就是 “最小优先队列”。大顶堆特点堆顶是整个堆里最大的值核心逻辑快速获取当前堆的最大值海量数据找 最小的 K 个数用途有限内存找最小 K 个原理维护大小为 K的大顶堆新数 堆顶 → 替换最终堆里就是全局最小 K 个数为什么用大顶堆快速拿到堆里最大的方便淘汰大的保留小的
