快速排序算法 - 好文

前言

在计算机程序设计过程中，经常会出现将无序的序列排列为有序序列的情形。由于待排序的记录数量不同，可以将排序的方法分为两类，一是将待排序记录存放在计算机随机存储器中进行排序的过程，称作
内部排序，二是需要进行排序的数据基数很大，内部存储器无法在一次存储过程中将数据完整排序，需要在排序过程中对外存进行访问，这称作外部排序。

内部排序主要分为四大类，第一类称作插入排序，即将一个单独的元素插入到一个已经排列好的有序序列中，包括了
直接插入排序以及折半插入排序、2-路插入排序、希尔排序，第二类称作交换排序
，主要完成的过程是通过特定的顺序，将不同顺序的元素经过不停交换达到了序列有序的效果，主要包括冒泡排序以及快速排序法，第三类称作选择排序，主要包括了堆排序
，第四类称作归并排序，主要将两个或者两个以上的有序表合并成一个新的有序表。

正文

在学习程序语言的过程中，我们或多或少的会涉及到一些排序算法，而涉及次数最多的便是冒泡排序法，而快速排序法，是对冒泡排序法的一种改进，基本思路如下
1）确定一个关键字（枢轴），通过一趟排序将原有的序列分为两个序列，一个序列中的所有元素均小于等于枢轴量，另一个序列中的元素均大于等于枢轴量
2）利用递归的思想，将两个序列再次分别确定枢轴量，接着进行两个子序列的快速排序。

按照已知的思路，对于快速排序法进行具体过程的书写，以任意一个序列为例：

假设有一个无序的序列，记作{5，3，2，6，4，7，1}，示意图如下，首先确定一个关键字（即枢轴量，第一个数字5），确定两个数i与j，将ij分别放置在队伍的首端与队伍的末端。

将队伍末端的坐标j（高坐标）向前移动，遇见第一个比关键字数值小的元素时，将该元素与首坐标i（低坐标）指向的元素进行位置互换，这里直接先将元素1与元素5对换，示意图如下：

再将低坐标进行左移，若遇见了元素值大于关键字值的情形时，将高坐标低坐标所指的元素位置互换，这里需要将6与5位置互换

高坐标继续向左移动，移动至元素4，因为4小于5，所以将4与5位置互换。因此就满足了第一次操作的最终目的，使原有序列根据关键字分为两个新的序列12。将小于关键值的元素放置在序列1内，即挪移至关键字的左侧，将大于关键字值的元素放置于序列2中，挪移至关键字的右侧。低坐标继续向右移动，直至低坐标的值等于高坐标，第一次分序列的操作就此结束。此时低坐标与高坐标均落在同一个位置，记作j，同时该位置也是原有序列关键字的最终位置。

原有的序列被分为了{1，3，2，4}{5}{7，6}两个序列以及一个单独的元素值5。

在分割完毕原有的序列之后，需要对于两个子序列进行相同的操作，子序列分割而成的子序列继续进行操作，最终达到排序的结果为{1，2，3，4，5，6，7}，关于子序列整体的操作函数如下：
void Quick(int a[],int low,int high) { int point; if(low<high) {
point=partion(a,low,high); Quick(a,low,point-1); Quick(a,point+1,high); } }

值得注意的是，定义的快速排序函数Quick(a[],low,high)具有三个参数，待排列的数组记作a[]，低坐标记作low，高坐标记作high，最关键的是需要定义一个partion()函数，该函数用于返回一次分割序列过程最后关键字的最终位置,该变量记作Point（通过该操作可以将原有序列依据关键字分为两个序列），依靠关键字的最终位置（该位置在序列中对应的数字的值必是原有序列的关键字），可以将两个新的子序列继续进行快速排序。在这种情形下，原有序列为{low,low+1,.....,high-1,high}，分割为两个新子序列为{low,low+1,...point-1}与{point+1,point+2,....,high-1,high}。

继续定义partion()函数，返回关键字的最终位置，主要思路与上文快速排序法的书写思路完全相同，利用while循环，在低坐标low小于高坐标high时进行循环。定义一个变量取为key，用于记录每个序列的关键字，key赋值为a[low].

先将high坐标向下递减，直到a[high]小于关键字key时，将a[high]的值与a[low]的值进行交换，同样地，再将low坐标向上递增，使得当a[low]的值大于关键字key时，a[high]a[low]的值交换。最后，当low的值等于high值时，结束循环，返回最后的high值。代码如下：
void swap(int a[],int low,int high) { int temp=a[low]; a[low]=a[high];
a[high]=temp; } //交换函数 int partion(int a[],int low,int high) { int key=a[low];
while(low<high) { while(low<high&&a[high]>=key) { high--; } swap(a,low,high);
while(low<high&&a[low]<=key) { low++; } swap(a,low,high); } return high; }
快速排序算法的优化

通常在快速排序算法的过程中，我们将序列中位置为1的元素定义为序列的关键字，但如果关键字并不是整个序列中大小中间的元素，则第一次分割成的两个序列会大小不均，因此，将关键字可以重新进行选取。定义一个变量称为m，m取到高坐标与低坐标的中间值，然后将a[low]，a[m]，a[high]三者进行比较，确保a[low]的元素是最小的，与此同时a[high]最大，a[m]居中。
代码如下：
int m=low+(high-low)/2; if(a[low]>a[high]) { swap(a,low,high); }
if(a[m]>a[high]) { swap(a,m,high); } if(a[low]>a[m]) { swap(a,low,m); }

第二个优化就是通过观察上文的过程，发现一直都是元素5在与高坐标低坐标元素进行交换，元素5在最后的过程仅仅只需要被赋值到a[high]位置即可，而不需要过早地将5与a[high]a[low]交换。只需要a[high]a[low]之间互相赋值即可，即：高位元素小于关键值时将高位元素赋值给低位元素，而低位元素大于关键值时将低位元素赋给高位元素（关键字5存在key变量中，对结果不影响，只需最后赋值给高位）。代码如下：
int key=a[low]; while(low<high) { while(low<high&&a[high]>=key) { high--; }
a[low]=a[high]; while(low<high&&a[low]<=key) { low++; } a[high]=a[low]; }
a[high]=key;

热门工具换一换