vlambda博客
学习文章列表

「今天是学习C语言第 130 天」

# 为什么学习排序算法

排序和查找是计算机专业课程数据结构和算法中最重要的部分之一，也是编程中常用的基础知识。C语言初学者对直接插入、简单选择两种最简单的排序算法必须掌握，足以应付一般的考试、课程设计、小程序编写。

但是对于计算机专业、编程开发的同学，必须熟练掌握这12个算法，达到手写算法的程序，排序算法在算法能力训练、考研笔试和机试、工作面试、真实软件项目中普遍使用。

C语言必须的12个排序算法文章系列，每篇文章介绍一个算法，使用C语言实现一个排序算法，这些代码可以作为模板代码，大家可以收藏，方便编程使用。

# 何为排序

排序是编程中最重要的操作，软件项目中也有大量的需求，例如日常购物商品按照价格、名称、购买数量等排序。

排序，简单的说，就是给定一些数据记录，其中数据记录有很多元素组成，按照其中的某个元素进行排序（从大到小、从小到大等），最终形成一个有序的数据记录序列。这里的某个元素可以称为关键字，排序的过程就是算法。

例如：例如商品记录有商品编号、名称、价格、销量、上架日期等元素组成，如果按照价格排序，那么价格就是关键字。

排序能提高另一个重要操作查找的效率，有序的记录可以进行折半查找，无序的记录只能按照顺序进行查找。

# 基本概念

## 算法

算法是对问题求解的步骤，例如数学问题往往都有相应的解法，这里的解法在计算机中就是算法。但是计算机的算法概念更广，解决问题的过程就可以当作算法。

算法特性：

• -  有穷性，算法步骤必须是有限步骤，可以在有限的时间执行完成。

• -  确定性，相同的输入必须得出相同的输出，执行的路径是唯一的。

• -  可行性，算法必须是能够通过计算机的基本操作实现的。

• -  输入输出，算法一般都有输入和输出，算法执行后的结果是输出。

好算法的标准：

• - 正确性，算法必须能够考虑特定问题所有情况，正确求解问题。

• - 可读性，程序实现算法清晰、易懂、容易理解，符合规范。

• - 健壮性，考虑全面，能够正常处理各种输入等非法错误。

• - 效率，算法执行时间快，需要的内存空间少，这点是衡量算法优劣的重要标准，解决相同的问题，时间和空间效率高的算法更加优秀。

## 时间复杂度

算法执行时间，一般使用程序中重要的操作次数表示，例如循环次数，常见的表示有O(1),O(n),O(n^2),O(nlogn),O(2^n)等，这里的n表示问题的规模，也就是数据记录个数。

## 空间复杂度

算法执行过程，所需要的内存空间大小，内存是计算机重要的硬件资源，算法执行过程除了保存数据记录的内存空间以外，还需要辅助内存空间，以降低时间复杂度和程序代码复杂性。

## 稳定和不稳定的排序算法

数据记录中如果出现两个或以上相同关键字的数据记录，排序后仍然保持原来的顺序，就是稳定的，否则不稳定。

例如：商品A和B的价格相等，商品A数据记录在商品B数据记录前面，如果按照价格排序后，商品A数据记录始终在商品B的前面，那么该算法就是稳定的排序，反之不稳定。

## 内部排序和外部排序

内部排序：所有的数据记录读入到计算机内存中进行排序，一般数据记录量中小规模，计算机内存空间可以一次性容纳。

外部排序：数据记录数量很大，计算机无法一次性读入内存，必须依赖外部硬盘文件进行辅助排序，涉及到硬盘文件等操作。外部排序一般常用的是多路归并排序，这与内部排序中的归并排序思想类似。

# 排序算法分类

排序算法分类根据操作的特点进行分类，常用的有以下12种排序算法，当然排序还有很多复杂、改进的算法。

内存排序分类：

• - 插入排序：直接插入、折半插入、希尔排序

• - 交换排序：冒泡排序、快速排序

• - 选择排序：简单选择排序、堆排序

• - 归并排序：二路归并排序

• - 桶排序

• - 计数排序

• - 基数排序

外部排序：

• - 多路归并排序

其中桶排序、计数排序、基数排序是非比较类算法，它们利用关键字特征和内存空间连续寻址特征进行设计排序，其余算法均是通过比较关键字的大小决定记录的位置。

---------- End ----------

往期精彩推荐：

「喜欢C请赏个 赞    点击右下角 在看」