论文_快速排序的再认识

快速排序的再认识

江西省婺源中学 汪有万 333200

关键词：交换、排序、数组

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。最简单的是使用冒泡排序，但其时间复杂度为O（n2）。

算法复杂度分为时间复杂度和空间复杂度。时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。

在全国青少年信息学（计算机）奥林匹克分区联赛(NOIP)中，由于规定内存使用不超过32M，运行时间不超过1秒，否则以0分论处。这样的要求，对参赛选手提出了较高的要求。特别对于大数据量，即要考虑时间复杂度，也要考虑空间复杂度，否则，要得满分，那是天方夜谈。

一般来说，有n个数待排序，如果使用冒泡法进行排序，其时间复杂度为O(n-1+n-2+„„+1)=O((n-1)*n/2)=O(n2)，当n>=10000时，其时间复杂度为O(108)，即使用每秒运行亿次的计算机才能在1秒内完成排序。为此，做过测试，在“AMD Athlon™ TT X3 425 Processor 2.71MHz,2.00GB的内存”微机上，n=100000时，完成冒泡排序要运行28秒左右！

在此种情况下就要考虑使用快速排序了，否则在复赛时很有可能超时被判0分。但是普及组参赛选手对快速排序的理解有很大的难度，经常记不住快速排序的代码。将快速排序算法与高精度算法、背包问题算法等作为必须掌握的基础知识，是取得好成绩所必须掌握的。

快速排序是目前已知的效率最高的排序。它的特点是：越乱排序效率越高，交换数据最少，移动数据的距离最大。一趟快速排序之后，就会出现“左<关键字<=右”的情形，由于左<右，左右之间就不用进行比较，从而大大提高排序效率，它的期望时间复杂度可达O(n log n)。对于n=100000而言，使用冒泡排序，其时间复杂度为O(1010)，使用快速排序，其时间复杂度可为O(500000)，真是天壤之别。

下面以一个例子来说明快速排序的过程。

一

婺源中学NOIP复赛资料

对{5，28，16，29，27，23，3，20，1，8，32，26，33，11，12}进行快速排序。

① 取第一个数5为关键字，即key=5 。

②从左到右找>key的数（=key就停下），同时从右到左找③交换这两数，即是：

{1，28，16，29，27，23，3，20，5，8，32，26，33，11，12}

④不等于关键字的指针移动（左指针右移或右指针左移）或等于关键字的右指针左移。

左从第2个数向右，右从第9个数向左重复②③，得： {1，5，16，29，27，23，3，20，28，8，32，26，33，11，12}

⑤不等于关键字的指针移动（左指针右移或右指针左移）或等于关键字的右指针左移。

左从第2个数向右，右从第8个数向左重复②③，得： {1，3，16，29，27，23，5，20，28，8，32，26，33，11，12}

⑥不等于关键字的指针移动（左指针右移或右指针左移）或等于关键字的右指针左移。

左从第3个数向右，右从第7个数向左重复②③，得： {1，3，5，29，27，23，16，20，28，8，32，26，33，11，12}

⑦不等于关键字的指针移动（左指针右移或右指针左移）或等于关键字的右指针左移。

左从第3个数向右，右从第6个数向左重复②③，得： 左右指针重叠在第3个数5上，一趟快速排序完成。

从结果可以看出，以关键字为准分为左右两个区域，左<关键字<=右。另外，还以看出，由于关键字的位置忽左忽右，所以快速排序是一种不稳定的排序。

根据以上思路可写出快速排序的Pascal代码，默认是对数组a进行从小到大排序。

//自定义过程——用于2个变量的值进行交换 procedure swap(var x,y:longint);

二

婺源中学NOIP复赛资料

var c:longint; begin

c:=x; x:=y; y:=c; end;

//自定义过程——快速排序，对a[i]进行从小到大排序 procedure qsort(L,R:longint); var key,i,j:longint; begin

if L>=R then exit; i:=L; j:=R; key:=a[i];

while ia[i] do inc(i); //左<关键字，则左指针右移 while keya[i] then inc(i); //关键字>左，则左指针右移 if keyif a[i]=a[j] then dec(j); //左右相等时（即都等于关键字），右指针左移 end; qsort(L,i-1); qsort(i+1,R); end;

如果a [i]与b[i]有着一一对应的关系，对a[i]进行快速排序，而b[i]同步变化，只需在交换数据的位置，增加语句：swap(b[i],b[j])即可。在2010年全国青少年信息学（计算机）奥林匹克分区联赛普及组第3题、第4题就使用到了快速排序。

三