快速排序(QuickSort)

快速排序(QuickSort)也是一种排序算法,对包含n个数组的输入数组,最坏情况运行时间为O(n^2)。虽然这个最坏情况运行时间比较差,但是快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,期望的运行时间为O(nlgn),且O(nlgn)中隐含的常数因子很小,另外它还能够进行就地排序在虚拟环境中也能很好的工作。

一、快速排序原理

快速排序也和合并排序一样,基于分治法,分为分解、解决、合并三个步骤;

分解:数组array[low...high]被分为两个(可能空)子数组array[low...temp-1]和array[temp+1...high],使得array[low...temp-1]中的每一个元素都小于等于array[temp],而array[temp+1...high]中的每一个元素都大于array[temp],下标temp也是在这个过程中被计算出来;

解决:通过递归的调用快速排序,对子数组array[low...temp-1],array[temp+1...high]进行排序;

合并:因为两个子数组是就地排序的,将他们的合并不需要操作,整个数组array[low...high]是已经排好序的。

二、快速排序实现

[cpp]

#include <iostream>

#include <ctime>

#include <cstdlib>

#define N 10

using namespace std;

//快速排序的递归算法

void quickSort(int * array , int low , int high);

//求分割点

int partition(int * array , int low , int high);

//交换两个变量的值

void exchange(int &a,int &b);

int main()

{

//声明一个待排序数组

int array[N];

//设置随机化种子,避免每次产生相同的随机数

srand(time(0));

for(int i=0 ; i<N ; i++)

{

array[i] = rand()%101;//数组赋值使用随机函数产生1-100之间的随机数

}

cout<<"排序前:"<<endl;

for(int j=0;j<N;j++)

{

cout<<array[j]<<" ";

}

cout<<endl<<"排序后:"<<endl;

//调用快速排序函数对该数组进行排序

quickSort(array,0,N-1);

for(int k=0;k<N;k++)

{

cout<<array[k]<<" ";

}

cout<<endl;

return 0;

}//main

void quickSort(int * array , int low , int high)

{

if(low < high)

{

int temp = partition(array , low , high);

quickSort(array , low , temp-1);

quickSort(array , temp+1 , high);

}

}

int partition(int * array , int low , int high)

{

int i = low - 1;

int x = array[high];

for(int j=low ; j<high ; j++)

{

if(array[j] <= x)//在array[i]左边都是小于x即array[high]的数,右边均是大于它的数

{

i += 1;

exchange(array[i],array[j]);

}

}

exchange(array[i+1],array[high]);

return i+1;//所以循环完毕后,i+1就是该数组的分割点

}

void exchange(int &a,int &b)

{ www.2cto.com

int temp = a;

a = b;

b = temp;

}

运行结果:

快速排序(QuickSort)

三、快速排序性能分析

快速排序的运行时间与划分是否对称有关,而后者又与选择了哪一个元素进行划分有关。如果划分是对称的,那么本算法在渐近意义上与合并排序一样快,如果划分是不对称的那么本算法在渐进意义上与插入排序一样慢。下面分别讨论快速排序的最坏情况划分、最家情况划分、平衡的划分。

最坏情况划分:快速排序的最坏情况划分行为发生在划分过程中产生的两个区域分别包含n-1个元素和0个元素的时候。假设算法每次递归调用都出现了这种不对称划分,划分的时间代价为O(n),因为对一个大小为0的数组进行递归调用后,返回了T(n)=O(1),故算法的运行时间可递归的表示为:

T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)

从直观上来看,如果将每一层递归的代价加起来,就可以得到一个算术级数(等式(array,2)其和值的量极为O(n^2))利用代换法可以比较直接的证明递归式 T(n) = T(n-1) + O(n)的解为 T(n) = O(n^2)。

因此如果在算法的每一层递归上,划分都是最大程度不对称的,那么算法的运行时间为O(n^2),亦即快速排序算法的最坏情况运行时间不如插入排序的好。此外当输入数组完全排好序时,快速排序的运行时间是O(n^2),而插入排序的运行时间为O(n)。

最佳情况划分:在Partition可能做的最平衡划分中,得到的两个子问题的大小都不可能大于[n/2],因为若其中一个子问题的大小为[n/2],则另外一个子问题的大小必然为[n/2]-1。在这种情况下,快速排序的运行速度要快得多,这时表达其运行时间的递归式为:

T(n) <= 2T(n/2) + O(n)

解该递归式可得T(n) = O(nlgn)。由于在每一层递归划分的两边都是对称的,因此从渐进意义上来看,算法运行的就更快了。

平衡的划分: 快速排序的平均情况运行时间与其最佳情况运行时间很接近,而不是非常接近与其最坏情况运行时间(证明原因详细参考《算法导论》原书第二版P88),因为任何一种按常数比例进行划分都会产生深度为O(lgn)的递归树,其中每一层的代价都是O(n),因而每当按照常数比例进行划分时,总的运行时间都是O(nlgn)。

分类:默认分类 时间:2012-01-08 人气:2
本文关键词:
分享到:

相关文章

  • POJ 2299 Ultra-QuickSort (归并排序) 2012-01-19

    Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 43446 Accepted: 15822 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping tw

  • UVA 10810 - Ultra-QuickSort(树状数组+离散化) 2012-07-04

    Problem B: Ultra-QuickSort In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of ndistinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For t

  • poj - 2299 - Ultra-QuickSort(树状数组) 2012-10-17

    题意:求长度为n(n 题目链接:http://poj.org/problem?id=2299 ——>>设x[i]表示数i已经出现的次数,从后往前扫描,对于每个数k,那么k产生的逆序对数为x[0] + x[1] + ... + x[k-1],于是可以用树状数组了。 ——>>由于元素范围可到999999999,所以应做离散化操作。 ——>>如果所有数逆序出现,那么逆序对数最多为n(n-1)/2,代入n = 500000可知已超32位整数范围,应用64位整数。 第一

  • POJ训练计划2299_Ultra-QuickSort(线段树/单点更新) 2014-02-28

    解题报告 题意: 求逆序数。 思路: 线段树离散化处理。 #include #include #include #include #define LL long long using namespace std; LL sum[2001000],num[501000],_hash[501000]; void push_up(int rt) { sum[rt]=sum[rt*2]+sum[rt*2+1]; } void update(int rt,int l,int r,int p,LL v) {

  • poj 2299 Ultra-QuickSort 2014-05-25

    树状数组 样例过了就A了 YA各种爽 #include #include #include using namespace std; #define maxx 500050 int bit[maxx],a[maxx]; int n; struct node { int x,y; }pos[maxx]; bool cmp(node aa,node bb) { return aa.x0){ s+=bit[i]; i=i&(i-1); } return s; } void add(int i,

  • 快速排序的深入详解以及java实现 2012-03-10

    快速排序作为一种高效的排序算法被广泛应用,SUN的JDK中的Arrays.sort 方法用的就是快排。 快排采用了经典的分治思想(divide and conquer): Divide:选取一个基元X(一般选取数组第一个元素),通过某种分区操作(partitioning)将数组划分为两个部分:左半部分小于等于X,右半部分大于等于X。 Conquer: 左右两个子数组递归地调用Divide过程。 Combine:快排作为就地排序算法(in place sort),不需要任何合并操作 可以看出快排的

  • POJ 3687-Labeling Balls(逆序拓扑排序) 2012-03-25

    Labeling Balls Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11256 Accepted: 3230 Description Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that: No two balls share the

  • poj 2907 Collecting Beepers 邮递员问题暴力解法 2012-05-25

    题意: 给起点和n个点,求从起点出发经过这n个点每个点至少一次再回到起点的最短路。 分析: 类似邮递员问题,直接用STL枚举访问顺序暴力解决。 代码: //poj 2907 //sep9 #include #include using namespace std; int x[16],y[16]; int d[16][16]; int a[16]; int n; int main() { int cases; scanf("%d",&cases); while(cases--){ sca

  • 内部排序实现(数据结构) 2012-06-01

    以下源码全部经过测试,有些地方可能不是最优,仅是练习。如果错误或更好的方法欢迎大家指出。以下仅供参考: 说明:为了测试的方便,在每个排序算法前都进行了一次初始化-重新分配内存,以防止影响后面的测试。cygwin下G++测试通过 #include #include #include #include #include #include #include /* *根据内部使用的原则:插入排序,选择排序,交换排序, *归并排序,基数排序 * */ /* * 插入排序 */ //常规插入 void In

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.051 (s). 10 q(s)