数据结构

第一章：绪论

---

1.1 什么是数据结构

---

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

程序 == 算法 + 数据结构

1.2 基本概念和术语

---

• 数据：被计算机加工处理的对象。
• 数据元素（记录、表目）：数据的基本单位，是数据集合中的一个个体。
• 数据项：若干数据项组成一个数据元素。
• 数据对象：是性质相同的数据元素的集合，是数据的一个子集。

• 数据类型：在一种程序设计语言中，变量所具有的数据种类。
• 数据结构：具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。

  1. 逻辑结构：数据元素之间的逻辑关系，与计算机无关。

     (1) 集合结构：数据元素除了“属于同一集合”的联系之外，没有其它的关系。
     (2) 线性结构：数据元素之间存在一对一的关系。
     (3) 树型结构：数据元素之间存在一对多的关系。
     (4) 图状结构或网状结构：数据元素之间存在多对多的关系。

  2. 存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。

     (1) 顺序存储：数据元素依次放在连续的存储单元中。
     (2) 链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。
     (3) 索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。
     (4) 散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)

  • 数据元素的映像：用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点，每个数据项的映象称为数据域。
  • 关系的映像：

    顺序映象：以相对的存储位置表示关系
    链式映象：以附加信息(指针)表示关系

• 运算：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。

  常见的运算：
  (1)建立数据结构 (6)检索*
  (2)清除数据结构 (7)更新
  (3)插入数据元素 (8)判空和判满*
  (4)删除数据元素 (9)求长*
  (5)排序
  *操作为引用型操作，即数据值不发生变化；其它为加工型操作。

1.3 抽象数据类型的表示与实现

---

抽象数据类型 ADT（ Abstract Data Type ）：数据类型概念的引伸。指一个数学模型以及在其上定义的操作集合，与计算机无关。

• 抽象数据类型的描述方法：

  ADT 抽象数据类型名 {
  数据对象：〈数据对象的定义〉
  数据关系：〈数据关系的定义〉
  基本操作：〈基本操作的定义〉
  } ADT 抽象数据类型名

  其中基本操作的定义格式为:

  基本操作名（参数表）
  初始条件：〈初始条件描述〉
  操作结果：〈操作结果描述〉

• 赋值参数：只为操作提供输入值。
• 引用参数：除可提供输入值外，还将返回该参数值在操作后的变化结果
• 初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
• 操作结果：说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

1.4 算法和算法分析：

---

1.4.1 算法

算法：是对特定问题求解步骤的一种描述。
算法是指令的有限序列，其中每一条指令表示一个或多个操作。

1. 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
2. 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
3. 可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
5. 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

1.4.2 算法设计的要求

评价一个好的算法有以下几个标准:

1. 正确性(Correctness)：算法应满足具体问题的需求。
2. 可读性(Readability)：算法应该好读。以有利于阅读者对程序的理解。
3. 健状性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
4. 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。

1.4.3 算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。

一个算法的评价主要从时间复杂度和空间复杂度来考虑。
T(n)表示语句执行的操作数，而O(f(n))是其同量级函数，一般用后者代表时间复杂度。

1.4.4 算法的存储空间的需求

空间复杂度：算法所需存储空间的度量，
记作S(n)=O(f(n))，其中n为问题的规模(或大小)

算法的存储空间：

(1) 输入数据所占空间；
(2) 程序本身所占空间；
(3) 辅助变量所占空间。

可分为：

(1) 固定部分：程序代码，常量，简单变量，定长的结构变量；
(2) 可变部分：与问题规模有关的存储空间。

第二章：线性表

---

待完善

第三章：栈与队列

---

待完善

第四章：串

---

4.1 串的概念和基本操作

---

4.1.1 串的概念

基本术语

• 串（字符串）：由零个或多个字符组成的有限序列。 记作：s = ‘a1a2…an’（n>0）。串是特殊的线性表，数据元素是单个字符。
• 子串：串中任意个连续的字符组成的子序列。
• 主串：包含了字串的串。
• 串相等：两个串长度相等，且对应位置的字符都相等。
• 空串：不包含任何字符的串,表示为Φ。
• 空白串：由一个或多个空格组成的串，如‘ ’。
• 子串的位置：子串的第一个字符在主串中的序号。

4.1.2 串的基本操作

待完善

4.2 串的储存结构

---

待完善

4.3 串的基本操作的实现

---

4.3.1 静态结构存储串时的实现示例

待完善

4.4 串的匹配算法

---

4.4.1 KMP算法

从左到右匹配，原理如下：

KMP算法主体：

int Index_KMP(SString S, SString T, int pos)    //其中S为主串，T为模式串
{                                               //pos为主串开始比较位置
    i = pos;   j = 0;     
    while (i <= S.length && j <= T.length) 
    {
        if (j == -1 || S[i] == T[j]) 
            ++i;  ++j;      //继续比较后继字符
        else
            j = next[j];    //模式串向右移动，匹配模式串下一个可匹配的位置
    }
    if (j > T.length)
        return  i-T.length; //匹配一旦成功，立即返回主串中对应的第一个字符位置
    else
        return -1;          //匹配失败，返回-1
}

可知需求得模式串的next数组。当模式串当前字符匹配失败时，通过next数组可跳过冗余比较，找到下一个可匹配的位置。举例：

j	0	1	2	3	4	5	6	7	8
模式串	a	b	a	a	b	c	a	c	a
next[j]	-1	0	0	1	1	2	0	1	0

下图体现了next[5]与next[7]的逻辑：

求next数组算法：

void get_nextval(SString &T, int &next[]) 
{   
    i = 0;   next[0] = -1;   j = -1; 
    while (i < T.length) 
    {
        if (j == -1 || T[i] == T[j])
        {
            ++i;  ++j;
            next[i] = j;
        }
        else
            j = next[j];    
    }
}

然而，当模式串存在下述情况时：

j	0	1	2	3	4	5
模式串	a	a	a	a	a	b
next[j]	-1	0	1	2	3	4

当该串与形如‘aaaabaaaabaaaaab’的主串进行匹配时，会导致多次冗余重复比较，如下图所示，当第一次比较过后，重复进行了四次相同的无用比较：

因此，需对next数组的算法进行改进，当出现跳转后的字符与跳转前相同时，能够跳过该跳转后字符的比较。

改进后的求next数组算法：

void get_nextval(SString &T, int &nextval[]) 
{   
    i = 0;   next[0] = -1;   j = -1; 
    while (i < T.length) 
    {
        if (j == -1 || T[i] == T[j])
        {
            ++i;  ++j;
            if (T[i] != T[j])
                next[i] = j;
            else
                next[i] = next[j]; 
        }
        else
            j = next[j];    
    }
}

改进后的next数组：

j	0	1	2	3	4	5
模式串	a	a	a	a	a	b
next[j]	-1	-1	-1	-1	-1	4

跳过了重复比较，效率得到极大提高。

4.4.2 BM算法

待完善

第五章：数组和广义表

---

待完善

第六章：树和二叉树

---

待完善

第九章：查找表

---

9.1 概念和术语

---

• 查找表：同一类型的记录(数据元素)的集合。
• 关键字：记录(数据元素)中的某个数据项的值。

  主关键字：该关键字可以唯一地标识一个记录。
  次关键字：该关键字不能唯一标识一个记录。

• 查找：指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值。
• 静态查找表：对查找表的查找仅是以查询为目的，不改动查找表中的数据。
• 动态查找表：在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。
• 查找成功：查找表中存在满足查找条件的记录。
• 查找不成功：查找表中不存在满足查找条件的记录。
• 内查找：整个查找过程都在内存中进行。
• 外查找：在查找过程中需要访问外存。
• 平均查找长度ASL（ Average Search Length ）：查找方法时效的度量。

  ASL计算方法：$ ASL = \sum\limits_{i=1}^n {p_ic_i} $ 且 $ \sum\limits_{i=1}^n {p_i} = 1 $
  n：记录的个数
  pi：查找第i个记录的概率 ( 不特别声明时认为等概率 pi =1/n )
  ci：找到第i个记录所需的比较次数

9.2 静态查找表

---

9.2.1 顺序表的查找

$ ASL = \sum\limits_{i=1}^n {p_ic_i} = \frac{n+1}{2} $

9.2.2 有序表的查找

$ ASL = \frac{1}{n}\sum\limits_{i=1}^h {j*2^{j-1}} = \frac{n+1}{n}\log_2{(n+1)}-1 \approx \log_2(n+1)-1 $
其中 $ h = \lfloor \log_2{n} \rfloor + 1 $

利用折半查找加快效率，学习判定树的画法。

9.2.3 静态树表的查找

1.静态最优查找树

定义：查找性能最佳的树。
性质：带权内路径长度之和PH为最小值。

2.静态次优查找树

优点：PH值近似最小，且比静态最优查找树易于构造，时间开销少
构造方法：通过令每一个非叶子节点左右子树的权重尽可能相等来构造。
查找性能：比较次数不超过树的深度 $O(\log_2{n})$。
查找步骤：设给定的查找值为K，将根节点作为起始节点。

(1) 若当前指针为NULL，则返回空指针；
(2) 若当前指针不为NULL，则将该节点关键字key与K比较：

若K = key，则返回当前节点指针；
若K > key，则将其左孩子作为当前节点，转(1)；
若K < key，则将其右孩子作为当前节点，转(2)。

9.2.4 索引顺序表的查找

分块查找步骤：

(1) 折半或者顺序查找索引表，确定所在块；
(2) 在已确定的块中顺序查找/折半查找；

设b为索引表长度，s为块中记录个数
$ ASL = \frac{1}{b}\sum\limits_{i=1}^b{i} + \sum\limits_{j=1}^s{j} = \frac{1}{2}(b+s)+1 = \frac{1}{2}(\frac{n}{s}+s)+1 $
可知 $s$ 取 $\sqrt{n}$ 时，$ASL$ 取最小值 $\sqrt{n}+1$。

分块查找效率介于顺序查找和折半查找之间。

9.3 动态查找表

---

9.3.1 二叉排序树BST(二叉查找/搜索树)

• 定义：二叉排序树或者是空树，或者是满足如下性质的二叉树：

  (1) 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  (2) 若其右子树非空，则右子树上所有结点的值均大于根结点的值；
  (3) 其左右子树本身又各是一棵二叉排序树。

• 性质：中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列。
• 操作：通常取二叉链表进行操作。

  (1) 查找

  Bitree  SearchBST ( BiTree T,  KeyType key )
  // 在二叉排序树T中查找关键字值为 key 的结点，
  //找到返回该结点的地址，否则返回空。
  {  
      if  (!T || EQ(key, T->data.key)) 
              return (T) ;
      else if(LT(key,T->data.key)) 
             return SearchBST(T->lchild,key);
      else 
             return SearchBST(T->rchild,key); 
   }

  (2) 插入

  Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)
  //f指向当前结点的双亲,初始调用值为NULL。
  //查找成功，p指向该结点，并返回TRUE；
  //查找失败，p指向查找路径上的最后一个结点，并返回FALSE
  {  
      if (!T)  {p=f;  return FALSE;}
      else if (EQ(key, T->data.key)) {  p=T; return TRUE; }  
      else if (LT(key, T->data.key))  
          return SearchBST(T->lchild, key, T, p );
      else
          return SearchBST(T->rchild, key, T, p);
  }
  
  Status InsertBST (BiTree &T,ElemType e) 
  {
      if (!SearchBST(T, e.key, NULL, P))
      {
          s=(BiTree)malloc(sizeof(BiTNode));
          s->data=e;
          s->lchild=s->rchild=NULL;
          if (!T)
              T=s;
          else if (LT(e.key, p->data.key))
              p->lchild = s;
          else
              p->rchild = s;
          return TRUE;
      }
      else
          return FALSE;
  }

  (3) 生成：从空树出发，反复调用插入操作InsertBST。
  (4) 删除：

  p是叶子结点：修改其双亲指针;
  p只有左孩子：用p的左子树代替以p为根的子树;
  p只有右孩子：用p的右子树代替以p为根的子树;
  p有两个孩子：找到p的中序后继(或前趋)结点q，将q的数据复制给p，再删除只有右孩子(或左孩子)/无孩子的q。
  

• 性能分析：

  最差(单支树)：$ \frac{n+1}{2} $
  最好(类似折半查找的判定树)：$ \log_2{(n+1)}-1 $
  随机：$ \leq 4\log_2{n} $

可知为避免二叉排序树“退化”，采用平衡二叉树。

9.3.2 平衡二叉树(AVL树)

• 定义：或者是空树，或者是满足如下性质的二叉排序树：

  (1) 它的平衡因子的绝对值不超过1；
  (2) 其左右子树本身又各是一棵平衡二叉树。
  平衡因子：该结点的左子树高度减去右子树的高度。

• 节点存储结构：
• 定理：平均查找长度与 $ log_2{n} $ 同数量级。
• 操作

  1. 查找：同二叉排序树。
  2. 插入：利用平衡旋转技术。

     (1) LL型平衡旋转 —— 单向右旋（一次顺时针旋转）
     
     (2) RR型平衡旋转 —— 单向左旋（一次逆时针旋转）
     
     (3) LR型平衡旋转 —— 一次逆时针旋转 + 一次顺时针旋转
     
     (4) RL型平衡旋转 —— 一次顺时针旋转 + 一次逆时针旋转
     

9.3.3 B-树 (B-tree，B即balanced)

• 定义：一棵m阶B-树，或为空树，或为满足下列特性的m叉树：

  1. 树中每个结点最多有 m 棵子树；
  2. 若根结点不是叶子结点，则最少有两棵子树；
  3. 除根之外的所有非叶子结点最少有 $ \lceil \frac{m}{2} \rceil $ 棵子树；
  4. 所有非叶子结点包含 （n,A0,K1,A1,K2,…,Kn,An）信息数据；其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。
  5. 所有叶子结点在同一层上，且不带信息。

• 查找：设查找时给定值为K，从根结点开始。

  (1) 在当前结点*p中顺序或者折半查找，若找到某个i，满足key[i]=K，则查找成功，返回p、i、1，否则，确定满足key[i]<K<key[i+1]的i值；
  (2) 若*p结点中的ptr[i]为空指针，则查找失败，返回p、i、0；
  (3) 从磁盘上读入ptr[i]指示的结点 DiskRead(p->ptr[i])，将此结点作为当前结点，转(a)。

• 插入：插入至叶节点的$ \lceil \frac{m}{2} \rceil $处，当节点关键字达到 m 个时分裂。若由底向上至根结点仍需分裂时，需要构造新的根结点，B-树会增加一层。

  

• 生成：从空树起，逐个插入关键字得到。
• 删除：分三种情况。

  
  
  

9.3.4 B+树

是B-树的变形。有 n 棵子树的结点中有 n 个关键字；非叶结点保存的可以看成是索引集，即下一个节点内最大的数，而叶节点内保存的是数据集。

各操作与B-树相同。

9.3.5 键树(数字查找树/字符树)

将关键字分解为字符的多叉树，多叉树中的每个结点只代表关键字中的一个字符，叶结点用于表示字符串的结束符(如‘$’)。

9.4 哈希表

---

9.4.1 基本术语

• 哈希表：一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。
• 哈希函数：记录的存储位置与它的关键字之间存在的一种对应关系。 $ Location = H(key) $
• 冲突：对于 $key_i \neq key_j$ ，$i \neq j$ ，出现的 $H(key_i) = H(key_j)$的现象。
• 同义词：在同一地址出现冲突的各关键字。
• 哈希(散列)地址：根据设定的哈希函数$H(key)$和处理冲突的方法确定的记录的存储位置。
• 装填因子：表中填入的记录数 n 和哈希表表长 m 之比。
  $\alpha=\frac{n}{m}$

9.4.2 哈希函数的基本构造方法

待完善

第十章：内部排序

• 排序算法的约定：
  1. 待排序的数据结构为顺序存储；
  2. 关键字为整数，递增排列；
  3. 前置数据定义如下：

     #define MAXSIZE 20  //待排序元素最大个数
     typedef int KeyType;    //定义待排序元素的关键字的数据类型为整型
     typedef struct 
     {
     	KeyType key;        //待排元素的关键字
     	InfoType otherinfo;	//待排元素的其他信息
     } RedType;  //待排元素
     typedef struct
     {
     	RedType r[MAXSIZE+1];  //r[0]闲置或作哨兵
     	int length;     //待排元素个数
     }SqList;    //保存待排元素的列表，对其中的数组进行排序

---

10.1 概述

---

10.2 插入排序

---

10.2.1 直接插入排序（增量法）

• 是一种稳定排序。

• 算法思想：每次排序在有序区（红框）中增加一个记录，进行n-1次。

• 哨兵的作用：简化边界条件的测试，提高算法时间效率。

  • 没有哨兵，则每次比较后都需将两个相邻元素进行交换，共需要进行 3n 次操作；
  • 有哨兵，在起始时将待排元素放入哨兵，每次比较后只需将另一个元素后移一位，最后将哨兵填入其中，共需要进行 n+2 次操作。

void InsertSort (SqList &L)
{   
    int i,j;
    for (i=2; i<=L.length; i++) //从第二个元素开始
        if (Less(L.r[i].key,L.r[[i-1].key))  //当第i个元素的关键字小于第i-1个元素的关键字
        {
            L.r[0] = L.r[i];    //将第i个元素放入哨兵
            L.r[i] = L.r[i-1];  //将第i-1个元素向后移动一位
	        for (j=i-2; L.r[0].key < L.r[j].key; j--)   //从第i-2个元素开始往前遍历
                L.r[j+1] = L.r[j];   //当第j个元素的关键字大于哨兵的关键字时，第j个元素向后移动一位
            L.r[j+1] = L.r[0];  //此时j是最后一个移动的元素原位置的下标
        }                       //将哨兵元素放入其中，其关键字大于前一个小于后一个
}

• 性能分析：
  • 最好情况（元素按正序排列）：

    比较次数 $C_{min} = \sum\limits_{i=2}^{n}{1} = n-1$
    移动次数 $M_{min} = 0$

  • 最坏情况（元素按逆序排列）：

    比较次数 $C_{max} = \sum\limits_{i=2}^{n}{i} = \frac{(n+2)(n-1)}{2}$
    移动次数 $M_{max} = \sum\limits_{i=2}^{n}{(i-1+1+1)} = \sum\limits_{i=2}^{n}{(i+1)} = \frac{(n+4)(n-1)}{2}$

  • 平均情况：

    比较次数 $C_{avg} = \frac{1}{2}(C_{min}+C_{max}) \approx \frac{n^2}{2}$
    移动次数 $M_{avg} \approx \frac{n^2}{2}$

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$（就地排序）

10.2.2 希尔排序（浅减/缩小增量排序）

• 是一种不稳定排序。

• 同样需要一个哨兵。

• 算法思想：选定一个下标的增量d，将整个序列按增量d从第一个记录开始划分为若干分序列，对每个分序列进行直接插入排序。然后减小增量d，不断重复上述过程。如此下去，直到d=1(此时整个序列是一组)。

void ShellSort (SqList &L, int delta[ ], int t)
//按增量序列dlta[0..t-1]对顺序表L作希尔排序
{  
    for(k = 0; k < t; k++) //将整个序列划分为delta[k]个分序列，对每个分序列进行直接插入排序。共进行t次
    {
        dk = delta[k];   //增量序列函数，如: ……15,7,3,1 
        for (i=dk+1; i <=L.length; i++) //对每个分序列从第二个元素开始，进行直接插入排序
            if (L.r[i].key < L.r[i-dk].key)     //当前分序列的第n个元素的关键字小于第n-1个元素的关键字时
            {
                L.r[0] = L.r[i];      //r[i]需进行插入排序，暂存在哨兵
                for (j=i-dk; j>0 && L.r[0].key <L.r[j].key; j -= dk)    //往前遍历
                    L.r[j+dk] = L.r[j];//当前元素的关键字大于哨兵的关键字时，该元素在其所在分序列向后移动一位
                r[j+dk] = r[0];       //将哨兵元素放入其中，其关键字大于前一个小于后一个
            }
    }
}

• 性能分析：
  • 如何选择更好的delta序列：
    • 最后一个增量必须为1；
    • 尽可能令增量序列的值互质（尤其是相邻的值）。
  • 当n较大时：

    • 比较次数 $C_{avg} \approx a*n^{1.25},1<a<1.6$
    • 移动次数 $M_{avg} \approx a*n^{1.25},1<a<1.6$

  • 时间复杂度：取决于n和delta序列
  • 空间复杂度：$O(1)$（就地排序）

10.3 交换排序

---

10.3.1 冒泡排序

• 是一种不稳定排序。

• 算法思想：将两个相邻记录的关键字进行比较，若为逆序则交换两者位置，抓住大者往下沉，则相对地小者便会往上浮。

void bubbleSort(SqList &L)
{
    n = L.length;   //记录n为待排序列长度
    sorted = FALSE; //将标志排序完毕的标记初始化为FALSE
    for(i = 0; i < n-1 && !sorted; i++)
    {
        sorted = TRUE;  //若之后未能找到一对逆序记录，则排序完毕
        for(j = 0; j < n-i; j++)    //此时已沉底了i个元素
            if(L.r[j].key > L.r[j+1].key)   //若相邻元素前者关键字大于后者关键字
            {
                Switch(L.r[j], L.r[j+1])   //交换相邻元素，即将大者往下沉
                sorted = FALSE;     //找到了一对逆序记录，尚未排序完毕
            }
    }
}

• 性能分析：

  • 最好情况（元素按正序排列）：

    • 比较次数 $C_{min}=n-1$
    • 移动次数 $M_{min}=0$

  • 最坏情况（元素按逆序排列）：

    • 比较次数 $C_{max}=\sum\limits_{i=1}^{n-1}{(n-i)}=\sum\limits_{i=1}^{n-1}{i}=\frac{n(n-1)}{2}$
    • 移动次数 $M_{max}=3\sum\limits_{i=1}^{n-1}{(n-i)}=3\sum\limits_{i=1}^{n-1}{i}=\frac{3n(n-1)}{2}$（交换需要三次）

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$（就地排序）

• 算法改进：

  • 每次循环记录最后一次交换的位置，可知之后的已经排好序了；
  • 双向交替扫描，改进数据不对称性。即沉底一次，升顶一次。

10.3.2 快速排序（分划交换排序/分治法）

• 是一种不稳定排序。

  • 反例：序列[2,2,1]

• 算法思想：指定枢轴r[p]（通常为第一个记录），通过一趟排序将其放在一个位置，该位置满足
  $左边记录的关键字\leq r[p].key\leq右边记录的关键字$
  对左右部分记录重复上述过程，直到子序列只剩一个记录或不剩记录为止。

void quikSort(SqList &L)    //包装函数
{
    qSort(L,1,L.length);
}

void qSort(SqList &L, int low, int high)    //递归排序
{
    if(low < high)
    {
        pivotLoc = partition(L,low,high);   //将首元素排序到枢纽位置，并返回该位置
        qSort(L,low,pivotLoc-1);            //递归是串行执行
        qSort(L,pivotLoc+1,high);
    }
}

int partition(SqList &L, int low, int high) 
{//将该序列首元素置于比前方所有元素的值大，比后方所有元素的值小的位置
    L.r[0] = L.r[low];          //首元素放入哨兵
    pivotKey = L.r[low].key;    //记录首元素的值
    while(low < high)           //通过对序列元素位置进行一定交换，找到该位置
    {                           //无论何时，不动的那个指向的总是原来的首元素
        while(low < high && L.r[high].key > pivotKey)
            high--;
        L.r[low] = L.r[high]; 
        while(low < high && L.r[low].key < pivotKey)
            low++;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];  //将哨兵置于枢纽位置
    return low;         //返回该位置
}

• 性能分析：

  • 最好情况：每次划分出的左右两个子序列长度基本相等，即原序列越无序情况越好

    • 比较次数 $C_{min}\leq O(nlog_2{n})$
    • 移动次数 $M_{min}\leq C_{min}$

  • 最坏情况：原始数据正、逆序排序，即原序列越有序情况越坏

    • 比较次数 $C_{max}=\sum\limits_{i=1}^{n-1}{(n-i)}=\sum\limits_{i=1}^{n-1}{i}=\frac{n(n-1)}{2}$
    • 移动次数 $M_{max}\leq C_{max}$

  • 平均情况：$O(nlog_2{n})$
    • 就平均时间而言，目前快速排序被认为是最好的内部排序法。
  • 空间复杂度：
    • 最好情况：$O(log_2{n})$
    • 最坏情况：$O(n)$

• 算法改进：合理选择枢轴记录。

  • 三者取中
  • 随机产生

10.4 选择排序

---

10.4.1 简单选择排序（直接选择排序）

• 是一种不稳定排序。

• 算法思想：每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止。

void selectSort(SqList &L)
{
    for(i = 0; i < L.length; i++)   //遍历序列n次，n为序列长度
    {
        minLoc = i;
        for(k = i+1; k <= L.length; k++)        //当前已排序了i个元素
            if(L.r[minLoc].key > L.r[k].key)    //若存在元素比第i个元素更小
                minLoc = k;    //重复多次将minLoc设置为当前关键字最小的元素下标
        if(i != min)
            switch(L.r[i],L.r[minLoc]);     //将更小的元素交换到前面
    }
}

• 性能分析：
  • 比较次数只与序列长度n有关：$C=\sum\limits_{i=1}^{n-1}{(n-i)}=\sum\limits_{i=1}^{n-1}{i}=\frac{n(n-1)}{2}$
  • 移动次数：

    最好情况：$M_{min}=0$
    最坏情况：$M_{max}=3(n-1)$

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$（就地排序）

10.4.2 树形选择排序（锦标赛排序）

• 是一种稳定排序。

• 算法思想：每次进行一次排序后把树顶端元素选出，将树中对应选出的叶子节点设为$\infty$，之后再继续排序，直到所有叶子节点都被设置为$\infty$。

……

• 性能分析：
  • 时间复杂度：$O(nlog_2n)$
  • 空间复杂度：有点小多
  • 需与“最大值”进行多余的比较

10.4.3 堆排序

• 小根堆：每个节点都比左右孩子小

• 大根堆：每个节点都比左右孩子大

• 是一种不稳定排序。

• 算法思想：首先将初始文件建成长度为 n 的大根堆，之后每次排序将堆顶元素与最后一个元素交换后，再将前 n-1 个元素调整为堆，重复 n-1 次。

typedef  SqList   HeapType;

void HeapSort(HeapType &H)  //第一个元素啥也不放
{  
    for (i = H. length / 2; i > 0; i--)   //对所有的非叶子节点，从序号最大的开始依次调整为堆
        HeapAdjust(H, i, H.length);
    for (i=H.length; i>1; i--) 
    {
        Switch(H.r[1],H.r[i]);  //交换栈顶元素和最后一个元素
        HeapAdjust(H, 1, i-1);  //下沉现在的栈顶元素，使之重新成堆
    }
}//HeapSort

void HeapAdjust(HeapType &H, int s, int m)  //将标号为s的节点下沉到不能再沉
{  
    rc=H.r[s];      //取根节点元素
    for (j=2*s;j<=m;j*=2)   //取左孩子
    {
        if (j<m && H.r[j].key < H.r[j+1].key)   //如果左孩子已经是最后一个元素，或没有孩子，则跳过该步
            j++;    //若右孩子的关键字大于左孩子的关键字，则取右
        if (rc.key > H.r[j].key) //若根节点的关键字大于该孩子的关键字
            break;   //退出循环
        H.r[s] = H.r[j];    //将该孩子放在父亲的位置
        s=j;    //现在父亲的位置变成该孩子原来的位置
    }
    H.r[s]=rc;  //将根节点放入最终位置
}//HeapAdjust

• 性能分析：
  • 时间复杂度：

    最好情况：$O(nlog_2n)$
    最坏情况：$O(nlog_2n)$
    平均情况：$O(nlog_2n)$

    • 平均性能接近于最坏性能
    • 建初始堆时，比较次数$\leq 4n$
    • 反复调整堆时，比较次数$<2n\lfloor log_2n \rfloor$

  • 空间复杂度：$O(1)$
  • 对记录大的文件很有效

10.5 归并排序

---

10.5.1 两路归并排序

• 是一种稳定排序。

• 算法思想：首先将待排序列看作 n 个长度为 1 的有序子序列，之后每趟排序两两归并，并保证每次排序后每个子序列内部有序，直到合并为一个序列为止。

//递归算法
void MergeSort(SqList &L)	 //包装函数 第一个元素也是啥也不放
{   
    Msort ( L.r, L.r, 1, L.length )  ；
}//MergeSort

void MSort( RedType SR[], RedType &TR1[], int s, int t  )
// 将 SR[s..t] 归并排序为 TR1[ s..t]
{  
    RedType TR2[t+1-s];     //自下而上的排序

    if( s == t )   
        TR1[s] = SR[s];
    else  
    { 
        m = ( S+ t)/2 ; // 将SR[s..t]分为SR[s..m]和SR[m+1..t]
        Msort(SR,TR2, s,m); // 将SR[s..m]归并为有序的TR2[s..m]
        Msort(SR,TR2,m+1, t);// 将SR[m+1..t]归并为有序的TR2[m+1..t] 
        Merge(TR2,TR1,s,m, t);// 将TR2[s..m]和TR2[m+1..t] 归并到TR1[s..t]
    } 
}//MSort

void Merge(RedType SR[ ], RedType &TR[], int i, int m, int n)
{       //此时的SR，前一半和后一半是不相干的有序序列   
    for (j=m+1, k=i; i<=m && j<=n; k++)    
    {   //每次比较两个序列的当前元素，把关键字较小的元素插入TR
        if ( SR[i].key <= SR[j].key)
            TR[k] = SR[i++];    //若插入了前一半序列的当前元素，则i++
        else 
            TR[k] = SR[j++];    //若插入了后一半序列的当前元素，则j++
    }
    if (i<=m) 
        TR[k..n] = SR[i..m];    //若后一半插完了，则把前一半剩下的插进去
    if (j<=n)  
        TR[k..n] = SR[j..n];    //若前一半插完了，则把后一半剩下的插进去
}//Merge

//非递归算法
void  MergeSort (SqList &L)     //第一个元素啥也不放
{    
    len =1; 
    n= L.Length;
    while ( len < n ) 
    {
        s1= 1;  
        while  (s1 + len <= n)  // 其实就是上一次的 t2+1+len > n 则退出循环（第n个元素肯定被排过序了）
        {
            t1 = s1 +len - 1;   //开始元素
            t2 = t1 + len;      //结束元素
            if (t2 > n)     //如果超过总长度，则设置为总长度
                t2 = n;
            Merge ( L.r, TR, s1, t1, t2);    //Merge还是那个Merge
            s1 = t2+1;
        }
        for  (i = 1; i<s1; i++)    //将第一个元素到当前最后一个元素从TR搬回L
            L.r [ i ] = TR[ i ];
        len = len*2;
      }
}//MergeSort

10.5.2 自然两路归并排序

• 是一种不稳定排序。

• 特点：比直接两路归并更有效

• 算法思想：左右往中间走的同时进行归并，碰到比当前元素小的元素便停下，当左右都停下时完成一个归并。归并按照左一个右一个的顺序放置，两边小中间大。

10.6 基数排序

• 是一种稳定排序。

• 算法思想：好长不想写，代码也不想写，看图理解

• 性能分析：
  • 时间复杂度：
    • 每趟：分配$O(n)$ ，收集 $O(rd)$
    • d趟总计：$O(d(n+rd))$
    • 总时间复杂度：$O(n)$
  • 空间复杂度：$O(rd+n)$

10.7 各种内部排序方法的比较

排序方法	最好时间	平均时间	最坏时间	辅助空间	稳定性
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	√
希尔排序		$O(n^{1.3})$		$O(1)$	×
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	√
快速排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	×
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	×
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	×
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	√
基数排序	$O(d(rd+n))$	$O(d(rd+n))$	$O(d(rd+n))$	$O(rd+n)$	√

• 按平均时间排序分为四类：$O(n^2)、O(nlog_\epsilon{n})、O(n^{1+\epsilon})、O(n)
  $

• 选择排序方法应综合考虑各因素

  • 快速排序是基于比较的内部排序中最好的方法
  • 关键字无序分布时，快速排序需要的时间最短，堆排序次之，但后者空间复杂度低
  • 当$n$较小时（$n<50$），可直接采用直接插入排序或简单选择排序，前者是稳定排序，但后者通常记录移动次数少于前者
  • 当$n$较大时，应采用时间复杂度为$O(nlog_\epsilon{n})$的排序方法（主要为快速排序和堆排序）或者基数排序的方法，但后者对关键字的结构有一定要求
  • 当n较大时，为避免顺序储存时大量移动记录的时间开销，可考虑用链表作为存储结构（如插入排序、归并排序、基数排序）
  • 快速排序和堆排序难于在链表上实现，可以采用地址排序的方法，之后再按辅助表的次序重排各记录
  • 序列初态基本按正序排列时，应选用直接插入排序、冒泡排序、随机的快速排序

待完善