排序算法——快速排序-创新互联

快排

​ 确定一组数据 ,即q数组

十余年的正定网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销的优势是能够根据用户设备显示端的尺寸不同,自动调整正定建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联公司从事“正定网站设计”,“正定网站推广”以来,每个客户项目都认真落实执行。

​ 左端点为了,右端点为r

​ (1)确定分界点

​ q[l] 或 q[ (l + r) / 2] 或 q[r] 或任意一个数 作为分界点,分界点数为x

​ (2)调整区间 (重点)

​ 使<= x的数放在左半边,使 >= x 的数放在右半边,两边的数可以乱序,暂时不用排序

​ (3)利用递归处理左右两端 ,进行排序

​ 暴力法

​ (1)开两个额外数组a,b

​ (2)扫描 l 到 r 的所有数,将<= x 的值放到a中,将 >= x的数放到b中

​ (3)将a,b排序后放到q数组中 a[ ] ->q[ ], b[ ]->q[ ];

​ (4)弊端:额外开辟空间,占用内存

​ 简便方法(指针)

​ 用两个指针i,j指向左端与右端的数

​ (1)判断指针i所指向的数是否小于x,符合条件时往右移一位,当大于等于x时指针i停下

​ (2)判断指针j所指向的数是否大于x,符合条件时往左移一位,当小于等于x时指针停下

​ (3)将i与j指针所指向的数交换,并再次重复1,2,3,直到i,j走到中间位置

​ (4)两边排序

模板
#include// scanf和printf也在iostream里面 ,但cstdio更快一些
#include#include  //使用swap函数
using namespace std;
const int N = 1000001;
int n;
int q[N];
void quick_sort(int q[ ], int l, int r)
{
    if (l >= r) return ; // 返回一个随机值,该return只是起到一个中止的作用,无需返回特定值
    int x = q[l], i = l - 1, j = r + 1,;
    //x = q[(l+r+1 )/2    一定不能取到边界上,上面的x只是举例
    // x = q[l + r >>1]会更快,以后再理解
    while (i< j)
    {
        do {
            i++;
        } while (q[i]< x);
        do {
            j--;
        } while (q[j] >x);
            if (i< j) swap(q[i],q[j]);
    }
    if(l< j )quick_sort(q, l, j);//左半部分
    if(i< r)quick_sort(q, j + 1, r);//右半部分
}
int main()
{
    scanf("%d", &n);
    for (int i = 0;i< n;++i) scanf("%d", &q[i]);
    quick_sort(q, 0, n-1);
    for (int i = 0;i< n;++i) printf("%d ", q[i]);
    return 0;
}

END


自学编程的小伙伴们不容易,在学习编程的路上会遇到很多瓶颈,甚至会感到迷茫,为此我给大家整理了一些资源福利,都放在下方啦,还可以和群里的小伙伴们一起来学习交流嗷~

C/C++编程学习基地icon-default.png?t=M85Bhttps://jq.qq.com/?_wv=1027&k=9Hqqlikh

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前文章:排序算法——快速排序-创新互联
网址分享:http://myzitong.com/article/dspcse.html