首页 > 编程语言 >AcWing算法基础课---第一讲基础算法---01排序

AcWing算法基础课---第一讲基础算法---01排序

时间:2022-08-22 11:00:24浏览次数:51  
标签:sort 01 int mid while --- 算法 排序

快速排序

步骤

  1. 确定分界点:q[l], q[(l+r)/2], q[r], 随机
  2. 调整区间
  3. 递归处理
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return; //递归结束条件
    
    int i = l - 1, j = r + 1, x = q[l + r >> 1]; //定义i, j指针, 确定分界点x(一般取中间值)
    while (i < j)
    {
        do i ++; while (q[i] < x); 
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]); //交换两值
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

步骤

  1. 确定分界点 mid
  2. 递归排序left, right
  3. 归并---合二为一
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1; //确定分界点
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] < q[j]) temp[k ++] = q[i ++];
        else temp[k ++] = q[j ++];
    }
    while (i <= mid) temp[k ++] = q[i ++];
    while (j <= r) temp[k ++] = q[j ++];
    
    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = temp[j]; 
}

标签:sort,01,int,mid,while,---,算法,排序
From: https://www.cnblogs.com/hjy94wo/p/16612074.html

相关文章

  • TCP-IP详解 卷一:协议 pdf
    高清文字版 下载链接:https://pan.baidu.com/s/15RvvtVL6vRVZGBsAdjrveg点击这里获取提取码。  ......
  • 2022-8-22 剑指offer-优先队列-每日一题-二叉树-搜索/递归
    剑指OfferII060.出现频率最高的k个数字难度中等36收藏分享切换为英文接收动态反馈给定一个整数数组 nums 和一个整数 k ,请返回其中出现频率前 k 高的元......
  • 面试---JMM内存模型
    内存模型---内存、线程有关 JMM内存模型是JVM在计算机内存中如何工作的行为规范;它屏蔽了各种硬件和操作系统的访问差异。保证了java程序在各种平台下对内存的访问都能......
  • prometheus process-export进程监控
     oToyix 于2021-09-0811:53:45prometheusprocess-export进程监控 一、环境部署,见prometheus邮件告警第一节https://blog.csdn.net/oToyix/article/detai......
  • 算法中的Top_K 问题总结
    写在前面在人工智能算法岗位的面试中,TopK是问得最多的几个问题之一:到底有几种方法?这些方案里蕴含的优化思路究竟是怎么样的?为啥TopK这么受欢迎呢?究其原因,还是因为它不......
  • Python-09_01函数参数的传递
    参数传递:在Python中,类型属于对象,变量是没有类型的:如Str=‘hello’;Str=50,在以上代码中,hello是string类型的,50是整型,而变量Str是没有类型的,它仅仅是一个对象的引用(指针),......
  • 从零开始Blazor Server(12)--编辑菜单
    上个星期有点事,导致没法及时更新。现在我们继续更我们的从零开始系列。这个系列也快要结束了,目前规划再有2-3篇,就结束了。今天我们来说编辑菜单的问题,说实话菜单这种东西,你......
  • Python-09_02函数参数类型、函数嵌套
    1、Python函数参数类型:必备参数、关键字参数、缺省参数、任意个数参数。必备参数须以正确的顺序传入函数,也叫做位置参数,即参数是通过位置进行匹配的,从左到右,依次进行匹配,......
  • 01-springcloud学习记录
    SOA架构与微服务区别微服务拆分更加详细,主要以远程相互调用完成业务功能。SOA也是业务拆分,但一个模块内仍然有多个相近业务相互依赖。RestfulAPI是一种软件设计风......
  • JAVA---04
    第四天1.Java方法什么是方法方法是语句的集合,它们在一起执行一个功能方法是解决一类问题的步骤的有序组合方法包含于类或对象中......