none
快速排序与C++ RRS feed

  • 问题

  • 大家好,我是一名大一的学生,最近看算法(c++实现)书时候遇到了个问题:快速排序到底是怎么实现的?能不能举个例子,比如,5,6,4,9,21,14,15,8来详细分析下?谢谢了
    bylh
    2009年3月31日 9:06

答案

  • 具体的算法想必你已经在书上看的很清楚了。可能就是不能很好的理解。在这里我利用你的这个数列来一次执行过程的演变。
    首先咱们在数列里选择一个游标。比如咱们从数列的尾端取一个数做游标。(去游标的位置其实是随便的,但是如果去不好会严重影响时间复杂度)。
    快拍是一种拆分排序,每次拆分后,对拆分的两个子数列在进行同样方式的排序。
    首先进行第一次排序。
    5,6,4,8,9,21,14,15(由于游标正好可以放到中间,所以第一次排序不做仔细介绍)。
    那么现在就出现了两个子序列
    5,6,4 和9,21,14,15
    对第一个子数列在进行排序。游标是4
    结果是4,5,6。无需再进行拆分。
    对第二个字序列进行排序,游标是15
    这里就终于体现了快排算法了。
    整个过程是:
    9,21,14 (9 <15 i 不变 j加1)
    i
        j
    9,21,14 (21 > 15 i +1 和j交换。 i 加1 j加1)
        i
             j
    9,14,21
        i
            j

    2009年3月31日 10:33
    版主

全部回复

  • 具体的算法想必你已经在书上看的很清楚了。可能就是不能很好的理解。在这里我利用你的这个数列来一次执行过程的演变。
    首先咱们在数列里选择一个游标。比如咱们从数列的尾端取一个数做游标。(去游标的位置其实是随便的,但是如果去不好会严重影响时间复杂度)。
    快拍是一种拆分排序,每次拆分后,对拆分的两个子数列在进行同样方式的排序。
    首先进行第一次排序。
    5,6,4,8,9,21,14,15(由于游标正好可以放到中间,所以第一次排序不做仔细介绍)。
    那么现在就出现了两个子序列
    5,6,4 和9,21,14,15
    对第一个子数列在进行排序。游标是4
    结果是4,5,6。无需再进行拆分。
    对第二个字序列进行排序,游标是15
    这里就终于体现了快排算法了。
    整个过程是:
    9,21,14 (9 <15 i 不变 j加1)
    i
        j
    9,21,14 (21 > 15 i +1 和j交换。 i 加1 j加1)
        i
             j
    9,14,21
        i
            j

    2009年3月31日 10:33
    版主
  • 嗯,我再理解下,谢谢您
    bylh
    2009年3月31日 12:13