Python快速排序

陈新龙

排序算法我们之前已经讲过了冒泡排序和选择排序，今天我们就来学习一种新的排序算法：快速排序。快速排序是冒泡排序的改进版本，通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据要比另外一部分的所有数据小，然后按此方法对两部分数据分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列。

首先我们将排序的元素进行分区，从排序的元素中设置一个基准（基准可以任意设置，但是基本上都是把第一个数字设置为基准），比基准大的元素放在右边，比基准小的元素放在左边，将左右两个分区重复以上步骤直到所有元素都是有序的。所以我们可以把快速排序联想成东拆西补或者西拆东补，一边拆一边补，直到所有的元素都达到有序的状态。

待排序元素初始状态：

把5作为与其他元素比较的基准元素，设置两个指针left和right。

1. 把5拆到一边作为基准元素（第二行数字为元素的初始状态）;

2. right指针从右向左扫描，首先4和5比较，4<5，拆4，补原元素5的空缺位，left指针右移;

3. 7和5比较，7>5，拆7补元素4的空缺位。right指针左移;

4. 8和5比较，8>5，保持不变，right指针继续左移;

5. 5和1比较，1<5补元素7的空缺位，left指针右移，此时left=right，则将基准元素5补入到left/right的位置，结束这一趟拆补过程。

Python代碼部分：

第一步：在代码中我们先增加一条需要排序的数列example。并且设置a：为起始位置，b：为末尾位置，接下来开始快速排序定义，head相当于左指针，left相当于右指针，base为基准数。

第二步：从右往左扫描，通过偏移right指针，寻找比基准数小的元素，当找到比基准数小的元素后，将其赋值给left指针所在的位置。

第三步：从左向右扫描，通过偏移left指针，寻找比基准数大的元素，找到后，将其赋值right指针所指向的位置。

第四步：不断重复二三步骤，直到left和right指针重合，这样所有的元素都被扫描一遍了，将基准数赋予重合位置，完成一遍排序，左边的数字比基准数小，右边数字比基准数大。

第五步：以之前的基准数为分割点，对左右两侧按照以上的方法进行递归，最后排序结束。

快速排序的效率虽然比冒泡排序高，但是它是一种不稳定排序法：在一组数据中原有A1和A2两个相等数字，不稳定排序算法排序后，可能导致排序之后A2反而在A1之前，原有顺序颠倒，这就称为不稳定排序。