【数据结构与算法】——排序综述

Love The Way You Lie 2022-08-09 05:14 205阅读 0赞

# 【定义】 #

#     #

#          将杂乱无章的数据元素，通过一定的方法按照关键字顺序排列的过程叫做排序。 #

# 【分类】      #

排序分为两种：

## 内部排序 ##

待排序记录全部存放在内存中进行排序的过程

## 外部排序 ##

待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程

![Center][]

# 【名词】 #

#     #

#          在这里我们首先明确一下几个名词：时间复杂度、空间复杂度、稳定性 #

## 时间复杂度 ##

一个算法执行所耗费的时间。从理论上是不能算出来的，必须上机运行测试才能知道。一个算法花费的时间与算法中语句的执行次数成正比，语句执行次数多，花费的时间就多。一个算法中语句执行次数成为语句频度或时间频度。记做T(O)。

## 空间复杂度 ##

算法的空间复杂度是指运行完一个算法所需内存的大小。利用空间复杂度，可以对程序的运行时所需的内存有预先的估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

程序执行时所需存储空间包括以下两部分。

（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示。

S(n)=O(f(n))          其中n为问题的规模，S(n)表示空间复杂度。

## 稳定性 ##

排序算法的稳定性，通俗的讲就是能保证排序前两个相等的数，其在序列的前后位置顺序和排序后它们两个的前后位置相同。比如：如果Ai=Aj，Ai原来的位置在Aj的前边，那么排序完之后，Ai的位置还要在Aj的前边。

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些。

# 结语 #

带着这些问题，我们再去探讨排序算法，相信会更加有目的性。

在后续的文章中，我将进一步对排序和算法进行介绍。

[Center]: /images/20220731/3db6373352aa4174a2e1d209a30b4d2f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关 [数据结构与算法] 排序算法

终于学习到了算法部分, 在学习算法时, 我们还是应该回顾一下数据结构与算法之间的关系数据结构是研究数据的组织方式, 是算法的基础算法是解决编程问题的方法论,

逃离我推掉我的手/ 2023年07月02日 12:28/ 0 赞/ 91 阅读

相关数据结构与算法(c++)--排序算法

数据结构与算法(c++)–排序算法这篇文章主要简单记录下数据结构与算法中的排序算法技术书签插入排序直接插入排序希

àì夳堔傛蜴生んèń/ 2022年12月05日 12:27/ 0 赞/ 214 阅读

相关【数据结构与算法】——排序综述

【定义】将杂乱无章的数据元素，通过一定的方法按照关键字顺序排列的过程叫做排序。【分类】

Love The Way You Lie/ 2022年08月09日 05:14/ 0 赞/ 206 阅读

相关 Java数据结构与算法：排序算法

1. 冒泡排序冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的

亦凉/ 2022年07月13日 09:08/ 0 赞/ 256 阅读

相关数据结构与算法系列之一：八大排序综述

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

迷南。/ 2022年06月02日 08:56/ 0 赞/ 256 阅读

相关数据结构与算法排序

数据结构与算法排序一、简述记-排序方法。冒泡排序、选择排序、快速排序、直接插入排序。排序方法优劣比较： ![70

港控/mmm°/ 2022年05月19日 13:14/ 0 赞/ 259 阅读

相关图解数据结构---“内部排序”综述

《图解数据结构---“内部排序”综述》一、为什么我们要进行排序？在当今社会里，我们经常面临要在浩如烟海的信息中查找某条信息。要使这种查找操作

港控/mmm°/ 2022年05月18日 09:17/ 0 赞/ 265 阅读

相关数据结构与算法排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

怼烎@/ 2022年04月12日 08:59/ 0 赞/ 284 阅读

相关数据结构与算法——排序算法—（5）归并排序

思想：将两个有序数列合并成一个有序数列我们称之为归并。归并排序就是利用归并思想对数列进行排序。归并排序包括“从上到下”和“从下到上”，这里主要讲从上到下的思想： (1

缺乏、安全感/ 2022年02月26日 20:59/ 0 赞/ 353 阅读

相关数据结构与算法——排序算法篇

参考网站：[http://www.cnblogs.com/morewindows/category/314533.html][http_www.cnblogs.com_more

ゝ一纸荒年。/ 2021年09月14日 00:52/ 0 赞/ 473 阅读