图解快速排序算法,图解快速排序的方法

　　假设我们现在对10个数字“6 1 2 7 9 3 4 5 10 8”进行排序。首先，在这个序列中找一个随机数作为参考数(不要被这个名词吓到，这是参考数，后面你就知道它是干什么用的了)。为方便起见，让第一个数字6作为参考数字。接下来，这个序列中所有大于参考数的数字需要放在6的右边，小于参考数的数字需要放在6的左边，类似于下面的排列。

　　3 1 2 5 4 6 9 7 10 8

　　在初始状态下，数字6位于序列的第一个位置。我们的目标是将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指向序列的最右边(即j=10)，并指向数字8。

　　首先，哨兵J开始了。因为这里设置的参考号是最左边的号，所以让哨兵J先出去很重要(请自行思考为什么)。哨兵一步一步向左移动(即J——)，直到发现一个小于6的数字停下来。接下来，哨兵I一步一步向右移动(即I)，直到发现一个大于6的数，停下来。最后，哨兵J停在了5号门前，哨兵I停在了7号门前。

　　现在交换Sentinel I和Sentinel J指向的元素的值，交换后的顺序如下。

　　6 1 2 5 9 3 4 7 10 8

　　至此，第一次交流结束。接下来，哨兵J继续向左移动(友情提示，哨兵J每次必须先开始)。他找到了4(比基准数6小，符合要求)，然后停了下来。哨兵也继续向右移动。他找到了9(大于基准数6，符合要求)就停了。此时再次进行交换，交换后的顺序如下。

　　6 1 2 5 4 3 9 7 10 8

　　第二次交流结束，“试探”继续。哨兵J继续向左移动。他找到了3(小于基准数6，满足要求)然后停了下来。我一直向右移动，该死！这时哨兵I和哨兵J相遇，哨兵I和哨兵J都去了3。至此，“探查”结束。我们交换基准数6和3。交换后的顺序如下。

　　3 1 2 5 4 6 9 7 10 8

　　到这第一轮“探索”结束时。此时以参考数字6为分界点，6左边的数字都小于等于6，6右边的数字都大于等于6。回顾一下刚才的过程，其实哨兵J的任务是寻找小于基准数的数，而哨兵I的任务是寻找大于基准数的数，直到I和J相遇。

　　好了，解释完毕。现在引用号6已经返回了，正好在序列的第6个位置。此时，我们已经将原始序列以6为分界点拆分为两个序列。左边的顺序是“3 1 2 5 4”，右边的顺序是“9 7 10 8”。接下来，需要分别处理这两个序列。因为左右的序列目前还是很混乱的。不过，没关系，我们已经掌握了方法。接下来我们只需要模拟刚才的方法分别处理6左右的序列。现在我们来处理6左边的序列。

　　左边的顺序是“3 1 2 5 4”。请以3为基数调整此顺序，使3左边的所有数字都小于等于3，3右边的所有数字都大于等于3。好了，开始写吧。

　　如果你的模拟是正确的，调整后的顺序应该是。

　　2 1 3 5 4

　　好了，现在3又回到原位了。接下来，需要处理左边的序列“2 1”和右边的序列“5 4”。序列“2 ^ 1”以2为参考数进行调整，处理后的序列为“1 ^ 2”，其中已返回2。序列“1”只有一个数，不需要任何处理。到目前为止，我们都处理了序列“2 1”，得到了序列“1 2”。序列“5 4”的处理也遵循这种方法，最终序列如下。

　　1 2 3 4 5 6 9 7 10 8

　　对于序列“9 7 10 8”，也模拟刚才的过程，直到不能分离出新的子序列。最终，你会得到这样一个序列，如下。

　　1 2 3 4 5 6 7 8 9 10

　　至此，排序完全完成。细心的同学可能已经发现，每一轮快速排序，其实就是重置本轮的基准数，直到所有的数都重置完毕，排序才算完成。下面这张霸气的图描述了整个算法的处理过程。

　　快速排序更快，因为与冒泡排序相比，每次交换都是跳跃式的。每次排序的时候，设定一个基准，所有小于等于基准的数字放在左边，所有大于等于基准的数字放在右边。这样每次交换的时候就不用像冒泡排序一样在相邻数之间交换了，交换的距离也会大很多。所以总的比较交流次数少了，速度自然就提高了。当然，最坏的情况，可能还是相邻的两个号码互换了。所以快速排序最差的时间复杂度和冒泡排序是一样的，都是O(N2)，其平均时间复杂度都是O(NlogN)。

　　模板：

　　c版本

　　void quick_sort(int q[]，int l，int r)

　　{

　　if (l=r)返回；

　　int i=l - 1，j=r 1，x=q[(l r)/2]；//在这里，选择中间的数字作为参考数字。

　　while (i j)

　　{

　　我愿意；while(q[I]x)；

　　做j-；while(q[j]x)；

　　if (i j) swap(q[i]，q[j])；

　　}

　　quick_sort(q，l，j)，quick_sort(q，j ^ 1，r)；

　　}

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。