数据结构快速排序问题

题:已知一组键值序列(3,6,8,9,2,7,4,3),试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果。

答案:

请问大牛,这个解题过程是怎么推导的啊?我从书上看,书上说是用low high重叠法,任意选一个中间值,然后每次把小于中间值的放左边,大于中间值的放右边。 感觉和标准答案的解法对不起来啊。请问这个解法如何推导?为什么这样写?

最佳答案

答案的交换算法


以下用加粗表示low的位置,红色表示high的位置,

初始 3,6,8,9,2,7,4,3

  1. 先用一个额外的存储空间存储low的值3(用tmp表示)
  2. high往左移动直到对应位置的值小于tmp, 将它的值赋给low指向的位置,(如果当high=low时还没找到则停止)
    得到 2,6,8,9,2,7,4,3
  3. 将low往右移动直到对应位置的值大于tmp,将它的值赋给high指向的位置,(如果当high=low时还没找到则停止)
    得到 2,6,8,9,6,7,4,3
  4. 以上2、3交替进行,直到low=high, 最后将tmp的值赋给low指向的位置, 结果2,3,8,9,6,7,4,3, 此时
    low指向的值3已经在正确的位置上,以low为分界得到两个子序列2和8,9,6,7,4,3
  5. 对步骤4得到的子序列中长度大于1的序列应用步骤1-5,直到所有子序列都不大于1,排序完成。子序列的处理方式相同这里不再分析

所谓的low high重叠法大概就是指这个

以下可能是废话


答案的实现是选择序列的第一个元素作为中间值

排序过程是递归进行的,对一个序列作一层递归调用后, 会得到两个序列(可能为空),需要再对两个子序列做同样的操作,直到子序列的长度为0或1。

对于题中的序列,第一层递归选择3作为中间值,得到的两个子序列分别为2 和 8,9,6,7,4,3,左边序列只有一个元素,不需要递归下去了,右边序列需要进行第二层递归。选择子序列的第一个值也就是8作为中间值,得到3,4,6,7和9两个子序列";然后继续对左边序列做递归操作……

至于为什么得到的子序列的顺序是这个样子, 这跟交换的算法有关