如果我问你:排序算法的「稳定性」有何意义?你怎么回答?

虽然我们在工作不一定经常去写排序算法,但是排序算法却是充斥着我们的程序生活,比如你不经意间调用了SDK中的某个sort算法,其背后无非是什么快排、归并等算法。而且在我们面试的过程中也会经常被问及,如果你在面试的过程中连一个最基本的冒泡排序都不会写的话,那么很明显的面试结果也不会好到哪里去。

除了基本的实现之外,我们关注排序算法的同时,往往还会关注它的时间复杂度和空间复杂度。在面试之前,我们可能还会临时抱佛脚的去记一下其稳定性。下表中列举了几种常见的排序算法的核心总结。

对于时间复杂度和空间复杂度这种倒是好理解,如果你经常刷leetcode,就会非常关注此类问题。但是「稳定性」这个属性往往被我们所忽视,我们一般会记住稳定性的定义以及特定算法所对应的稳定性,但是是否想过「稳定性」有何意义?

稳定性的定义:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

如果我们只是面对简单的数字排序,那么稳定性确实也没有多大意义。比如,1 2 3 3 4的序列中如果第一个3和第二个3在sort方法反复执行之后位置也反复变化,但是对于调用sort方法所想要获得排序结果的上游应用而言,那么结果还是1 2 3 3 4,至于3的次序,无关紧要。

如果排序的内容仅仅是一个复杂对象的某一个数字属性,那么稳定性依旧将毫无意义(所谓的交换操作的开销已经算在算法的开销内了,如果嫌弃这种开销,不如换算法好了?)

如果要排序的内容是一个复杂对象的多个数字属性,但是其原本的初始顺序毫无意义,那么稳定性依旧将毫无意义。

那么排序算法的「稳定性」在什么情况下才会变得有意义呢?

举个例子,一个班的学生已经按照学号大小排好序了,我现在要求按照年龄从小到大再排个序,如果年龄相同的,必须按照学号从小到大的顺序排列。那么问题来了,你选择的年龄排序方法如果是不稳定的,是不是排序完了后年龄相同的一组学生学号就乱了,你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法,我就只需要按照年龄排一遍就好了。

从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。要排序的内容是一个复杂对象的多个数字属性,且其原本的初始顺序存在意义,那么我们需要在二次排序的基础上保持原有排序的意义,才需要使用到稳定性的算法。

排序算法的「稳定性」有何意义?这个还是要分应用场景来看,很多使用情况下,并没有什么实质的意义,而在有些情况下却有很重要的意义。

有很多算法你现在看着没啥,但是当放在大数据云计算的条件下它的稳定性非常重要。举个例子来说,对淘宝网的商品进行排序,按照销量,价格等条件进行排序,它的数据服务器中的数据非常多,因此,当时用一个稳定性效果不好的排序算法,如堆排序、shell排序,当遇到最坏情形,会使得排序的效果非常差,严重影响服务器的性能,影响到用户的体验。

排序算法的「稳定性」有何意义?你以前是否忽略了这个问题,那么现在你Get到了吗?或者你有更好的答案,欢迎在文末留言。

Image placeholder
zhangsanfeng1227
未设置
  82人点赞

没有讨论,发表一下自己的看法吧

推荐文章
如果有人再问你怎么实现分布式延时消息,这篇文章丢给他

1.背景上篇文章介绍了RocketMQ整体架构和原理有兴趣的可以阅读一下,在这篇文章中的延时消息部分,我写道开源版的RocketMQ只提供了18个层级的消息队列延时,这个功能在开源版中显得特别鸡肋,但

Dubbo 稳定性案例:Nacos 注册中心可用性问题复盘

问题描述上周四晚刚回到家,就接到了软负载同学的电话,说是客户线上出了故障,我一听”故障“两个字,立马追问是什么情况,经过整理,还原出线上问题的原貌:客户使用了Dubbo,注册中心使用的是Nacos,在

稳定性专题 | Spring Boot 常见错误及解决方法

导读『StabilityGuide』是阿里多位阿里技术工程师共同发起的稳定性领域的知识库开源项目,涵盖性能压测、故障演练、JVM、应用容器、服务框架、流量调度、监控、诊断等多个技术领域,以更结构化的方

谈谈前端面试中的七种排序算法

课程推荐:前端开发工程师--学习猿地精品课程 一、冒泡排序冒泡排序的思路:遍历数组,然后将最大数沉到最底部; 时间复杂度:O(N^2); 空间复杂度:O(1) functionBubbleSort(a

小程序拍了拍你:来看看如何避开路由雷区

推荐课程:课程推荐:前端开发工程师--学习猿地精品课程 典型案例在一个夜黑风高的夜晚,“xx饭很多”百度智能小程序悄然上线,目录结构如下: ├──pages│└──home│├──index.js│├

SQL 查询语句总是先执行 SELECT?你们都错了

很多SQL查询都是以SELECT开始的。不过,最近我跟别人解释什么是窗口函数,我在网上搜索”是否可以对窗口函数返回的结果进行过滤“这个问题,得出的结论是”窗口函数必须在WHERE和GROUPBY之后,

源码分析 | 咋嘞?你的IDEA过期了吧!加个Jar包就破解了,为什么?

微信公众号:bugstack虫洞栈|博客:https://bugstack.cn沉淀、分享、成长,专注于原创专题案例,以最易学习编程的方式分享知识,让自己和他人都能有所收获。目前已完成的专题有;Net

Java的Lambda表达式有何用处?如何使用?

本文转载自知乎,之前刚接触到Lambda表达式,看了好多文章,看完也还是一脸懵逼,后来刷知乎刷到这篇文章,顿开茅塞,让我明白了Lambda表达式到底是个啥,咋用。最重要的是第一点,知道了这个,其他的要

基于中台实践的DevOps平台有何不同?

为了响应快速变化的市场需求,业务要快速迭代。IT正在向云原生架构转型,解放架构自由度,最大化业务敏捷性,解耦合、敏捷开发、快速部署是当下企业的追求,可以消除研发与运维之间鸿沟的DevOps(研发运维)

瞧瞧,这样的「函数」才叫 Pythonic

课程推荐:Python开发工程师--学习猿地--送9个上线商业项目 在机器学习中,我们经常需要使用类和函数定义模型的各个部分,例如定义读取数据的函数、预处理数据的函数、模型架构和训练过程的函数等等。那

编程书说的 “Go 程序员应该让聚合类型的零值也具有意义” 是在讲什么

在《Go语言编程》这本书和很多其他Go编程教程中很多都提到过“Go程序员应该让一些聚合类型的零值也具有意义”的概念,我们这篇文章主要说一下有意义的零值这个话题。 在Go中声明变量时如果初始化表达式被省

实践和思考的重要意义(论软件代码设计)

感触 最近这段时间,包括以前,经常听到,程序员们大谈设计模式,这个话题并不陌生,面试必问的问题,活了这么多年,我就一直没搞清楚,为啥面试官喜欢问这个问题。如果一个面试官喜欢问这种问题,我觉得也没啥意思

实践和思考的重要意义(论软件代码设计)

感触最近这段时间,包括以前,经常听到,程序员们大谈设计模式,这个话题并不陌生,面试必问的问题,活了这么多年,我就一直没搞清楚,为啥面试官喜欢问这个问题。如果一个面试官喜欢问这种问题,我觉得也没啥意思。

最稳定可靠,PostgreSQL 12.1版本正式发布!

1.PG12.1Beta发布了!PostgreSQL全球开发组宣布,PostgreSQL12的第一个测试版(PG12.1Beta)现已开放下载。该版本中可预览的所有特性都将延续至PG12的最终版本中,

稳定彰显强悍实力,商务办公首选ThinkPad L490

商务本主要面向的人群是职场精英,他们对于产品的稳定性以及数据的安全性都有极高的要求,与此同时为了满足繁杂的办公任务,也需要强劲的性能来保驾护航。全新产品ThinkPadL490采用了英特尔第八代低功耗

21世纪了还愚公移山?数据库这么迁移更稳定!

Photoby BarthBailey on Unsplash在系统的快速迭代过程中,业务系统往往部署在同一个物理库,没有做核心数据和非核心数据的物理隔离。随着数据量的扩大这种情况会带来稳定性的风险,

爬虫究竟是合法还是违法的?

据说互联网上50%以上的流量都是爬虫创造的,也许你看到很多热门数据都是爬虫所创造的,所以可以说无爬虫就无互联网的繁荣。前天写了一篇文章《只因写了一段爬虫,公司200多人被抓!》,讲述程序员因写爬虫而被

第 10 节:复合类型 1.4 冒泡排序与数组去重

04冒泡排序packagemain import"fmt" funcmain(){ vararr[10]int=[10]int{9,1,5,6,8,2,10,7,4,3} //外层执行一次内层执

orderBy 排序优化

在日常的业务开发中,orderby排序是少不了的。但要写出高效的排序SQL,需要先花点精力和时间来了解排序的底层原理,这样才能找到优化排序的好策略。排序的方式index(索引排序,性能最佳)尽可能使用

mysql 查询按照中文进行排序

在mysql中我们使用orderby来实现查询排序,如:SELECT\*FROMmemberORDERBYidASC//查询用户表并按照id正序排序 SELECT\*FROMmemberORDERBY

小知识-SQL 自定义排序

问题场景在一次写业务的过程中,发现在使用sql查询数据的时候,不是按照我希望的顺序进行排序的,而是根据系统顺序进行排序的.o(╥﹏╥)oSELECT*FROMtable_nameWHEREidin(3

浅谈JavaScript 中sort( ) 排序的坑

推荐课程《Java全栈开发工程师--学习猿地》 Array数组的排序受关注度一直就不高,除非当它出现了问题。最近我在项目中就遇到了一个数组排序问题,数组中的项没有按我预想的被排序,导致界面上无法正常显

聊聊前端排序的那些事

课程推荐:前端开发工程师--学习猿地精品课程 前言貌似前端[1]圈一直以来流传着一种误解:前端用不到算法知识。[2]长久以来,我也曾受这种说法的影响。直到前阵子遇到一个产品需求,回过头来看,发现事实并

八大基础排序总结

课程推荐:Java开发工程师--学习猿地精品课程 前言大概花了一周的时间把八大基础排序过了一遍,这篇博文主要是用来回顾一下八大基础排序的要点和一些总结~回顾: 冒泡排序就这么简单选择排序就这么简单插入

阿里云小蜜对话机器人背后的核心算法

0.对话系统简介 对话系统的一般架构如图: 图1:对话系统一般架构 这是我们所熟知的对话系统框架,这里面主要有:NLU自然语言理解,DM对话管理,NLG自然语言生成3个主要模块,DM里面有dialo