快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤:

1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使a[p:q-1]中的任何元素都小于a[q],a[q+1:r]中的任何元素都大于a[q]

2 递归求解:递归的对a[p:q-1],a[q+1:r]再进行排序

3 合并:就地排序,不需要执行任何计算,便完成排序

template <class Type>
void QuikSort(Type a[],int p,int r){
    if(p<r)
    {
        int q = Partition(a,p,r);
        QuikSort(a,p,q-1);
        QuikSort(a,q+1,r);
    }
}

template <class Type>
void Oartition(Type a[],int p,int r){
    int i=p,j=r+1;
    Type x = a[p];
    while(true){
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j)
            break;
        Swap(a[i],a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

40760
来自专栏Python小屋

Python中lambda表达式的常见用法

非常抱歉,昨天发的代码中有一处小错误,已通过留言的方式进行了纠正,详情请见【详解Python列表推导式】 lambda表达式常用来声明匿名函数,即没有函数名字的...

37090
来自专栏GreenLeaves

Oracle dbms_random随机函数包

dbms_random是oracle提供的一个随机函数包,以下是它的一些常用的功能: 1、dbms_random.value 作用:生成一个大于等于0,大于等于...

21950
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

29850
来自专栏desperate633

LintCode A+B问题题目分析代码

给出两个整数a和b, 求他们的和, 但不能使用+等数学运算符。 ** 注意事项 ** ** 你不需要从输入流读入数据,只需要根据aplusb的两个参数a和b...

7820
来自专栏用户2442861的专栏

NumPy简明教程(二、数组1)

http://blog.csdn.net/sunny2038/article/details/9002531

10710
来自专栏ACM算法日常

前m大的数(堆)- HDU 1280

还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,...

9820
来自专栏数据结构与算法

1341 与3和5无关的数

1341 与3和5无关的数 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description ...

28840
来自专栏老秦求学

快速排序

快速排序: 设要排序的数组是A[0]……A[N-1], 思想:分治法(递归实现)关键是求出基准记录所在的位置(由于两个数之间进行交换,导致原来基准的位置发生改变...

29360
来自专栏猿人谷

成员以其在类中声明的顺序构造

分析以下代码的输出: #include<iostream> using namespace std; class A { public: A(int j):...

20560

扫码关注云+社区

领取腾讯云代金券