形式系统

计算机专业教学
posts - 48, comments - 150, trackbacks - 0, articles - 10
  教师博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

关于快速排序的过程

Posted on 2008-01-10 19:52 形式系统 阅读(386) 评论(0)  编辑 收藏 引用 网摘 所属分类: 数据结构

       快速排序的指导思想:以某个数(通常选第一个)作为分界,小于该数的调至左边,大于该数的放在右边。然后分别对左右两段序列进行同样的操作,这样子序列越分越小。最后只有一个元素。那么整个序列自然是有序的。
    以下通过实例演示:

第一趟:
序列 说明


32
    08    54    12    29    12    25    62    55    41    37

 
32<3737应放在32右边,不动。


32    08    54    12    29    12    25    62    55    41    37


依次考查415562,都不动。

┌────────────┐

32    08    54    12    29    12    25    62    55    41    37


32>2525应位于32左边,具体实现上把3225交换

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

(红色斜体均表示每趟的分界元素。)
(要求:写出每趟结果及第一趟的每步移动结果(即上面第一个表))


只有注册用户登录后才能发表评论。