算法导论第七章-快速排序
Avatera · · 1184 次点击 · · 开始浏览7.1-1 参照图7-1的方法,说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。
答:golang实现:
// Partition 分解重排步骤
func Partition(a QuickSortInterface, p int, r int) int {
x := a.Get(r)
i := p - 1
for j := p; j < r; j++ {
if a.Get(j) < x {
i++
a.Swap(i, j)
}
}
a.Swap(i+1, r)
return i + 1
}
结果为:
[9 5 8 7 4 2 6 11 21 13 19 12]
7.1-2 当数组A[p..r]中所有元素的值都相同时,PARTITION返回的q值是什么?修改PARTITION,使得当数组A[p..r]中所有元素的值都相同时,q=[(p+r)/2]
答:PARTITION返回的值为r;把第四行代码改为
if a.Get(j) < x && j%2 == p%2
7.1-3 请简要地证明:在规模为n的子数组上,PARTITION的时间复杂度为O(n)
答:在for循环中,对于子数组的每个元素,都会做一次判断,在循环外的操作时间代价都是常数级的,所以复杂度为O(n)。
7.1-4 如何修改QUICKSORT,使得它能够以非递增进行排序?
答:将a.Get(j) < x判断条件改为a.Get(j) > x即可。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
7.1-1 参照图7-1的方法,说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。
答:golang实现:
// Partition 分解重排步骤
func Partition(a QuickSortInterface, p int, r int) int {
x := a.Get(r)
i := p - 1
for j := p; j < r; j++ {
if a.Get(j) < x {
i++
a.Swap(i, j)
}
}
a.Swap(i+1, r)
return i + 1
}
结果为:
[9 5 8 7 4 2 6 11 21 13 19 12]
7.1-2 当数组A[p..r]中所有元素的值都相同时,PARTITION返回的q值是什么?修改PARTITION,使得当数组A[p..r]中所有元素的值都相同时,q=[(p+r)/2]
答:PARTITION返回的值为r;把第四行代码改为
if a.Get(j) < x && j%2 == p%2
7.1-3 请简要地证明:在规模为n的子数组上,PARTITION的时间复杂度为O(n)
答:在for循环中,对于子数组的每个元素,都会做一次判断,在循环外的操作时间代价都是常数级的,所以复杂度为O(n)。
7.1-4 如何修改QUICKSORT,使得它能够以非递增进行排序?
答:将a.Get(j) < x判断条件改为a.Get(j) > x即可。