我的双节日志——学习快速排序

排序过程

• 橙色为排序的基准数 绿色为交换后的基准数位置
• 黄色为右哨兵 青色为左哨兵
• 粉色为两即将交换的数

本人用python写的(感觉效果不好)

原理

这是序列：

我们需要以基准数为分界点，让pivot左边的数比它小(即左边序列的元素都 <= -1)，pivot右边的数比它大(即又边序列的元素都 >= -1)。

下面以序列最左侧的元素(首元素)为基准数(后面就叫它pivot吧)。

再通过设置两个哨兵left,right(left < right)，从序列两端开始与pivot比较。

橙色背景为基准数pivot

<1>先移动右边的哨兵(后面解释为什么)：

由于 -1 < 1，符合条件(条件：arr[right] >= pivot)，所以我们将哨兵right左移到下一元素与pivot比较。

我们移动到-3处，发现 -1 > -3,不符合我们之前的条件，所以我们让哨兵right停下。

<2>现在移动左哨兵left：

首元素为 -1 ， -1 = -1,符合条件(条件：arr[left] <= pivot)，现在左哨兵继续左移。

我们发现移动后设备left处的数 2 > -1，不符合条件，所以哨兵停下。

快速排序的核心思想就是分治。

我们以基准数为界，基准数左侧所有元素皆小于基准数，右侧所有元素皆大于基准数。

我们左侧所有元素和右侧所有元素可以继续进行这个操作，再取出一个基准数为界，如此反复下去，最后使得整个序列有序。

故而我们在两哨兵停下时，让其所在元素进行交换以达目的。

<3>交换元素：

<4>继续移动右哨兵直到遇到左哨兵:

我们发现左右哨兵已经相遇，这时候说明相遇位置的左侧所有元素<=基准数，右侧所有元素>基准数。这时候我们将相遇位置处元素与基准数交换来分界序列

<5>交换基准数位置：

交换位置后我们发现，基准数-1左侧已经排序完成，右侧还未排序完，下面我们开始用相同的思路对右侧序列进行排序。

排序子序列

我们快速排序的函数是QuickSort(array[],begin,end);

其中array为待排序序列(数组)，begin(begin = left + 1)是array中要排序的起始位置，end是结束位置。

红色框内是要排序的序列

现在我们按照之前排序总序列的方法来排序右边子序列。

由于我们不对左侧范围外序列排序，所以这边我没写出来。不过注意，左侧的序列仍然是存在的，我们仍然可以对其操作，所以我们要避免这种越界事情发生。

左侧序列我没写出来

现在我们移动右哨兵right到符合条件位置：

发现与左哨兵相遇，所以继续之前的交换基准数位置的操作。

这时我们发现基准数与哨兵相遇位置相同，那么怎么办呢？

这证明了右边序列元素都比基准数大，所以我们继续对右边排序！

QuickSort(array[],left+1,right);

下面我直接列出后面的所有步骤：

结果：

为什么右哨兵先行

我直接举个例子给大家了解一下。

下面是待排序的序列：

1 0 3 7 2

哨兵left移动到3

1 0 3 7 2

      ^

下面移动哨兵right到3，然后与基准数交换

3 0 1 7 2

很显然这使得比基准数大的数交换到了左边。

如果是右哨兵先行的话就能保证交换的数是绝对比基准数小的。

 原因：

哨兵left移动后到达比基准数大的数位置，可能该位置后的还有一个数大于这个基准数，但left已经无法移动。

如果此时哨兵left所在位置右边都大于基准数的话，只能等待right移动会面，被迫把大于基准数的数交换到了前面。

当然这也是我们使用的基准数是第一位数才造成的问题，我们也可以自行改动代码来解决问题。

代码：

C语言：

VS得使用动态数组编译，这用的是dev

C++：

VS上可编译。

Python：

写blog也是双节日记。

欢迎大家指出错误，互相学习让我们一起成长！