sort.md

排序

常考排序

快速排序

funcQuickSort(nums []int) []int {
// 思路：把一个数组分为左右两段，左段小于右段quickSort(nums, 0, len(nums)-1)
returnnums
}
// 原地交换，所以传入交换索引funcquickSort(nums []int, start, endint) {
ifstart<end {
// 分治法：dividepivot:=partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
// 分区funcpartition(nums []int, start, endint) int {
// 选取最后一个元素作为基准pivotp:=nums[end]
i:=start// 最后一个值就是基准所以不用比较forj:=start; j<end; j++ {
ifnums[j] <p {
swap(nums, i, j)
i++
}
}
// 把基准值换到中间swap(nums, i, end)
returni
}
// 交换两个元素funcswap(nums []int, i, jint) {
t:=nums[i]
nums[i] =nums[j]
nums[j] =t
}

归并排序

funcMergeSort(nums []int) []int {
returnmergeSort(nums)
}
funcmergeSort(nums []int) []int {
iflen(nums) <=1 {
returnnums
}
// 分治法：divide 分为两段mid:=len(nums) /2left:=mergeSort(nums[:mid])
right:=mergeSort(nums[mid:])
// 合并两段数据result:=merge(left, right)
returnresult
}
funcmerge(left, right []int) (result []int) {
// 两边数组合并游标l:=0r:=0// 注意不能越界forl<len(left) &&r<len(right) {
// 谁小合并谁ifleft[l] >right[r] {
result=append(result, right[r])
r++
} else {
result=append(result, left[l])
l++
}
}
// 剩余部分合并result=append(result, left[l:]...)
result=append(result, right[r:]...)
return
}

堆排序

用数组表示的完美二叉树 complete binary tree

完美二叉树 VS 其他二叉树

动画展示

核心代码

package main
funcHeapSort(a []int) []int {
// 1、无序数组a// 2、将无序数组a构建为一个大根堆fori:=len(a)/2-1; i>=0; i-- {
sink(a, i, len(a))
}
// 3、交换a[0]和a[len(a)-1]// 4、然后把前面这段数组继续下沉保持堆结构，如此循环即可fori:=len(a) -1; i>=1; i-- {
// 从后往前填充值swap(a, 0, i)
// 前面的长度也减一sink(a, 0, i)
}
returna
}
funcsink(a []int, iint, lengthint) {
for {
// 左节点索引(从0开始，所以左节点为i*2+1)l:=i*2+1// 有节点索引r:=i*2+2// idx保存根、左、右三者之间较大值的索引idx:=i// 存在左节点，左节点值较大，则取左节点ifl<length&&a[l] >a[idx] {
idx=l
}
// 存在有节点，且值较大，取右节点ifr<length&&a[r] >a[idx] {
idx=r
}
// 如果根节点较大，则不用下沉ifidx==i {
break
}
// 如果根节点较小，则交换值，并继续下沉swap(a, i, idx)
// 继续下沉idx节点i=idx
}
}
funcswap(a []int, i, jint) {
a[i], a[j] =a[j], a[i]
}

参考

十大经典排序

二叉堆

练习

• 手写快排、归并、堆排序