排序 专题讨论

排序 专题讨论

排序 专题讨论

一.问题阐述

前K大问题

从一组元素(n个)中找出前K大个元素

二.解决思路

1.先将n个元素按照从小到大进行排序。

2.然后将排序好的数组从后输出K个元素。

三.关键过程

如何将n个元素进行排序?

代码如下:

void Sort(int* arr, int n)
{
    int i=0;
    int position=-1;
    while(i<n)
    {
        if(i==0||arr[i-1]<=arr[i])
        {
            if(position==-1)
            {
                i++;
            }
            else{
                i=position+1;
                position=-1;
            }
        }else{
             if(position==-1)
            {
                position=i;
            }
            int tmp=arr[i];
            arr[i]=arr[i-1];
            arr[i-1]=tmp;
            i--;
        }
    }
}

四.分析

代码中的position是用来记录交换时,当前元素的下标。

当前面的元素整理完成,i 可以直接跳到 position+1,减少循环次数。

举例:

[5, 3, 2, 4]

cmp 5 3

change -> [3, 5, 2, 4]

position 为 1

jump 2 #这里jump的位置是position+1

cmp 5 2

change -> [3, 2, 5, 4]

cmp 3 2

change -> [2, 3, 5, 4]

jump 2

cmp 3 5

cmp 5 4

change -> [2, 3, 4, 5]

cmp 3 4

jump 4

运行代码截图:

排序 专题讨论
排序 专题讨论

最好循环执行次数为n,最坏为n(n+1)/2。

所以最好的时间复杂度为O(n),最坏为O(n^2)。

五.拓展

这个问题和PTA 7-5 选做 寻找大富翁 考核的差不多

所以用这个排序进行测试。

排序 专题讨论
排序 专题讨论

六.结论

这个排序算法比较简单,比较稳定,容易理解,有点类似与插入排序,但是将一个数放入其正确位置的交换同冒泡排序(一系列交换)

简单,只有一层循环,最好的时间复杂度为O(n),最坏为O(n^2)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114446.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java算法——判断素数[通俗易懂]

    Java算法——判断素数[通俗易懂]Java算法——判断素数,供自己学习方便和初学者参考! publicstaticbooleanisPrimeNumber(intnumber){if(number<2){returnfalse;}for(i

  • 常用电平转换电路的方法有_双击电平转换单级电路

    常用电平转换电路的方法有_双击电平转换单级电路电平转换在电路应用中屡见不鲜,方案设计也是五花八门,本文中整理了一些常见的电平转换电路,区别于成本功耗等因素的不同适用于不同的应用场景,读者可以用作参考,根据实际项目需求加以更改。1、上拉电阻加二极管方案(低成本)本方案适用于输入信号电平大于输出信号电平的转换电路上2、适用于输入信号大于输出信号的电平转换电路上,三极管选型要求:PNP三极管的饱和压降尽可能小,否则可能导致转换异常3、适用于大部分应用场景。属于典型应用。很多模块设计上都会采用这样的方案,成本低,而且转换的可靠性好4、2级反相

  • [Android] 【每日更新书源】「阅读」APP -100+ 精品书源一键导入!每天自动更新最新书源!…

    [Android] 【每日更新书源】「阅读」APP -100+ 精品书源一键导入!每天自动更新最新书源!…我特地写了个爬虫爬取书源,每天自动更新书源(URL是固定的)!大家也可以定期导入一下!放心!导入时会自动去除重复书源的!前段时间我发过一个书源大礼包的帖子,不过现在已经无法编辑修改了,所以我又开了一个新帖子,这次内容可不一样了!我上次说过想要自动抓取阅读官方公众号里分享的书源,结果结果公…

  • Python面试必备的7大问题

    本文给大家总结了Python面试必备的7大问题。例如:交换变量值、is 和 == 的区别、可变对象和不可变对象、连接字符串用join还是+、__new__和__init__的区别,等等。

  • vim退出编辑模式非esc_centos保存退出vim

    vim退出编辑模式非esc_centos保存退出vimlinux中退出vi编辑器,按下esc没反应的解决办法:1、在正常模式下按下q键盘;2、选择【a-z】或【0-9】中任意一个作为缓冲器的名字,准备开始录制宏;3、在非insert模式下输入q停止宏的录制;4、使用@和定义的缓冲器名字即可。linux中退出vi编辑器,按下esc没反应的解决办法:vimrecording功能介绍使用vim时无意间触碰到q键,左下角出现“recording”这个标识,…

  • 现场总线及其应用「建议收藏」

    现场总线及其应用「建议收藏」现场总线是应用在生产现场、在微机化测量控制设备之间实现双向串行多节点数字通信的系统,也被称为开放式、数字化、多点通信的底层控制网络。现场总线技术形成了真正分散在现场的完整控制系统,提高了控制系统运行的可靠性,丰富了控制设备的信息内容。为控制信息进入公用数据网络创造了条件,沟通了现场控制设备之间及其与更高控制管理层网络之间的联系,便于实现管控一体化,同时控制网络与数据网络的结合,便于实现信号的远程传…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号