快速排序是对冒泡排序的一种改进,它使用分治的思想,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录循环进行排序,以达到整个序列有序的状态。
快速排序是C.A.R Hoare在1962年提出的,显然,它是一种分治算法,并且是原地排序算法。快速排序可分为四个步骤:
1)选择杠杆点:在待排序的序列中按照某种方式选取一个元素作为划分的杠杆点。
2)分解:以杠杆点为界,将序列分为两个子序列,其中一个子序列里的所有元素小于等于杠杆点,另一个子序列里的所有元素大于杠杆点。
3)治之:递归对两个子序列进行快速排序。
4)合并:将排好序的两个子序列合并成大序列。
快速排序的时间成本取决于分解这一步,分解的好坏将对整个算法的效率产生决定性影响。但分解的好坏取决于杠杆点的选择。下面是标准的序列分解算法:
PARTITION(A, m, n)//A[m...n]为一个序列
x<--A[m]
//A[m]为我们选择的杠杆点
i<--m
for
j<--m+1to n do
if
A[j]<=x then
i<--i+1
Exchange A[i] <--> A[j]
Exchange A[m] <--> A[i]
return
i;
上述算法将子序列A[m…n]以A[m]为界分解为两个子序列:A[m…i-1]和A[i+1…n]。在每一次for循环中,A[m…i]里面的元素都小于等于杠杆点x,A[i+1…j]里面的元素都大于杠杆点x,而A[j+1…n]里面的元素是尚未分解的子序列里的元素。
有了分解算法之后,整个快速排序算法如下:
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, n)。
快速排序最坏情况下时间复杂度是Θ(n2),最好情况下和平均情况下都是Θ(nlogn)。
快速排序分解出的子序列是否为空取决于杠杆点与其他元素的相对关系,因此,在使用快速排序的时候,要想保证算法的时间复杂度不被输入序列有意地操控,我们在选择杠杆点的时候就不能是确定性的。如果每次都是随机选择一个元素作为杠杆点,则无论对手进行多少次实验也不能得出任何肯定的结论,自然也就不能有针对性的进行输入数据次序的安排来使我们快排算法总是处于最坏时间复杂度下。
随机化快速排序算法模板如下:
/*
函数名:quick_sort
功能:快速排序辅助过程
*/
template <typename
T>
void quick_sort (T data[],int
frist,int last)
{
int
lower=frist+1;
int
upper=last;
int
t=rand()%(last-frist)+frist;
std::swap(data[frist], data[t]);
T& bound=data[frist];
while
(lower<=upper)
{
while
(data[lower]<bound)
{
++lower;
}
while
(bound<data[upper])
{
--upper;
}
if
(lower<upper)
{
std::swap(data[lower], data[upper]);
++lower;
--upper;
}
else
++lower;
}
std::swap(data[upper], data[frist]);
if
(frist<upper-1)
quick_sort(data, frist, upper-1);
if
(upper+1<last)
quick_sort(data, upper+1, last);
}
/*
函数名:QuickSort
功能:快速排序
模板参数说明:T必须支持小于操作
参数说明:data待排序数组, size待排序数组大小
前置条件:data!=NULL, size>0
后置条件:data按排列
用法:
#include <algorithm>
#include <stdlib.h>
#include <time.h>
int arr[]={10,9,8,4,5,7,6,3,1,4};
QuickSort(arr, 10);
*/
template <typename
T>
void QuickSort (T data[],int
size)
{
int
i, max;
if
(size<2)
return;
for
(i=1, max=0; i<size; ++i)
{
if
(data[max]<data[i])
max=i;
}
std::swap(data[size-1], data[max]);
srand(time(0));
quick_sort(data, 0, size-2);
}
/*
函数名:quick_sort
功能:快速排序辅助过程
*/
template <typename
T, typename Func>
void quick_sort (T data[],int
frist,int last, Func& f)
{
int
lower=frist+1;
int
upper=last;
int
t=rand()%(last-frist)+frist;
std::swap(data[frist], data[t]);
T& bound=data[frist];
while
(lower<=upper)
{
while
(f(data[lower],bound))
++lower;
while
(f(bound,data[upper]))
--upper;
if
(lower<upper)
{
std::swap(data[lower], data[upper]);
++lower;
--upper;
}
else
++lower;
}
std::swap(data[upper], data[frist]);
if
(frist<upper-1)
quick_sort(data, frist, upper-1, f);
if
(upper+1<last)
quick_sort(data, upper+1, last, f);
}
/*
函数名:QuickSort
功能:快速排序
模板参数说明:T元素类型,Func函数对象或指针
参数说明:data待排序数组, size待排序数组大小,函数对象或指针
前置条件:data!=NULL, size>0
后置条件:data按排列
用法:
#include <algorithm>
#include <stdlib.h>
#include <time.h>
bool cmp(int a, int b)
{ return a<b; }
int arr[]={10,9,8,4,5,7,6,3,1,4};
QuickSort(arr, 10, cmp);
*/
template <typename
T, typename Func>
void QuickSort (T data[],int
size, Func f)
{
int
i, max;
if
(size<2)
return;
for
(i=1, max=0; i<size; ++i)
{
if
(f(data[max],data[i]))
max=i;
}
std::swap(data[size-1], data[max]);
srand(time(0));
quick_sort(data, 0, size-2, f);
}
分享到:
相关推荐
(2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个...
实现对数组的普通快速排序和随机快速排序,并统计算法运行时间。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示...
算法导论及算法设计与分析(高级版)的程序
自己编写的基于java的快速排序和归并算法
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...
采用速度快的快速排序节省时间,数据结构中快速排序需要时间相对时很短的。
1)不做随机化处理的递归实现; 2)采用随机化处理的递归实现; 3)用while循环消除尾递归; 4)用栈模拟递归,并证明所需的栈空间为O(logn); 5) 够小时改用插入排序
1、掌握快速排序随机算法的设计思想与方法。 2、熟练使用高级编程语言实现不同的快速排序算法。 3、利用实验测试给出不同快速排序算法的性能以理解其优缺点。 快速排序是算法导论中的经典算法。在本实验中,给定一...
文章介绍了基本的快速排序算法及三种枢轴元素的选取方法,全面深入地分析了快速排序算法最坏情况下的时间复杂度、平均情况下的时间复杂度、随机情况下的时间复杂度。并对快速排序算法和堆排序算法进行了比较,理论和...
二分搜索算法、快速排序,算法分析与设计(完整的代码,结合例题详细解析) 全套资源,求抱走!...3)快速排序算法的性能与划分是否对称有关,设计随机化的快速排序算法解决划分对称性问题,将算法编程实现。
快速排序的三种写法及随机主元快速排序时间复杂度是nlgn,
在输入序列个数、排序情况不同的情况下对确定性快速排序与随机化快速排序的比较。比较他们的运行时间,验证是否与理论相符。
实现了快速排序,输入为可变大小的随机数组,并可以统计排序的时间
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
参照算法导论,代码实现并加入了计时。算法实验必备,纯C代码,方便参考.学习交流,共同进步