手把手带你认识快速排序（1）——简介

手把手带你认识快速排序（一）——简介

前言

最近在准备软考，前些天看了那个老师讲的快速排序，个人见解他讲的快速排序还是有点问题的。至于他讲的有什么问题，我就不说了，自己看下我的文章，然后自己对照吧。

1.快速排序简介

首先，快速排序是交换排序的一种个，交换排序还有冒泡排序，快速排序是对冒泡排序的一种改进。有兴趣的自己研究冒泡排序。我这里只说一下快速排序：

快速排序，其基本思想是通过一趟排序，将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要笑，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.快速排序过程分析

设有序列 68 59 52 72 57 28 96 33 25 19.

那么需要从这个序列中选出来一个基准，然后进行筛选，使得这个基准前面的数据都比它小，后面的都比它大。

一般情况下，不选择第一个数据作为基准，而选择中间数作为基准。我们就选择57作为基准吧。下面，我就开始一步步的进行第一趟排序。

a.首先，将57与第一个数进行位置互换：57 59 52 72 68 28 96 33 25 19，那么现在就先将57用一个空的位置来替换，我这里用一个括号来代替：

（） 59 52 72 68 28 96 33 25 19

b.现在先从右边开始，遇到比57小的数据时，就将括号替换成那个数，同时，那个位置成为这个括号。即：19 59 52 72 68 28 96 33 25 （19）。

c.现在从左边开始，遇到比57大的数据时，将括号替换成那个数，那个位置变成这个括号。即：19 （59） 52 72 68 28 96 33 25 59.

d.重复b、c的动作，直到向左移动和向右移动的指针重合。

e.现在，将57替换那个位置，这样最后就能得到这样的数列 19 25 52 33 28 57 68 72 59

f.现在，在57左边的都是比57小的，右边的都是比57大的，对着两个子序列分别重复abcde的步骤。

3.快速排序的改进。

快速排序虽然名为快速排序，但是是有条件限制的，在某些情况下，快速排序的排序效率没有直接插入排序的效率高。而这个临界点，当然就是序列中数的个数了。具体是多少个我忘了，这个就涉及到一个更深层次的讨论了。

我这里只讨论到此，下篇博文，我将给大家贴一下快速排序的代码。下面我就说一下视频中老师讲的到底出现了什么问题。

视频中，老师讲到交换时，所说的是位置交换，大家一定想到了加入临时变量，然后就是那三句实现了交换。可是在排序中，你有想一下这样会增加多少语句么？

但是如果你只是把它当成一个空篮子，这样在像空篮子里面放东西时，就不涉及到交换，而只是单纯的数据覆盖。无疑这样的效率是比前者高的。

如果你没看懂后面说的，那么我将在代码中给大家同时展示一下二者的代码，相信大家看后就会明白了。