快速排序
用于排序的最佳的实用选择,因其平均性能很好,期望运行时间O(nlog2^n),最坏情况运行时间为O(n^2).
1、快速排序
和合并排序一样,采取分治模式:
(1)分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A[q],而A[q+1..r]大于A[q],q在此划分过程中进行计算。
(2)解决:递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序
(3)合并:两个子数组都是原地排序的,因此合并不需要操作,整个数组就已经排好序
伪代码:
QUICKSORT(A,p,r)
if p<r then
q<—PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
最初调用QUICKSORT(A,1,A.length).
其中子程序PARTITION(A,p,r)代码如下,实现对子数组A[p..r]进行重排:
//对数组A[p,...,r]进行重排,使得A[p..q-1]中的每个元素都小于等于A[q],而A[q+1..r]大于A[q]
int partition(int a[],int p,int r){
int key=a[r];
int index=p-1;
int temp=0;
for(int i=p;i<=r-1;i++){
if(a[i]>key){
index++;
temp=a[i];
a[i]=a[index];
a[index]=temp;
}
}
temp=a[index+1];
a[index+1]=a[r];
a[r]=temp;
return index+1;
}
将A[r]=key作为参照数来进行对比,最后的结果是A[p..q-1]中的每个元素都小于等于key,而A[q+1..r]大于key,而A[q]最后和A[r]交换,并返回q。此子程序的运行时间为O(n),其中n=r-p+1.
2、快速排序的性能
快速排序的运行时间和划分是否对称有关,而后者又和选择了哪一个元素来进行划分比较有关。如果划分对称,渐近意义上,与合并算法(nlog2^n)一样快,不对称时,渐近意义上,和插入算法(n^2)一样慢。
(1)最坏情况
最坏划分是划分过程中产生的两个区域分别包含了n-1个元素和1个0元素。假设每次递归调用都出现了这种划分,划分的时间代价是O(n),递归树有n层,则算法的运行时间为O(n^2).递归表达式T(n)=T(n-1)+O(n).
(2)最好情况
最平衡的划分,两个子数组的大小都不可能大于n/2,递归式T(n)<=2T(n/2)+O(n),解为O(nlog2^n).由于每一层递归的划分都是两边对称的,因此,从渐进意义上,算法运行就更快了。
(3)平衡划分
平均情况和最佳运行时间很接近
任何一种按常数比例进行的划分都会产生深度为O(log2^n)的递归树,其中每一层的代价为O(n),因而,当按照常数比例划分时,总运行时间是O(nlog2^n).
3、快速排序的随机化版本
加入随机化部分,以便对于所有的输入,它均能获得较好的平均情况性能。随机化算法使得输入数组不相关,使最坏情况发生的可能性变小。
伪代码
RANDOMIZED-PARTITION(A,p,r)
i<—Random(p,r)
exchange A[r]<->A[i]
return PARTITION(A,p,r)
4、Hoare划分
将数组第一个元素作为对比元素,即主元,用两个指针分别从数组的首尾进行遍历,首指针找到第一个比主元大的元素,尾指针找到第一个比主元小(包括等于)的元素,将两个元素交换,循环进行此过程指导首尾指针相遇,最后的尾指针(包括尾指针)之前是比主元小(等于)的元素,尾指针后是比主元素大的元素,将尾指针位置的元素和主元素交换,并返回尾指针位置。
伪代码:
HOARE-PARTITION(A,p,r)
x<—A[p]
i<—p-1
j<—r+1
while TRUE
do repeat j<—j-1
until A[j]<=x
repeat i<—i+1
until A[i]>x
if i<j
then exchange A[i]<—>A[j]
else
A[p]<—>A[j]
return j
c代码
int hoare_partition(int a[],int p,int r){
int temp=0;
int key=a[p];
int i=p-1;
int j=r+1;
while(true){
do{
j--;
}while(a[j]>key);
do{
i++;
}while(a[i]<=key);
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else{
temp=a[p];
a[p]=a[j];
a[j]=temp;
return j;
}
}
}
此划分算法的运行时间为O(n),n=r-p+1.
分享到:
相关推荐
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
算法分析与设计里面的快速排序 算法分析与设计里面的快速排序算法分析与设计里面的快速排序
快速排序快速排序快速排序快速排序快速排序快速排序
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
舍伍德——快速排序源码报告和算法分析 有需要的朋友看下
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
算法设计分析课本中,根据快速排序算法而得来的程序。希望对大家有用~~
快速排序 实验数据:input.txt(共100个数据) ——要求按从小到大进行排序 将排好序的数据输出到output.txt文件中
1)不做随机化处理的递归实现; 2)采用随机化处理的递归实现; 3)用while循环消除尾递归; 4)用栈模拟递归,并证明所需的栈空间为O(logn); 5) 够小时改用插入排序
算法的学习,分治
快速排序 快排标准代码 快速排序标准代码 快速排序分析
二分搜索算法、快速排序,算法分析与设计(完整的代码,结合例题详细解析) 全套资源,求抱走!!! 1、给定数组a[0 : 8]={1, 8, 12, 15, 16, 21, 30, 35, 39}。采用二分搜索算法完成下述任务: 1)查找是否有元素30...
呵呵,rt,对快速排序的性能进行理论分析
在输入序列个数、排序情况不同的情况下对确定性快速排序与随机化快速排序的比较。比较他们的运行时间,验证是否与理论相符。
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
这是我自己写的java,快速排序法。以前在网上找了很久,都没有合适的,就自己写了个,希望大家有需要的能用到。呵呵呵
冒泡,快速排序算法比较试分别实现冒泡排序和非递归形式的快速排序算法,并通过随机数据比较两种排序算法中关键字的比较次数和移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少...
冒泡排序、快速排序和二分法查找的分析 Java