快速排序法

快速排序法 

快速排序（Quick Sort）法是对冒泡排序的一种改进，但都基于交换排序思想，

其基本思想是：通过一遍排序将需要排序的 数据划分成两部分，使其中一部分数据比另一部分数据小，然后再分别对这两部分数据继续进行这种排序，按此规则继续，直到 每个部分为空或只含一个数时，整个快速排序结束。这是一种分治策略，将大批的数据逐步分解，可使用递归的方法编写程序， 使程序更简洁。

算法描述 快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤为： 

（1）设定一个分界值，通过该分界值将数组分成左、右两部分。 

（2）将大于等于分界值的数据集中到数组右边部分，小于分界值的数据集中到数组的左边部分。此时，左边部分中各元素 都小于等于分界值，而右边部分中各元素都大于等于分界值。 

（3）左边部分和右边部分的数据独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左、右两部 分，同样在左边放置较小值，右边放置较大值。整个数组的右边部分的数据也可以做类似处理。 

（4）重复上述过程，通过递归将左边部分排好序后，再右边部分递归顺序。当左、右两部分各数据排序完成后，整个数组 的排序也就完成了。

提示 快速排序法通过递归的形式完成排序。

下面以一组待排序的数据演示快速排序的过程，假设有8个需要排序的数据序列如下：

 69，65，90，37，92，6，28，54

假设数组A中保存着这8个数据，其排序过程如上图所示。

（1）在变量left中保存数组的最小序号0，在变量right中保存数组的最大序号7，在变量base中保存数组的第1个元素A[0]作为 基准。如图a所示。 

（2）从数组右侧开始，逐个取出元素与base比较，直到找到比base小的数据为止。在本例中，数组最右侧的元素A[right]的值 54就比base变量中保存的值69小。 

（3）将右侧比基准base小的数（数组元素A[right]中的数）保存到A[left]（A[0]）元素中。 

（4）接下来，从数组左侧开始，逐个取出元素与base比较，直到找到比base大的数据为止。在本例中，数组最左侧的元素 A[left]（即A[0]）的值为54，比base的值小，将left自增1（值为1）。再取A[left]（A[1]）的值65与base的值69比较，65<69，继续将 left自增1（值为2）。再取A[left]（A[2]）的值90与base比较，因90>69，结束查找。 

（5）将左侧比基准base大的数（数组元素A[2]）保存到A[right]（A[7]）元素中。 

（6）将base中的值保存到A[left]（A[2]）中。经过这些运算，得到如图b所示的效果。 提示 经过这一次分割，base数据左侧（也就是left所指向的数据）的数比base小，而base数据右侧的数比base大。 

（7）接下来，通过递归调用，将left左侧的数据进行同样的排序，再将left右侧的数据进行同样的排序。 经过这样的递归调用，最终可将数据完成排序操作。

从前面的分析可知，快速排序是一个递归过程，其算法描述如下：

void 快速排序(数组, 左侧序号, 右侧序号)
{
    分割数据, 将left保存到 i
    快速排序(数组, 原左侧序号, i-1);
    快速排序(数组, i+1, 原右侧序号);
}