quick sort
分治思想，每次选中一个基准，然后为此基准找到合适位置，使得左边全部小于此基准，右边全部大于此基准。然后对左右两边的数组重复以上步骤。
如何为基准找到合适位置？同时从左往右、从右往左用下标扫描数组，如果分别扫描到<基准，>基准的树，就交换他们位置，如果扫描过程中下标交叉，说明交叉点就是基准应该放置的位置。
go代码
func portition(slice *[]int, start, end int) int {
left := start + 1
right := end
for left <= right {
for left <= right && (*slice)[left] <= (*slice)[start] {
left++
}
for left <= right && (*slice)[right] >= (*slice)[start] {
right--
}
if right <= left {
break
}
tmp := (*slice)[left]
(*slice)[left] = (*slice)[right]
(*slice)[right] = tmp
}
log.Println(start, end, left, right)
tmp := (*slice)[start]
(*slice)[start] = (*slice)[right]
(*slice)[right] = tmp
return right
}
func sortInt(unsort *[]int, s, e int) {
if s >= e {
return
}
log.Println(unsort)
mid := portition(unsort, s, e)
sortInt(unsort, s, mid-1)
sortInt(unsort, mid+1, e)
}
heap sort
有点类似冒泡，每次选出最大值放到最右边，然后迭代。只不过采用完全二叉树的形式去找最大值。
二叉树：每个节点最多2个子元素
满二叉树 full binary tree：每个节点0或2个子元素
完全二叉树 complete binary tree：刚好可以用数组完整表示的二叉树。
步骤：
1.根据数组初始化heap，使得最大值在对顶，max-heap
2.将堆顶值与末尾值交换位置，然后再次构造max-heap
3.对步骤2迭代
java代码
参考此连接
https://www.programiz.com/dsa/heap-sort
网友评论