算法-排序 快速排序 2024-03-23 默认分类 暂无评论 380 次阅读 <h2><a class="cl-offset" name="cl-1"></a>快速排序 </h2> 快排利用了分治的思想 每轮排序都将首位设置为基准元素 (这里假设为X) 保证 X 所在的位置前后都是非逆序的 完成上述的操作的同时, X所在的位置为排序的最终位置 最后将该序列划分为两个子区间: `[ 小于X的 ]` X ` [ 大于X的 ]` 之后对前后两个子区间同样进行一次快速排序 循环执行下去直到最终分隔的子区间不能再分隔即完成排序. **快速排序 速记** 递归调用 传AB 小A大B 首位基 i j交会 循环退 交替扫描 逆归位 循环结束 基归位 划分区间 再快排 ```Go package code import "fmt" func qSort(arr []int, a int, b int) { if a < b { i, j := a, b tmp := arr[a] for i != j { for j > i && arr[j] > tmp { j-- } arr[i] = arr[j] for j > i && arr[i] < tmp { i++ } arr[j] = arr[i] } arr[i] = tmp qSort(arr, a, i-1) qSort(arr, i+1, b) } } func TestSort2() { arr := []int{10, 7, 8, 9, 1, 5} n := len(arr) fmt.Println("Sorted array is:", arr) qSort2(arr, 0, n-1) fmt.Println("Sorted array is:", arr) } ``` 文章目录 快速排序 标签: 算法 转载请注明文章来源 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭