ToB企服应用市场:ToB评测及商务社交产业平台
标题:
算法 in Golang：Quicksort（快速排序）
[打印本页]
作者:
耶耶耶耶耶
时间:
2023-6-6 22:24
标题:
算法 in Golang：Quicksort（快速排序）
算法 in Golang：Quicksort（快速排序）
Quicksort（快速排序）
快速排序 O(nlog2^n)，比选择排序要快 O(n²)
在日常生活中经常使用
使用了 D & C 策略（分而治之）
使用 Quicksort 排序数组
不需要排序的数组（也就是 Base Case 基线条件）：
[]，空数组
，单元素数组
很容易排序的数组：
[a, b]，两个元素的数组，只需检查它们之间的大小即可，调换位置
3 个元素的数组（例如 [23, 19, 35]）：
使用 D & C 策略，简化至基线条件（Base case）
从数组中随便选一个元素，例如 35，这个元素叫做 pivot（基准元素）
找到比 pivot 小的元素，找到比 pivot 大的元素，这叫做分区：[23, 19], (35), []
如果左右两个子数组已排好序（达到基线条件），结果：左边 + [pivot] + 右边
如果左右两个子数组没排好序（没达到基线条件），那么：
quicksort(左边) + [pivot] + quicksort(右边)
使用 Quicksort 排序数组的步骤
选择一个 pivot
将数组分为两个子数组：
左侧数组的元素都比 pivot 小
右侧数组的元素都比 pivot 大
在两个子数组上递归的调用 quicksort
创建项目
[code]~/Code/go via
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4