数据结构快速排序问题

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

答案：
clipboard.png

请问大牛，这个解题过程是怎么推导的啊？我从书上看，书上说是用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两个子序列";然后继续对左边序列做递归操作……

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

回答：

明显每次移动答案是以序列的第一个数作为基准值，也就是你的中间值

以上是 数据结构快速排序问题 的全部内容， 来源链接： utcz.com/a/166768.html

回到顶部