数据结构中排序方法基本概念及分类

淩亂°似流年 2022-08-04 09:12 202阅读 0赞

**排序的基本概念：**

所谓排序，即将原来无序的一个序列重新排列成有序的序列。注意这个序列中的每一项可能是单独的数据元素，也可能是一条记录（记录是由多个数据元素组成的，例如一个学生记录就是有学号 姓名 年龄 专业等元素组成的）。如果是记录 既可以按照记录的主关键字排序（主关键字唯一标示一条记录，例如学生记录中的学号就是猪关键字，学号不能重复，用来唯一标示一个学生），也可以按照记录的次关键字排序（如学生的姓名 专业等）。

**稳定性：**

在各种排序方法中，有些是稳定的，有些是不稳定的。所谓稳定性，是指待排序的序列中有两个或两个以上相同的项，在排序前和排序后看这些相同项的相对位置有没有发生变化，如果没有发生变化，即该排序方法是稳定的，如果发生变化，则说明该排序方法是不稳定的。  
如果记录中关键字不能重复，则排序结果是唯一的，那么选择的排序方法稳定与否就无关紧要了；如果关键字可以重复，则在选择排序方法时，就要根据具体的需求来考虑选择稳定还是不稳定的排序方法。那么，哪些排序算法是不稳定的呢？  
“快些选堆”：  
其中“快”指快速排序，“些”指希尔排序，“选”指选择排序，“堆”指堆排序，即这四种排序方法是**不稳定**的，其他自然都是稳定的。

**排序算法的分类：**

1） **插入类排序**

即在一个已经有序的序列中，插入一个新的记录，就好比军训排队，已经排好一个纵队，这时来了个新家伙，于是新来的“插入”这个队伍中的合适位置。这类排序有：直接插入排序、折半插入排序、希尔排序。

2）**交换类排序**

该类方法的核心是“交换”，即每趟排序，都是通过一系列的“交换”动作完成的，如军训排队时，教官说：你比旁边的高，你俩交换下，还比下一个高就继续交换。这类排序有：冒泡排序、快速排序。

3） **选择类排序**

该方法的核心是“选择”，即每趟排序都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样最小（或最大）的记录到位。如军训排队时，教官选出个子最小的同学，让他和第一个位置的同学交换，剩下的继续选择。这类排序有：选择排序、堆排序。

4） **归并类排序**

所谓归并，就是将两个或两个以上的有序序列合并成一个新的有序序列。如军训排队时，教官说：每个人先和旁边的人组成二人组，组内排好队，二人组和旁边的二人组组成四人组，内部再排好队，以此类推，直到最后全部同学都归并到一个组中并排好序。这类排序有：（二路）归并排序。

5) **基数类排序**

此类方法较为特别，是基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字，如一副扑克牌，按照基数排序思想可以先按花色排序，则分成4堆，每堆再按A-K的顺序排序，使得整副扑克牌最终有序。

下一篇将详细介绍一下各种排序算法。