首页 > 编程语言 >算法基础之快速排序

算法基础之快速排序

时间:2023-09-23 16:25:37浏览次数:52  
标签:sort 示例 int 个数 while 算法 quick 排序 快速

quick_sort方法中如果 i=l,j=r 会死循环的分析

示例代码

void quick_sort(int a[],int l,int r){
    if(l>=r) return;
    int i=l,j=r; //此处设置会导致死循环
    int x = num[(l+r)>>1];
    while(i<j){
        while(a[++i] <x); //死循环的地方
        while(a[--j] >x);
        if(i<j) swap(a[i],a[j]);
    }
    
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
}

代码分析

因为数组a默认值都是0,i的坐标越过了选中的数x ,并且x往后的数都小于0或者没有明确赋值(此种情况为0)此后a[i]的值都会小于x,导致死循环。而

while(a[--j] >x); 就不会导致因为j往左移终究会变成没有明确赋值的0,所以循环会结束。

示例

假如就两个数 98 97,i=1(值97,i坐标往右移动,值变成0,始终小于选出来的数98,导致死循环)

心得

算法当中有很多默认值的地方,比如此处的数组a的未明确下标的值都为0,为一个隐含条件,可以帮忙判断是否发生死循环。

无限划分的分析

重要结论

当以i划分区间,选数不能选到左边界,则a[x] = a[(L+R+1)>>1]

当以j划分区间,选数不能选到右边界,则a[x]=a[(L+R)>>1]

逻辑分析

假设选的数是a[x] ,退出循环时,a[l] ...a[i-1] 都是<a[x],a[i]>a[x];a[j+1]...a[r] 都是>x,a[j]<a[x]

image-20230826164400548

示例

以3 1 2 5 4 这个五个数排序为例:

image-20230826161149245

心得

退出循环时的条件判断,有些退出循环时的条件很明确,比如以i划分,选数为L时,退出循环时i=L,但是j就不确定,只能是比L小的某一个位置。对于明确的位置是算法中一些重要判断的条件。

第K个数中K用作个数比较的分析

示例代码

以下代码是用K做个数

有的地方会看到K用作长度,长度这个说法个人感觉不太容易理解,用作个数更加方便理解。

int quick_sort(int q[], int l, int r, int k)
{
    if (l >= r) return q[l];

    int i = l - 1, j = r + 1, 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 (j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}

以下是K当作坐标


int quick_sort(int l, int r, int k) {
    if(l >= r) return a[k];

    int x = a[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    if (k <= j) return quick_sort(l, j, k);
    else return quick_sort(j + 1, r, k);
}

代码分析

以下分析基于示例数据: a[0] ~a[9] = {10,11,12,13,14,15,16,17,18,19}

K当作个数时:

有两点需要特别注意:

1、快排每一次递归比较的值 是选出的X的值,即中点位置的值,而不是第K个数。

2、退出循环时,以j分割区间,j最终的坐标是在>= X的位置,即如果刚好=X,则j的位置就是X所在位置,而不是X的左侧。

image-20230831001520584

证明一下K当做个数时和K当做下标时效果一样:

重要的隐含条件 初始的左端的

 L1=0

以第二轮比较K1和J2-L2+1为例

image-20230831092209117

本文由mdnice多平台发布

标签:sort,示例,int,个数,while,算法,quick,排序,快速
From: https://www.cnblogs.com/zhaodong462502/p/17724541.html

相关文章

  • 算法基础之高精度总结
    高精度算法分类分类:加、减、乘、除其中加减乘都适用于两个数都是高精度,除法因为除数是高精度的话不好用整除的方法,所以除法时被除数是高精度,除数是整型。高精度加减乘除的异同点加和乘相同点需要从低位到高位处理for(inti=stra.size()-1;i>=0;i--)c.push_back(stra[i......
  • 算法基础之二分查找
    原题链接二分查找中的mid+1和mid-1的问题二分查找中的边界问题处理不好很容易导致死循环和计算错误的问题,以题目数的范围为例。题目大意​二分查找重复数第一次出现的位置和最后一次出现的位置。数学含义​第一次位置即找到一个长度最大的>=X区间的左边界​最......
  • 深度学习算法中的参数共享(Parameter Sharing)
    引言在深度学习算法中,参数共享(ParameterSharing)是一种重要的技术,它通过共享模型的参数来减少模型的复杂度,并提升模型的性能和泛化能力。本文将介绍参数共享的概念、原理以及在深度学习算法中的应用。参数共享的概念参数共享指的是在模型的不同部分使用相同的参数。在传统的机器学......
  • 算法训练day8 LeetCode 344
    算法训练day8:LeetCode344.541.151.剑指offer05.58.344.反转字符串题目344.反转字符串-力扣(LeetCode)题解代码随想录(programmercarl.com)classSolution{public:voidreverseString(vector<char>&s){for(inti=0,j=s.size()-1;i......
  • 算法题——定义一个方法自己实现 toBinaryString 方法的效果,将一个十进制整数转成字符
    用除基取余法,不断地除以基数(几进制,基数就是几)得到余数,直到商为0,再将余数倒着拼起来即可。privatestaticStringtoBinaryString(intnumber){StringBuildersb=newStringBuilder();while(true){if(number==0)break;intyushu=num......
  • 常用算法模版
    常用算法模版今天学会在https://godbolt.org/看汇编了。顺便卡了下常数,以及简单的(不是)压行。快读signedread(){signednum=0,flag=1;charch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;for(;isdigit(ch);ch=g......
  • 算法题——实现类似parseInt的方法
    Scannersc=newScanner(System.in);Stringstr="";while(true){System.out.println("请输入");Stringstr1=sc.nextLine();if(str1.length()<1||str1.length()>10||str1.charAt(0)=='0'){System.out.......
  • 【算法】哈希表
    1哈希表理论基础1.1哈希表哈希表是根据关键码的值而直接进行访问的数据结构。一般哈希表都是用来快速判断一个元素是否出现集合里。1.2哈希函数哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值。如果ha......
  • 【算法】字符串
    1反转字符串题目:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用O(1)的额外空间解决这一问题。1.双指针classSolution:defreverseString(self,s:List[str])......
  • 网络拥塞控制算法总结-PolyCC
    字节跳动在SIGCOMM'23以Poster形式提交了一篇论文《PolyCC:Poly-AlgorithmicCongestionControl》,试图将各种拥塞控制算法整合到一个统一的框架里。其理由是近40年来各种渠道发布的各种拥塞控制算法,没有一种算法能解决所有网络场景(不同的应用,不同的流量模型等)。 如上图,PolyCC......