0%

数据结构——排序

发表于 分类于
“排序”是基于数据逻辑结构T=(D,R)定义的一种重要的运算。它的功能是将一个数据元素的任意序列，依据关键字的大小，重新排列称一个有序的序列。D是数据元素集；R是数据元素之间关系偶对集。

基本概念

“排序”是基于数据逻辑结构T=(D,R)定义的一种重要的运算。它的功能是将一个数据元素的任意序列，依据关键字的大小，重新排列称一个有序的序列。D是数据元素集；R是数据元素之间关系偶对集。

术语：能唯一标识数据元素的一个分量或多个分量的组合称为关键字；不能唯一标识数据元素的分量称为次关键字。

如果一个排序的算法，对于数据元素按照此关键字排序后，能确保相同次关键字的数据元素排序前后，相对次序不变，则称该算法为是稳定的，否则称该算法是不稳定的。

内部排序是指对存储在计算机的主存储器（也称“内存”）中的数据进行排序的过程。

插入排序法

直接插入排序法

基本原理：先把$a_1$看成一个有序的包含一个数据元素的序列。然后不断地在一个递增有序的序列$(a_1,…,a_{i-1})(2\le i\le n)$中，插入一个数据元素$a_i$，使得$a_1,…,a_{i-1},a_i$构成一个新的有序的序列。

基本步骤：

  1. 确定插入位置；
  2. 移动元素；
  3. 填入新元素。

正序情况：算法的比较次数和移动次数均达到最好，待插入元素仅仅与左边一个元素比较一次，不需要移动。即：比较次数和移动次数分别为n-1次和0次。

逆序情况：算法的比较次数和移动次数均达到最坏。即：比较和移动次数分别为2+3+…+n次和(2+1)+(3+1)+…+(n+1)次。

算法时间性能：$T_{best}(n)=O(n)\quad T_{worst}=O(n^2)\quad T_{average}=O(n^2)$

直接插入排序算法有几种不同的变种：

  1. 折半插入排序：折半插入排序是利用待插入表的有序性，将上述直接排序中欧给的顺序查找定位，改进采用为折半查找法定位。$T_{worst}(n)=T_{average}(n)=O(n^2)$
  2. 2-路插入排序：将待排序的数据元素，分情况插入到这两个子表的某一表中间。算法思想：
    1. 取出表$L=(a_1,a_2,a_3,…,a_i,…,a_n)$的第1个元素$a_1$存入辅助空间$D[1]$ ；
    2. 取出表$L$的下一个元素$a_1(2\le i\le n)$，如果$a_i<D[1]$，则插入到$D[1]$之左边的有序子表，否则插入到$D[1]$之右边的有序子表；
    3. 重复第二步，直到最后一个元素$a_n$插入后为止。
  3. 表插入排序：是基于静态链表的这样一种物理存贮结构，将待排序数据元素按照大小顺序建立起静态链表。这个静态链表是以0下标为头结点的循环链表，头结点存储关键字的最大理论值MAXINT，相当“哨兵”作用。插入每个元素$a_i$的操作：
    1. 确定插入位置，即从循环静态链表首结点开始，第一次遇到大于$a_i$的元素x时，x所在结点之前为$a_i$元素所在结点的插入位置；
    2. 修改指针，即$a_i$元素所在结点指向x所在结点，将x所在结点的前驱结点指向$a_i$所在结点。

希尔排序

直接插入排序的特性：待排序数据元素越接近正序，其时间复杂度会越低。待排序数据元素序列为正序时，其时间复杂度会从$O(n^2)$逐渐降低至$O(n)$。

基本思想：先将整个待排序数据元素序列分割成若干个子序列分别进行直接插入排序，待整个序列中的数据元素“基本有序”时，再对全体数据元素构成的序列进行一次直接插入排序。

把在第$i$步中，整个序列分成的组数记为$di$。一共进行的排序趟数计做$m$。那么，这里应该满足如下一些条件：

  1. dm=1
  2. 当$1\le i$，$j\le m$，且$i<j$时，di < dj
  3. 当$1\le i$，$j\le m$，且$i\not ={j}$时，$di$和$dj$的最大公约数为1

交换排序法

基本原理：通过不断进行两个元素之间位置的交换，逐步使得每个数据元素移动到表L的正确位置，最后得到一个有序序列。

冒泡排序

按照从左至右的顺序，从左边的第一个元素开始，依次比较相邻的两个数据元素，如果逆序则交换它们的位置。这样进行一趟比较交换，可以将最大值交换到最后的位置即正确位置。

第一趟：对于表$L=(a_1,a_2,a_3,…,a_i,…,a_n)$，从左至右的顺序，将序号相邻的、反序的两个元素交换。第一趟结束后，$a_n$就是关键字最大的那个数据元素；

第二趟：对于除最后一个数据元素之外的剩余部分构成的子表重复第一步，第二趟结束后，$a_{n-1}$就是关键字次大的那个数据元素；以此类推。直到剩余部分构成的子表表长等于1为止。

在“正序情况”下，算法的交换次数达到最好，不需要移动。即0次。在“逆序情况”下，算法的交换次数达到最坏，移动次数为(n-1)+(n-2)+…+1次。
所以，$T_{best}=O(n^2)\quad T_{worst}=O(n^2)$。

快速排序

快速排序时通过一趟交换，将待排序序列的第1个数据元素交换到正确位置。

  1. 依据表$L=(a_1,a_2,a_3,…,a_i,…,a_n)$的第一个元素$a_1$，把$a_1$放在合适的位置，以将表L“划分”成左右2个逻辑子表，使得$a_1$大于左子表的所有元素，且小于右子表的所有元素；
  2. 左、右子表分别进行递归处理。

首先$low$和$high$初始值分别指向表L的最左和最右的单元。

  1. 当$low < high$时，重复做如下处理：
    1. 向左移动$high$，将首次遇到的小于$L[low]$的$L[high]$与$L[low]$交换；
    2. 向右移动$low$，将首次遇到的大于$L[high]$的$L[low]$与$L[high]$交换。
  2. 当$low > high$，表示“划分结束”。

$T_{best}=O(nlog_2n)\quad T_{worst}(n)=O(n^2)\quad$

选择排序法

基本原理：先选择表L的最大元素，与最后位置上元素交换；然后选择表L的次大元素，与倒数第二个位置上元素交换；依此类推，最后得到一个有序的序列。

简单选择排序

简单选择排序是采用顺序查找法确定最大元素的位置，与最后位置上元素交换。

算法思想：

  1. 对于表$L=(a_1,a_2,a_3,…,a_i,…,a_n)$，顺序遍历，选择出最大元素所在位置，与最后位置元素交换；
  2. 对于除最后一个元素之外的剩余部分构成的子表重复第一步，直到剩余部分构成的子表表长等于1为止。

算法时间性能：$T_{worst}(n)=T_{best}=O(n^2)=T_{average}(n)$

堆排序

堆排序是利用构建“堆”的方法确定具有最大值的数据元素，并把该元素与最后位置上元素交换。

满足下列条件的n个数据元素序列$(a_1,a_2,…,a_n)$称为堆。

可以将任意一个由n个数据元素构成的序列$(a_1,a_2,…,a_n)$，按照从左到右的顺序按层排序构成一棵与该序列对应的完全二叉树。

一棵完全二叉树是一个堆，当且仅当完全二叉树的每棵子树的根值$a_i\ge$其左子树的根值$a_{2i}$，同时$a_i\ge$其右子树的根值$a_{2i+1}(1\le i\le \frac{n}{2})$。

堆和堆排序算法

堆排序的思路是将表$L=(a_1,a_2,a_3,…a_i,…,a_n)$转换成大顶堆，将堆的根（即L的第一个位置的元素）与最后一个叶子（即L最后一个位置的元素）交换；然后，除最后一个叶子外剩余部分再重复上述处理。

假设表$L=(a_1,a_2,a_3,…a_i,…,a_n)$对应的完全二叉树T中，树根的右子树均为堆，仅仅是T的根不满足堆的条件，将这种特殊情况的完全二叉树T转换成堆的过程，称为“调整堆”。

调整堆算法思想：

  1. 将树根与其左右子树根值最大者交换；
  2. 对交换后的左（或右）子树重复第一步，直到左（或右）子树为堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Typedef Sqlist HeapType;  //堆采用顺序表存储表示
void HeapAdjust(HeapType &H, int s, int m)
{
   //除了H.r[s].key之外，H.r[s..m]中的关键字均满足堆的定义，
   //本函数调整H.r[s]的关键字，使得H.r[s..m]成为一个大顶堆。
   rc.H.r[s];
   for(j=2*s;j<=m;j*=2) //沿key较大的华子结点向下筛选
   {
      if(j<m&&LT(H.r[j].key, H.r[j+1].key))
         ++j;
      if(!LT(rc.r[j].key, H.r[j].key))
         break;
   }
   H.r[s]=rc;
}

创建堆算法思想：

从最大序号的非叶子结点开始逐步到根，对于每棵子树，调用“调整堆”算法，使其成堆。

  1. 创建堆：从最后一个非叶子结点开始逐步到树根，对于每个子树进行调整堆；
  2. 重复n-1次如下处理：将堆的根与最后一个叶子交换；除最后一个叶子之外剩余部分再调整堆。

堆排序算法分析：$T_{worst}(n)=O(nlog_2n)$

归并排序法

基本原理：两个有序表合并（merge）成为一个有序表。

算法思想：（对线性表$L=(a_1,a_2,a_3,…a_i,…,a_n)$的每个元素，看成一个有序子表）

  1. 从左至右，将相邻的两个有序子表合并之；
  2. 重复第一步，直到所有子表合并成一个有序子表为止。

算法分析：$T_{worst}(n)=O(nlog_2n)\quad$空间复杂度$S(n)=O(n)$

基数排序法

多关键字排序

假设有n个数据元素的序列${R_1,R_2,…,R_n}$，且每个数据元素$R_i$中含有d个关键字$(K_0,K_1,…,K_{d-1})$。$K_0$：最主位关键字，$K_{d-1}$：最次位关键字。多关键字排序可以分为最主位优先排序法和最次位优先排序法两种。

最主位关键字排序（MSD-Most Significant Digit first）

算法思想：

  • 首先将所有的数据元素按照最主位，也就是第一个关键字$K_0$进行排序，将序列分成若干子序列，每个子序列中的数据元素都具有相同的$K_0$值；

  • 之后，对于具有相同$K_0$值的子序列，再依据第d个关键字$K_1$分别；

  • 依此类推，直到对相应子序列分别依据第d个关键字$K_{d-1}$排序为止，将所有子序列链接在一起构成整个有序序列。

最次位优先排序（LSD-Least Significant Digit first）

算法思想：

  • 首先依据最次位关键字，也就是第d个关键字$K_{d-1}$排序；

  • 之后，对于整个序列，再依据第d-1个关键字$K_{d-2}$排序；

  • 依此类推，直到对整个序列依据第1个关键字$K_0$排序为止。此时得到整个有序序列。

MSD和LSD排序方法的不同特点总结：

  • 若按照MSD进行排序，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序；
  • 若按照LSD进行排序，不必分割成子序列，对每个子序列都是整个序列参加排序，且只能用稳定的排序方法。

基数排序

基本原理：将关键字每一位$K_m$视为一关键字，这样排序问题就转换成多关键字$(K_0,K_1,K_2,…,K_{n-1})$排序，并采用最次位优先排序方法，即LSD方法进行排序。

算法思想：假设每个关键字的每一位可能的取值的情形数目为r，把它定义为基数。

  • 首先，开辟一块连续的地址空间，作为存贮区，存放待排序的关键字序列；
  • 然后，从最低位开始直到最高位，将存储区的关键字依次进行“入桶”操作，然后依次进行“出桶”操作，存放到存储区中。
  • 之后，入桶和出桶操作重复d遍（d代表关键字中的位数）。

时间性能：$T(n,d)=O(d\cdot n)\quad S(n,r)=O(r\cdot n)$