数据结构:排序概述
排序是计算机程序设计中的一种重要操作,在很多领域中都有广泛的应用。比如,各种升学考试的录取工作,日常生活的各类竞赛活动等都离不开排序。为了满足不同的需求,人们设计了大量的排序算法。每种排序算法都有其各自的特点和适用场景,了解和掌握典型的、常用的排序算法,可以帮助我们编写更高效的程序。排序涉及的知识点较多,本篇主要讨论与排序相关的基本概念。
一、排序的基本概念
1.1、排序的定义
排序(Sorting)是指按关键字的非递减(或非递增)顺序对一组记录重新进行排列。
假设含n个记录的序列为,其相应的关键字序列为。需确定的一种排列,使其相应的关键字满足如下的非递减(或非递增)关系:
即使含n个记录的序列成为一个按关键字有序的序列:
这样一种操作称为排序。
1.2、排序的稳定性
当排序记录中的关键字都不相同时,则任何一个记录的无序序列经排序后得到的结果唯一;反之,当待排序的序列中存在两个或两个以上关键字相等的记录时,则排序所得的结果不唯一。
假设,且在排序前的序列中领先于(即i<j)。若在排序后的序列中仍领先于,则称所用的排序方法是稳定的;反之,若可能使排序后的序列中领先于,则称所用的排序方法是不稳定的。需要注意的是,排序算法的稳定性是针对所有记录而言的。也就是说,在所有的待排序记录中,只要有一组关键字的实例不满足稳定性要求,则该排序方法就是不稳定的。
虽然稳定的排序方法和不稳定的排序方法排序结果不同,但不能说不稳定的排序方法就不好,各有各的适用场合。
1.3、内部排序和外部排序
由于待排序记录的数量不同,使得排序过程中数据所占用的存储设备会有所不同。根据在排序过程中记录所占用的存储设备,可将排序方法分为两大类:内部排序和外部排序。
- 内部排序,是指待排序记录全部存放在计算机内存中进行排序的过程;
- 外部排序,是指待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
二、内部排序方法的分类
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中,可以将排序记录区分为两个区域:有序序列区和无序序列区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。
根据逐步扩大记录有序序列长度的原则不同,可以将内部排序分为以下几类。
- 插入类:将无序子序列中的一个或几个记录“插入”到有序序列中,从而增加记录的有序子序列的长度。主要包括直接插入排序、折半插入排序和希尔排序。
- 交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。主要包括冒泡排序和快速排序。
- 选择类:从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。主要包括简单选择排序、树形选择排序和堆排序。
- 归并类:通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。2-路归并排序是最常见的归并排序方法。
- 分配类:是唯一一类不需要进行关键字之间比较的排序方法,排序时主要利用分配和收集两种基本操作来完成。基数排序是主要的分配类排序方法。
三、待排序记录的存储方式
通常会采用以下几种方式存储待排序记录:
-
顺序表:记录之间的次序关系由其存储位置决定,实现排序需要移动记录。
-
链表:记录之间的次序关系由指针指示,实现排序不需要移动记录,仅需修改指针即可
-
顺序表+链表:待排序记录本身存储在一组地址连续的存储单元内,同时另设一个指示各个记录存储位置的地址向量,在排序过程中不移动记录本身,而移动地址向量中这些记录的“地址”,在排序结束之后再按照地址向量中的值调整记录的存储位置。这种排序方式称为地址排序。
为讨论方便,在后续讲解具体排序算法时,都将采用顺序表作为存储方式,并假设记录的关键字均为整数。待排序记录的数据类型定义如下:
1 |
|
四、排序算法效率的评价指标
目前,评价排序算法好坏的标准主要有两点。
-
执行时间。对于排序操作,时间主要消耗在关键字之间的比较和记录的移动上(注:这里只考虑以顺序表方法存储待排序记录),排序算法的时间复杂度由这两个指标决定。因此可以认为,高效的排序算法的比较次数和移动次数都应该尽可能的少。
-
辅助空间。空间复杂度由排序算法所需的辅助空间决定。辅助空间是除了存放待排序记录占用的空间之外,执行算法所需要的额外存储空间。理想的空间复杂度为O(1),即算法执行期间所需要的辅助空间与待排序的数据量无关。
五、总结
本篇文章主要讨论了排序算法涉及的基本概念,主要内容如下。