算法 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
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
