Posted on 2008-01-10 19:52
形式系统 阅读(386)
评论(0) 编辑 收藏 引用 网摘 所属分类:
数据结构
快速排序的指导思想:以某个数(通常选第一个)作为分界,小于该数的调至左边,大于该数的放在右边。然后分别对左右两段序列进行同样的操作,这样子序列越分越小。最后只有一个元素。那么整个序列自然是有序的。
以下通过实例演示:
第一趟:
序列 |
说明 |
32 08 54 12 29 12 25 62 55 41 37
|
32<37,37应放在32右边,不动。 |
32 08 54 12 29 12 25 62 55 41 37
|
依次考查41、55、62,都不动。
|
┌────────────┐
32 08 54 12 29 12 25 62 55 41 37
|
32>25,25应位于32左边,具体实现上把32与25交换。 |
25 08 54 12 29 12 32 62 55 41 37 |
再从左边开始扫描,08<32,不动。 |
┌────────┐
25 08 54 12 29 12 32 62 55 41 37 |
54>32,交换。 |
┌───────┐
25 08 32 12 29 12 54 62 55 41 37 |
再从右边继续考察,32>12,交换。 |
25 08 12 12 29 32 54 62 55 41 37 |
再从左边继续考察,12<32,不动。 |
25 08 12 12 29 32 54 62 55 41 37 |
29<32,不动。 |
25 08 12 12 29 32 54 62 55 41 37 |
以32为分界线,将整个序列分为两段。 |
第二趟:
对左边序列在进行划分:
25 08 12 12 29
25 08 12 12 29
┌───────┐
25 08 12 12 29
12 08 12 25 29
12 08 12 25 29
12 08 12 25 29
25将序列又分为两段,其中{29}只有一个元素,不需要继续分段。另一段为{12,08,12}
|
对右边序列在进行划分:
54 62 55 41 37
┌───────┐
54 62 55 41 37
┌─────┐
37 62 55 41 54
┌────┐
37 54 55 41 62
┌───┐ 37 41 55 54 62
37 41 54 55 62
54将序列又分为两段:{37,41}{55,63}
|
第三趟(分别对上述子序列再进行划分):
12 08 12
12 08 12
┌──┐
12 08 12 (12<08,交换)
08 12 12
此时,{08} {23}均为单个元素构成的序列,不需再划分了。
|
37 41
37 41 (比较)
37 41 (37<41,不动)
此时,{41}也为单个元素序列。
|
55 62
55 62
55 62 (55<62,不动)
|
最后,将上面的排序合成为整体:
第一趟结果:25 08 12 12 29 32 54 62 55 41 37
第二趟结果:12 08 12 25 29 32 37 41 54 55 62
第二趟结果:08 12 12 25 29 32 37 41 54 55 62
(红色斜体均表示每趟的分界元素。)
(要求:写出每趟结果及第一趟的每步移动结果(即上面第一个表))