有关快速排序算法的了解

看天的小树

近日看到一篇文章，关于快速排序的，觉得挺生动易懂，所以就搬过来了生命不息，学习不止啊
地址在下面http://book.51cto.com/art/201405/441266.htm

看天的小树

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

香川群子

假设有一队小学生，大部分个子高矮不同(也有部分完全相同的)
需要按身高排序时，

① 以队列中某一个人的身高为基准，比如中间的人 120cm

② 升序检查、从第1人开始向后找到大于等于这个值的位置；如 115,118,123……时，找到第3人
    降序检查、从最后1人开始向前找到小于等于这个值的位置。如 ……117,131,128,124时，找到倒数第4人

③ 把这两个位置的内容进行交换。
（原始：115,118,123……120……117,131,128,124）
（变成：115,118,117……120……123,131,128,124）

④ 重复②、③直至升序和降序的检查位置交叉相遇时停止。
此时，队列中所有比基准值t大的值都到了这个位置的后面，而比基准值小的都到了这个位置的前面。
例如： 115,118,117,109,119,……120……131,127,123,131,128,124
这其中，上半区都小于等于120、下半区都大于等于120。这样就完成了一次递归排序

大家一看就明白，接下来，只要把上半区按更小的基准如 117进行同样的分级排序、同时，对下半区按更大的基准如123进行同样的分级排序即可。
这样不断缩小分区，最后就能得到所有队列的从小到大排序。

接下来的具体过程是：接着开始分段递归
⑤ 以此位置拆分为2个队列，按递归算法依次、分别对2个队列进行上述①-⑤的递归排序计算，
    直至最小队列无需排序时退回上一层递归……继续上一层剩余的队列的递归排序计算。

就这样，很快就能完成所有的高矮交换。

呵呵。

香川群子

这个比较高级一点。
QuickSort 快速排序算法应用 返回数组第k个大小的值
http://club.excelhome.net/thread-1151561-1-1.html

香川群子

QuickSort取第k个排序结果的算法原理：

1. 检查范围L to U (数组最小下标LBound、数组最大下标UBound)
2. 取中间位置值作为比较基准r
3. 左位置i 从L to U 以及 右位置j 从 U to L各自遍历、
    检查到比基准值大/小时即停止，左右交换一次。
4. 从停止位置继续遍历、检查、交换。
5. 左右相遇时停止
6. 递归
    如果右位置j比k大时，继续递归检查L to j
    如果左位置i比k小时，继续递归检查i to U

直到k位置超出检查范围时（即k位置部分已经排序完成），停止递归、退出。

呵呵。

和标准QuickSort唯一的不同是：
不需要完成全部递归排序、只需完成到k位置时的排序即可提前退出。
（因为本函数的目的就只需要提取第k个大小的值）

看天的小树

假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。

看天的小树

为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3  1  2 5  4  6  9 7  10  8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

看天的小树

方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

maditate

看天的小树 发表于 2016-1-14 18:13
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟 ...

技术的进步比算法的改进更具划时代意义。想当年设备落后，快速排序可以比其它排序法节省不小时间。现在设备已经完全不同了，快速排序法能节省的时间基本上可以忽略。

看天的小树

maditate 发表于 2016-1-16 16:51
技术的进步比算法的改进更具划时代意义。想当年设备落后，快速排序可以比其它排序法节省不小时间。现在设 ...

见笑了 ，只是在讨论这种思想和算法啦