作者avogau ( 假 装)
看板TransCSI
标题Re: [问题] Quick sort
时间Sat Jan 24 00:35:38 2009
※ 引述《walks (蹦蹦跳跳)》之铭言：
: 再写题目 有点问题
: 不懂 它的基值 是怎要挑选出来的
: 查了维基
: 从数列中挑出一个元素，称为 "基准"（pivot），
: 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准
: 的後面（相同的数可以到任一边）。在这个分割之後，该基准是它的最後位置。这个称为
: 分割（partition）操作。
: 这是题目
: http://www.postimage.org/image.php?v=Pqcmhlr
: 因为答案是 29 28 22 21 6 12 36
: 不太懂是怎样选出来的 ＞ ＜ 谢谢
从程式码 int parti() 里面的第一行
int v = b[b2];
可以看的出 pivot 是取最後一个数
10 12 3 6 38 36 22 28 26 21 29
step1 10 12 3 6 21 26 22 28
29 38 36
step2 10 12 3 6 21 26 22
28 29 38 36
step3 10 12 3 6 21
22 26 28 29 38 36
step4 10 12 3 6
21 22 26 28 29 38 36
step5 3
6 10 12 21 22 26 28 29 38 36
step6 3 6 10
12 21 22 26 28 29 38 36
step6 3 6 10 12 21 22 26 28 29
36 38
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.45.53.80
1F：→ walks:^^ 01/24 12:58