🗒️Day15【概念解析】排序算法
00 分钟
2023-10-6
2023-11-9
type
status
date
slug
summary
tags
category
icon
password

整理定义

来源
定义
排序(sorting)是计算机程序设计中的一种重要操作,它要求将一个数据元素的任意序列,重新排列成一个有序的序列。排序算法(sorting algorithm)将任意顺序的数据元素重新排列成一个有序的序列。
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。
计算机科学中,排序算法是一种将列表元素按顺序排列的算法

复述展开

算法对比分析

notion image
常见的快速排序归并排序堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序,由于其时间复杂度不能突破 O(nlogn),因此也称为非线性时间比较类排序。在冒泡排序之类的排序中,问题规模为 n,又因为需要比较 n 次,所以平均时间复杂度为 O(n²)。在归并排序快速排序之类的排序中,问题规模通过分治法消减为 logn 次,所以时间复杂度平均 O(nlogn)
比较类排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。
计数排序基数排序桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序,而是通过确定每个元素之前,应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。 非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度 O(n)
非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

算法对比总结

notion image
说明:
  1. 稳定的排序算法按照元素在输入中出现的相同顺序对相等的元素进行排序。如果一个算法具备稳定性,那么在排序之后,如果两个元素相等,排序结果能够相同元素的原始的排列顺序
  1. 排序方式中,in-place 表示可以在已有空间中使用,out-place 表示需要额外的空间进行存储中间数据。
十大排序算法超级链接 →
 

理解体会

  1. 排序算法可以算是计算机科学与技术的基础入门知识,也是在面试中常见的提醒。掌握十大排序算法可以说是面试做题的基础的基础了。在掌握算法各大原理之余,还需要掌握各个算法之间的时间复杂度以及空间复杂度,以及各个算法的排序方式和稳定性。可以在算法对比总结表中查看。
  1. 面试过程中,很多时候,简单的算法是决定面试结果的重要因素。试想,如果练如此基础的算法都无法掌握的话,那如何去使用和改进更复杂的算法呢?所以,在学习算法过程中,还需要自己实地去使用代码编写逻辑,知道原理,也知道如果用代码解决算法问题。

排序算法总结

 
 
📌
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
 

附录

常见排序算法(Python题解说明)
 

评论
  • Twikoo
  • Giscus
  • Cusdis