写给妹妹的编程札记 - 排序

2024-05-24 04:58

本文主要是介绍写给妹妹的编程札记 - 排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


排序, 顾名思义,就是将一个给定集合的元素按定义的比较函数排列为有序状态。


排序算法很多, 我们需要针对不同使用场景和要求,选择恰当的排序算法。 排序算法的一些重要权衡指标:
1. 编程实现复杂度 
2. 时间复杂度, 包括平均时间复杂度,和最坏时间复杂度
3. 空间复杂度
4. 稳定性。 我们说一个排序算法是稳定的, 当她能保证相同键值的元素在排序之后,先后顺序保持不变

下面是一些常见的排序方法, 应该熟悉掌握这些排序方法, 了解它们的优缺点,在正确的场景使用它们。
名称 数据对象 稳定性 时间复杂度 空间复杂度 描述
平均 最坏
插入排序数组、链表YesO(N^2)O(1)(有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。
直接选择排序数组No O(N^2)O(1)(有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。对数组:比较得多,换得少。
链表Yes
堆排序数组NoO(N * logN)O(1)(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。
归并排序数组、链表YesO(N * logN)O(N) + O(logN),如果不是从下到上把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。

缺点:
1. 需要额外的空间
快速排序数组NoO(N * logN)O(N^2)O(logN), O(N)(小数,枢纽元,大数)。

缺点:
1. 不稳定
2. 最坏时间复杂度为O(N^2)。 一般通过随机选取pivot或者采用混合排序(如内省排序)来弥补
内省排序数组NoO(N * logN)O(N * logN)O(logN)缺点:
1. 相对堆排序来说, 缺点就是递归需要的栈空间
计数排序数组、链表Yes
O(N)O(N + M)统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。
应用场景仅限于排序元素可能取值比较小。
桶排序数组、链表YesO(N)O(M)将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。
应用场景限于排序元素分布比较均匀
基数排序数组、链表YesO(k * N),最坏:O(N^2)
一种多关键字的排序算法,可用桶排序实现。
应用场景 log(N)显著大于k. 这时时间复杂度上才明显优于O(N* log N)

问题:
        1. 实现上述常见排序算法
        2. 思考什么样的情况下,实现的排序算法会效率降低?
        3. 给定一个排序实现, 怎么构造一个使得该排序实现消耗时间尽可能长的测试用例?
        4. 如果不需要全排序, 只需要找出最大的k个元素呢? 怎么分别对这些常见排序算法进行修改?

        如果针对上述的常见排序算法都能很好地回答这几个问题, 排序算法就算及格了。

参考资料:
         http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
http://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used


这篇关于写给妹妹的编程札记 - 排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/997436

相关文章

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal