快速排序的基本思想是:对于任意一个给定序列中的某个元素R[s],经过一趟排序后,将原序列分割成两个子序列(R[0] - R[s-1])和(R[s+1] - R[n-1])。使前一个序列中的值都不大于R[s]的值,后一个序列的元素的值都不小于R[s]。称R[s]为分割元素,前一个序列为其低端序列,后一个序列为其高端序列。然后对低端序列和高端序列分别进行快速排序,直到最后序列为空或者只有一个子元素,最后得到有效序列。
对于快速排序来说,最坏情况是初始序列有序时,时间复杂度为O(n^2)。其平均复杂度为O(n * log 2 n)。快速排序是目前最快的排序方法,偏爱基本无序的序列。
简单实现:
void swap(int &a,int &b){
int k = b;
b = a;
a = k;
}
void QSort(int *p,int plength){
//总是选取序列的第一个元素做为分割元素
int i,j,k;
i = 1;
j = plength - 1;
do{
while(p[i] < p[0] && i < plength)
i ++;
while(p[j] > p[0] && j > -1)
j --;
if( i < j)
swap(p[i],p[j]);
}while( i < j);
swap(p[0],p[j]);
if(j > 0)
QSort(p,j);
if( plength-j -1 > 0)
QSort(&p[j+1],plength -j-1);
}
int main()
{
int A[7] = {48,36,68,72,12,48,02};
QSort(A,7);
return 0;
}
分享到:
相关推荐
舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
我最喜欢的排序算法 快速排序和归并排序.doc
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
【排序算法】快速排序(C语言)
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
c语言版本的数据结构的快速排序算法,适用于新手学习
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
快速排序算法C语言实现,快排序算法QuickSort.cpp
自己编写的基于java的快速排序和归并算法
自己写的用C来实现快速排序 包含.c文件的全部内容
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
详细解释了快速排序的java实现.里面有代码,还有注释说明
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
Python 算法 快速排序.py
Java 快速排序,目前来说效率很高的一种排序算法,好理解。