应用研究
快速排序性能分析及实现
于胜志
(同济大学上海201804)
数事执本开与或用
摘要:排序,就是使一串记录,按照其中的某个或某要关键字的大小,逆增或递减的排列起来的操作。排序的算法有很多种,基本常见排序算法可分为稳定的排序算法和不稳定的排序算法。本文主要介绍了不稳定的快速排序算法，先给出快造排序算法的概述，并具体分析了其时间复杂度的问题。之后电给出了一种快速排序算法的]AVA语实现。最后,经过测试程序验证排序算法的有效性。
关键词：快造排序JAVA算法时间复杂度
中图分类号：TP312 1概述
文献标识码：A
快速排序是由C，A.R.Hoare在1962年提出，它是对日泡排序的一种改进。它采用了一种分治的策略，其基本思想是：首先，先从数列中取出一个数作为基准数。其次，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。最后，再对左右区间重复第二步，直到各区间只有一个数为止。整个排序过程可以递归进
行，使得整个数据变成有序序列。 2算法分析
为了分析快速排序的性能我们引人如下概念。 2.1时间频度
一个算法中的语句执行次数称为语句频度或时间频度，记为 T(n）。一个算法执行所耗费的时间，理论上没法计算，所以我们只计算算法中语句的执行次数。
2.2时间复杂度
时间频度几称为问题的规模，一般情况下，算法中基本操作重复执行的次数是问题规模n的函数，记为T(n)。若存在函数f(n)，当 n→+，使得T(n)/(n)的极限为不等于零的常数,则称/(n)是的 T(n)同数量级函数。记作T(n)=O(f(n)，称O(f(n)为算法的渐进时间复杂度，简称时间复杂度。
快速排序在最坏的情况下时间复杂度为O(")。假设每次将长度为n的数列分为两个n/2的子数列再对n/2分为两个n/4的子数列，依次类推。假设将这个数列排列的时间记为T(n)，则可得
T(n) ≤cn +2T(n / 2)
≤ c+ 2(cn / 2 + 27(n / 4) ≤ 2c + 4T(n / 4) .--
≤ cn log, n + nT(l) = O(n log, n)
如下引理1证明了快速排序函数(QuickSort)的平均时闻为 O(nlog: n)。
引理1"：令T(n)为QuickSort函数对一个含有n条记录的表进行排序所需时间的期望值，则存在一个常数k，使得
Ta(n)≤knlog,n对所有n≥2成立。 3算法实现
本节12)主要用JAVA语言实现快速排序类，并给出简要注释收移日期：2015-12-10
文章编号:1007-9416(2016)02-0080-01
classQuickSort//定义一个快速排序类 public int datal],
public void sort(int low,int high) if(low int middle = medium(data,low,high);
sort(low, middle1), sort(middle+1, high);
/递归寻找基数
private int medium(int sortArrayl,int low,int high)(//返回调整后基准数的位置
//取第一个数作为基数
int temp = sortArray[low], while(low while(low=temp) high—-
sortArray[low] = sortArray[high],
while(low sortArray[high] = sortArray[low]
】//退出时，low等于high，将temp填到sortArray[low]中
sortArray[low] = tem; returnlow
Dublicvoiddisplay(O)//依次打印数组元素 for(int i: data)
System.out.print(i+""), System.out.println("n"),
4结语
本文主要分析了快速排序算法的时间复杂度，并给出了算法平均时间的大致推导过程。通过编写测试函数，可以取得预期效果。表
明本文快排序算法真实有效。参考文献
[1JE1lis Horowitz,Sartaj Sahni,Dinesh Mehta.数据结构基础[M]. 张力.等译.北京：清华大学出版社,2009.
[2]严蔚敏.吴伟民.数据结构[M].北京：清华大学出版社,2008.
作者简介：于胜志(1986一),男，汉族，安微蒙城人,工学硕士，单位：同济大学电子信息与工程学院，研究方向：鲁棒观测器，滑模控制器等。 80