前言

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

         内部排序主要分为四大类,第一类称作插入排序,即将一个单独的元素插入到一个已经排列好的有序序列中,包括了
直接插入排序以及折半插入排序、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;