快速排序算法的优化

开篇：润墨网以专业的文秘视角，为您筛选了一篇快速排序算法的优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要快速排序算法是计算机内部排序程序设计中的一种重要操作，在现实生活中有广泛应用。本文主要对在排序过程中记录移动次数进行探讨优化，希望在计算机的学科发展大潮中贡献绵薄力量。

【关键词】快速排序 记录移动

快速排序是对起泡排序的一种改进，在时间、空间复杂度同数量级的排序方法中，其平均性能最优。其基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1 快速排序算法实现

1.1 一趟快速排序算法实现

假设待排序的序列为{L.r[s],L.r[s+1],…,L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴(或支点)(pivot)，然后按下述原则重新排列其余记录: 将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可以将该”枢轴”记录最后所落得位置i作分界线，将序列{L.r[s],…,L.r[t]}分割成两个子序列{L.r[s],L.r[s+1],…,L.r[i-1]}和{L.r[i+1],L.r[i+2],…,L.r[t]}。这个过程称做一趟快速排序(或一次划分)。

一趟快速排序的具体做法是: 附设两个指针low和high，他们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。其算法如下:

int Partition(SqList &L, int low, int high){

pivotkey=L.r[low].key;

while(low

while(low=pivotkey)--high;

L.r[low]L.r[high];

while(low

L.r[low]L.r[high];

}

return low;

}

1.2 递归形式的快速排序算法

通过对一次划分所得的两个子序列递归排序，得到原序列的排序

算法实现如下：

void QSort(SqList &L，intlow，inthigh){

if(low

pivotloc=Partition(L,low,high);

QSort(L,low,pivotloc-1);

QSort(L,pivotloc+1,high);

}

}

2 对一趟排序算法的优化

由上述算法知，在进行一次记录交换时，需要3次记录移动(赋值)的操作。而在实际上，在排序过程中对枢轴记录的赋值是多余的。因为在排序过程中，当low>=high时确定枢轴位置即可。因此可以将枢轴记录暂存，当一趟排序结束时才将枢轴记录移动到正确位置。此外，可以将指针的单向移动改为双向移动，即: low指针从开始位置向后搜索，直到遇到第一个大于pivotkey的记录；high指针从开始位置向前搜索，直到遇到第一个小于pivotkey的记录，然后交换low和high指针对应的记录。

算法实现如下:

int Partition(SqList &L, int low, int high){

l=low;

high=high+1;

while(low

do{

low++;

}while(L.r[low].key

do{

high--;

}while(L.r[high].key>pivotkey)

swap(L.r[low],L.r[high]); //交换两条记录

}

swap(L.r[low],L.r[high]);//当low>=high时 撤销最后一次交换

swap(L.r[l],L.r[high]);

returnhigh;

}

对比可知: 优化后的一趟排序算法不必对枢轴重复赋值

3 过程事例

如图1图2所示。

4 结束语

本文从快速排序算法的记录移动过程入手，针对一趟快速排序的枢轴移动赋值进行优化，并且将指针的单向移动改为双向移动，使得排序过程更加清楚。

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版).

[2]Anany Levitin(美).算法设计与分析设计基础(第二版).

作者单位

中南大学湖南省长沙市410083