第二章线性表

About 57 min

第二章线性表

第一节线性表的定义和基本操作

线性表的基本操作
InitList(&L) 初始化表。构造一个空的线性表。
Length(L) 求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e) 按值查找。在L中查找具有给定关键字值的元素。
GetElem(L,i) 按位查找。获取表L中第i个位置的元素的值。
ListInsert(&L, i, e) 插入操作。在L中的第i个位置插入指定的元素e。
ListDelete(&L, i, &e) 删除操作。删除L中第i个位置上元素，用e返回被删除元素的值。
PrintList(L) 输出操作。顺序输出L中所有元素值。
Empty(L) 判空操作。若L为空表，返回true，否则返回false。
DestoryList(&L) 销毁操作。销毁线性表，并释放所占用的内存空间。
注意：i是位序，其数值从1开始，而数组下标从0开始。

第二节线性表的顺序表示

一、顺序表的定义

1. 静态分配

#define MaxSize 10              // 最大长度
typedef struct{
    ElemType data[MaxSize];     // 使用静态数组存放数据元素
    int length;                 // 当前长度
}SeqList;

//初始化一个顺序表
SeqList L;
void InitList(SeqList &L){
    for(int i = 0; i < MaxSize; i++)
        L.data[i] = 0;			// 内存中含有之前遗留的脏数据
    L.length = 0;
}

2.动态分配

#define InitSize 10     // 初始长度
typedef struct{
    ElemType *data;     // 动态分配空间的起始地址指针
    int MaxSize;        // 最大容量
    int length;         // 当前长度
}SeqList;

// 初始化顺序表
SeqList L;
void InitList(SeqList &L){
    L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);    //   L.data = new ElemType[InitSize];
    L.length = 0;
    L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
    int *old = L.data;  // 暂存旧数据
    L.data = (ElemType *)malloc((L.MaxSize+len)*sizeof(ElemType));	
    for(int i = 0; i < L.length; i++)	  
        L.data[i] = old[i];     // 复制旧数据
    L.MaxSize = L.MaxSize+len;  // 调整长度
    free(old);  // 释放旧数据
}

二、顺序表的基本操作

1. 插入

// 在顺序表的第i个位置插入指定元素e。
bool ListInsert(SqList &L, int i, ElemType e){     // i: 第i个位置，合法范围 [1, length]
    if(i < 1 || i > L.length+1) 
        return false;
    if(L.length >= MaxSize) 
        return false;
    for(int j = L.length; j >= i; j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    return true;
}

2. 删除

// 删除L中第i个位置上元素，用e返回被删除元素的值。
bool ListDelete(SeqList &L, int i, ElemType &e){
    if(i < 1 || i > L.length)
        return false;
    e = L.data[i-1];
    for(int j = i; j < L.length; j++)   // i位置之后的元素整体向前移动1个位置
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}

3. 按位查找

// 获取表L中第i个位置的元素的值。	时间复杂度O(1)
ElemType GetElem(SeqList L,int i){
    if(i < 1 || i > L.length)
        return -1;
    return L.data[i-1];
}

4. 按值查找

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序。
int LocateElem(SeqList L, ElemType e){
    for(int i = 0; i < L.length; i++)
        if(L.data[i] == e)
            return i+1;
    return 0;
}

三、顺序表完整操作

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10

typedef struct {
    int *data;
    int MaxSize;
    int length;
}SeqList;

bool InitList(SeqList &L){
    L.data = (int *)malloc(sizeof(int)*InitSize);
    if(L.data == NULL)
        return false;
    for(int i = 0; i < InitSize; i++)
        L.data[i] = 0;
    L.length = 0;
    L.MaxSize = InitSize;
    return true;
}

bool IncreaseSize(SeqList &L,int len){
    int *p = L.data;
    L.data = (int *)malloc(sizeof(int)*(L.MaxSize+len));
    if(L.data == NULL)
        return false;
    L.MaxSize += len;
    for(int i = 0; i < L.length; i++)
        L.data[i] = p[i];
    free(p);
}

int Length(SeqList &L){
    return L.length;
}

int LocateElem(SeqList L,int e){
    for(int i = 0; i < L.length; i++)
        if(L.data[i] == e)
            return i+1;
    return -1;
}

int GetElem(SeqList L,int i){
    if(i < 1 || i > L.length)
        return false;
    return L.data[i-1];
}

bool ListInsert(SeqList &L, int i, int e){
    if(i < 1 || i > L.length+1)  
        return false;
    if(i >= L.MaxSize)
        return false;
    for(int j = L.length; j >= i; j--)  // 写法不唯一
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    return true;
}

bool ListDelete(SeqList &L, int i, int &e){
    if(i < 1 || i > L.length)
        return false;
    e = L.data[i-1];
    for(int j = i-1; j <= L.length-1; j++)	// 写法不唯一
        L.data[j] = L.data[j+1];
    L.length--;
    return true;
}

void DestroyList(SeqList &L){
    free(L.data);
    L.data = NULL;
    L.length = 0;
    L.MaxSize = 0;
}

void PrintList(SeqList L){
    for(int i = 0; i < L.length; i++)
        printf("data[%d]=%d\t", i, L.data[i]);
}

int main(){
    SeqList L;          
    InitList(L);             
    IncreaseSize(L,10);
    ListInsert(L,1,11);			
    ListInsert(L,2,22);      
    ListInsert(L,3,33);  			
    ListInsert(L,4,44);

    int e = -1;        
    e = LocateElem(L, 33);     
    printf("元素33所在的位序为: %d\n", e);

    e = GetElem(L, 3);   
    printf("位序为3的元素为: %d\n", e);

    ListDelete(L, 2, e);  
    PrintList(L);
    DestroyList(L);

    return 0;
}

第三节单链表

一、单链表的定义和初始化

1. 单链表定义

struct LNode{
    ElemType data;          // 存放当前结点的数据元素
    struct LNode *next;     // next指针指向下一个结点
};
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

// 可以使用typedef定义别名，简化名称。
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// typedef struct LNode LNode;
// typedef struct LNode *LinkList;

// 两者等价，不同的地方使用合适的名字，可读性更强
LNode* L;       // 强调这是一个结点
LinkList L;     // 强调这是一个单链表

LNode* GetElem(LinkList L, int i){      // 按序号查找结点值
    if(i < 1){
        return NULL;
    }else{
        int j = 1;
        LNode *p = L;
        while(p != NULL && j < i){
            j++;
            p = p->next;
        }
        return p;
    }
}

2. 单链表初始化

（1）不带头结点单链表的初始化

// 初始化
void InitList(LinkList &L){
    L = NULL;         // 空表，没有任何结点，防止内存中的脏数据
}

// 判断不带头节点的单链表是否为空
bool Empty(LinkList L){
    return (L == NULL);
}

（2）带头结点的单链表的初始化

bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));   		// 分配头结点
    if(L == NULL)           	  // 分配失败
        return false;
    L->next = NULL;           // 头结点的后继节点置空
    return true;
}

// 带头结点的单链表判空
bool Empty(LinkList L){
    return (L->next == NULL);
}

二、单链表的基本操作

单链表的插入（1）按位序插入（带头结点） ListInsert(&L,i,e) //插入操作。在表L中的第i个位置上插入指定元素e。 //找到第i-1个结点，将新结点插入其后。

//在第i个位置插入元素e（带头结点） //头结点视为第0个位置 bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) // 位序不合法 return false; int j = 0; LNode *p = L; while(p!=NULL && j<i-1){ // 找到第i-1个结点 p = p->next;
j++; } if(p==NULL) // 不存在第i-1个结点 return false; LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true; }

（2）按位序插入（不带头结点） //在第i个位置插入元素e（不带头结点） bool ListInsert2(LinkList &L,int i,ElemType e){ if(i<1) return false; else if(i==1){ L = (LNode *)malloc(sizeof(LNode)); if(L==NULL) return false; L->data = e; L->next = NULL; return true; }else{ int j = 1; LNode *p = L; while(p!=NULL && j<i-1){ p=p->next; j++; } if(p==NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; s->data = e; s->next = p->next; p->next = s; return true; } }

（3）指定结点的后插操作 //后插操作：在p结点之后插入元素e bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) return false; LNode s = (LNode)malloc(sizeof(LNode)); if(s==NULL) return false; s->data = e; s->next = p->next; p->next = s; return true; }

//可以将之前的在第i个位置插入元素e（带头结点）使用InsertNextNode这个函数进行封装 bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1)
retuen false; LNode *p;
int j=0;
p=L;
while(p!=NULL&&j<i-1){
p=p->next; j++; }

return InsertNextNode(p,e);

}

（4）指定结点的前插操作 //前插操作：在p结点之前插入元素e bool InsertPriorNode(LNode *p,ElemType e) //只能看到后面的，看不到前面的

传入头指针就能解决这个问题，本质上是寻找p的前驱结点，对前驱结点进行后插 bool InsertPriorNode(LinkList L,LNode *p,ElemType e)

// 传入头指针： bool InsertPriorNode(LinkList L,LNode *p,ElemType e){ if(L==NULL || p==NULL) return false; LNode *r = L; while(r->next!=p && r!=NULL) r = r->next; if(r==NULL) return false; LNode s =(LNode)malloc(sizeof(LNode)); s->data = e; r->next = s; s->next = p; return true; }

另外一种解决方法 // 偷天换日：在p后面插入一个新结点，把p中的数据赋给新结点，把元素e赋给p bool InsertPriorNode(LNode *p,ElemType e){ if(p==NULL) return false; LNode s = (LNode)malloc(sizeof(LNode)); if(s==NULL) return false; s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true; }

// 在p结点之前插入一个结点s // 偷天换日：在p后面插入一个新结点s，互换两个结点的数据 bool InsertPriorNode(LNode *p,LNode *s){ if(p==NULL || s==NULL) return false; s->next = p->next; p->next = s; ElemType temp = s->data; s->data = p->data; p->data = temp; return true; }

单链表的删除（1）按照位序删除 ListDelete(&L,i,&e) //删除操作。删除表L中第i个位置的元素，并用e返回被删除的元素值。

// 按照位序删除（带头结点） bool ListDelete(LinkList &L,int i,ElemType &e){ if(i<1 || L==NULL) return false; int j = 0; LNode *r = L; while(r!=NULL && j<i-1){ // 找第i-1个结点 r = r->next; j++; } if(r==NULL || r->next==NULL) // 第i-1个结点不存在 || 删除的恰好是表长+1的情况 return false; LNode *temp = r->next; e = temp->data; r->next = temp->next; free(temp); return ture; }

// 按照位序删除（不带头结点） bool ListDelete2(LinkList &L,int i,ElemType &e){ if(i<1 || L==NULL) return false; else if(i==1){ e = L->data; LNode *temp = L; L = L->next; free(temp); return true; }else{ int j = 1; LNode *r = L; while(r!=NULL && j<i-1){ r = r->next; j++; } if(r==NULL || r->next==NULL) // 第i-1个结点不存在 || 删除的恰好是表长+1的情况 return false; LNode *temp = r->next; e = temp->data; r->next = temp->next; free(temp); return ture; } }

（2）指定结点的删除 //删除指定结点p bool DeleteNode(LNode *p) 同样存在没办法找到前驱结点的问题，使用同样的方法：方法1：传入头指针，循环寻找p的前驱结点方法2：偷天换日

// 传入头指针，找前驱结点 bool DeleteNode(LinkList L,LNode *p){ if(L==NULL || p==NULL) return false; LNode *r = L; while(r!=NULL && r->next!=p) r = r->next; if(r==NULL) return false; r->next = p->next; free(p); return true; }

// 偷天换日把p节点后面一个结点q的值移到p内，转换为q的删除 bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *r = p->next; p->next = r->next; p->data = r->data; free(r); return true; } //此方法存在的问题：如果p刚好是最后一个结点，p->next->data就会出错了。

单链表的查找 GetElem(L,i) 按位查找。获取表L中第i个位置元素的值。 LocateElem(L,e) 按值查找。在表L中查找具有给定关键字值的元素。

（1）GetElem(L,i) 按位查找 //按位查找，返回第i个元素（带头结点） LNode* GetElem(LinkList L,int i){ if(i<0) return NULL; int j = 0; LNode *p = L; while(p!=NULL && j<i){ p = p->next; j++; } return p; } // 和之前插入删除的一部分代码相同，只需把i-1改成i （删除是找前驱结点，所以是i-1） // 边界情况： i<0 return NULL i=0 while(0<0) p不动 return p (p=L) i过大 p=NULL return p (p=NULL)

第二种写法 //按位查找，返回第i个元素（带头结点） LNode* GetElem(LinkList L,int i){ if(i<0) return NULL; else if(i==1) return L; else{ int j = 1; LNode *p = L->next; while(p!=NULL && j<i){ p = p->next; j++; } return p; } }

之前按位插入，按位删除都可以使用这个封装好的函数
//将if(i<1) return false;后面的到if(p==NULL)前面的替换成下面这个 LNode *p=GetElem(L,i-1); //找到第i-1个结点同样，按位插入后面的也可用封装好的InsertNextNode替换

//在第i个位置后面插入元素e bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; LNode *p=GetElem(L,i-1); return InsertNextNode(p,e); }

问题：为什么InsertNextNode要对p判空？ // bool InsertNextNode (LNode *p,ElemType e){ // if(p==NULL) // return false; 因为在上面封装好的例子中，如果i的范围不合法，比如过大，GetElem()会返回一个NULL，此时如果传给InsertNextNode，会出错。

（2）LocateElem(L,e) 按值查找 //按值查找，找到数据域==e的结点 LNode* LocateElem(LinkList L,ElemType e){ LNode *p = L->next; while(p!=NULL && p->data!=e) p = p->next; return p; }

（3）求表的长度计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。算法的时间复杂度为O（n）。 int Length(LinkList L){ int len = 0; LNode *p =L; while(p->next!=NULL){ p = p->next; len++; } return len; } //注意：此处是p->next!=NULL。如果改为p!=NULL，p指向最后一个结点的首地址时，下面还会再执行一次才退出，len会多1

4.单链表的建立（尾插法、头插法）（1）尾插法建立单链表 //如果调用按位插入，会从表头遍历，每次插入一个元素，链表长度+1，遍历的次数会越来越多O(n^2) //可以用一个指针指向尾部，每次插入使用尾插法

// 尾插法建立单链表 LinkList List_TailInsert(LinkList &L){ L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; LNode *tail = L; // tail相当于一个游标，始终指向表尾 LNode s; int x; scanf("%d",&x); while(x!=9999){ s = (LNode)malloc(sizeof(LNode)); s->data = x; s->next = tail->next; tail->next = s; tail = s; scanf("%d",&x); } tail->next = NULL; return L; }

（2）头插法建立单链表 //可以理解为对指定结点（头结点）的后插操作 // 头插法建立单链表 LinkList List_HeadInsert(LinkList &L){ L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; LNode s; int x; scanf("%d",&x); while(x!=9999){ s = (LNode)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d",&x); } return L; }

头插法重要应用：可以实现链表的逆置 // 链表逆置 LinkList *Inverse(LNode *L){ LNode *r = L->next; L->next = NULL; LNode *temp; while(r!=NULL){ temp = r; r = r->next; temp->next = L->next; L->next = temp; } return L; }

第四节双链表在单链表中，找到一个节点的前驱节点比较困难。双链表是在单链表的基础上再增加一个指针域prior用来指向前驱节点。

1.双链表的定义 typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist; //DNode *和DLinklist是等价的，一个强调结点，一个强调是链表

2.双链表的初始化 //带头节点的双链表的初始化 bool InitDLinkList(DLinkList &L){ L = (DNode*)malloc(sizeof(DNode)); if(L==NULL) return false; L->prior = NULL; L->next = NULL; return false; }

3.双链表判空 //判断双链表是否为空（带头结点） L->next==NULL

4.双链表的插入 //在p结点之后插入s结点 s->next=p->next; p->next->prior=s; s->prior=p; p->next=s;

存在的问题：如果p是最后一个结点，p->next->prior就会出现问题。解决： bool InsertNextDNode(DNode *p,DNode *s){ if(p==NULL || s==NULL) return false; s->next = p->next; if(p->next!=NULL) // 如果p有后继结点，才更改p的后继结点的前向指针 p->next->prior = s; s->prior = p; p->next = s; return true; } //这里其实是后插操作，可以由此来实现按位序插入 //按位序插入：从头节点开始，找到某个位序的前驱结点，进行后插操作 //前插操作：可以找到给定结点的前驱结点，对它执行后插操作

5.双链表的删除 //删除p的后继结点 p->next=q->next; q->next->prior=p; free(p); 存在问题：p的后继是否存在？p的后继的后继是否存在？

// 删除p的后继结点q p--q bool DeleteNextDNode(DNode *p){ DNode *q = p->next; if(p==NULL || q==NULL) // p指针为空 || p指针所指的结点没有后继 return false; p->next = q->next; if(q->next!=NULL) // q结点有后继结点，才修改它的后继结点的前向指针 q->next->prior = p; free(q); return true; }

6.销毁双链表 //销毁双链表 void DestoryList(DLinkList &L){ while(L->next!=NULL) DeleteNextDNode(L); free(L); L = NULL; }

7.双链表的遍历 //后向遍历 while(p!=NULL){ p=p->next; } //前向遍历 while(p!=NULL){ p=p->prior; } //前向遍历,跳过头结点 while(p->prior!=NULL){ p=p->prior; } 双链表不可以随机存取，按位查找、按值查找都只能用遍历的方式实现。时间复杂度O(n) 第五节循环链表

循环单链表单链表：表尾结点的next指针指向NULL 循环单链表：表尾结点的next指针指回头结点 typedef struct LNode{ Elemtype data; struct LNode *next; }LNode,*LinkList;

//初始化一个循环单链表 bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); if(L==NULL) return false; L->next=L; //头节点next指针指向头节点 return false; }

//判断循环单链表是否为空 L->next == L

//判断结点p是否为循环单链表的表尾结点 p->next==L

单链表：从一个结点出发只能找到后续的各个结点。循环单链表：从一个结点出发可以找到其他任何一个节点。 //删除单链表的一个结点时，如果只传入要删除的结点，删除时必然要修改其前驱节点的next指针，普通的单链表无法找到前驱。循环单链表，可以顺着一条链，找到其前驱结点。

循环单链表中，只设置尾指针效率更高，因为很多对链表的操作都是在头部或尾部。从头节点找到尾部，时间复杂度O(n)；从尾部找到头部，时间复杂度O(1)。

循环双链表表头结点的prior指向表尾结点，表尾结点的next指向头结点，形成了两条闭环。 //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){ L=(DNode*)malloc(sizeof(DNode)); //分配一个头结点 if(L==NULL) return false; L->prior=L; //头结点的头指针指向自身 L->next=L; //头结点的尾指针指向自身 return false; }

//判断循环双链表是否为空 L->next==L

//判断结点p是否为循环双链表的表尾结点 p->next==L

//在p结点之后插入s结点 bool InsertNextNode(DNode *p,DNode *s){ s->next=p->next; p->next->prior=s;
s->prior=p; p->next=s; }//在普通的双链表中，如果p是最后一个结点，p->next->prior相当于NULL->prior会出现问题，而循环双链表中恰好不存在此问题

//双链表的删除 -- 删除p的后继节点q p->next=p->next; q->next-prior=p; free(p); //同样的，此段代码如果在普通双链表中要删除的是最后一个节点就会出现问题

在循环链表中，关键在于判断一个节点p是否是表尾/表头结点，它是实现前向/后向遍历的核心。

第六节静态链表单链表：各个结点离散分布在内存中。每个结点都存放数据元素和指向下一个结点的指针。静态链表：分配一片连续的内存空间，结点集中安置。每个结点存放数据元素和下个结点的下标（游标）。游标充当了指针的作用，游标为-1表示已经到达表尾。若每个数据元素4B、每个游标4B（每个结点共8B），起始地址设为addr。则数组下标为2的结点的存放首地址为addr+82，该结点的地址范围是addr+82 ~ addr+8*3。

静态链表的定义 #define MaxSize 10 struct Node{ ElemType data; int next; };

struct Node a[MaxSize]; //数组a作为静态链表 //相当于创建了一个数组，数组里面的元素是结构体Node这种类型

另一种写法（两者完全等价）//上面的写法看起来更像一个数组，下面的写法看起来更像链表 #define MaxSize 10 struct Node{ ElemType data; int next; }SLinkList[MaxSize];

SLinkList a; //相当于声明了一个大小为10的数组，数组的每一个元素是一个struct

初始化一个静态链表 a[0].next=-1; //游标为-1表示已经到达表尾空结点的处理：对结点中“下个结点的下标”进行标记，例如next设为-2或其他值。
查找从头结点出发挨个往后遍历节点，找到某个位序的结点时间复杂度为O(n) //数组下标反映的是物理上的顺序，游标反应的是逻辑顺序
插入位序为i的节点 1）先找到一个空的节点，存入数据。 //初始化时可将空结点标记一下，例如把next设为-2 2）从头结点出发找到位序为i-1的结点。 3）修改新节点的next。 4）修改i-1结点的next。
删除某个结点 1）从头结点出发找到要删除结点的前驱结点。 2）修改前驱节点的游标，将其改为当前要删除结点的“下个结点的下标”(next)。 3）将要删除结点的next设为-2。
静态链表的优缺点：优点：增删操作不需要大量移动元素缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不可变

第七节顺序表和链表的比较（1）逻辑结构：都属于线性表，都是线性结构。

（2）存储结构：顺序表：顺序存储，各个元素大小相等，只需要知道起始地址，就能找到第i个元素，支持随机存取。只需要存储数据本身，存储密度高。但是，大片连续空间分配不方便，改变容量不方便。链表：结点离散存放，空间分配方便，改变容量方便。不可随机存取。存储密度低。

（3）基本操作：创销增删改查销毁考察不多，改就是在查的基础上赋值 1）创：顺序表：预分配大片空间。分配过小，之后不方便扩展。分配过大，浪费内存资源。静态分配：静态数组，容量不可改变。动态分配：动态数组（malloc，free）容量可改变，但是移动大量元素，时间代价高。链表：只需分配头结点（也可只声明一个头指针，不要头结点），之后方便拓展 2）销：顺序表：修改length=0 静态分配：静态数组，系统自动回收动态分配：动态数组（malloc、free）手动free malloc申请的内存在堆区，系统不会自动回收，malloc和free应该成对出现链表：依次删除各个结点（free）

3）增、删：
    顺序表：

相邻有序，插入/删除元素要将后续元素都后移/前移。时间复杂度O(n)，主要源于移动元素链表：插入/删除只需要修改指针。时间复杂度O(n)，主要来源于查找目标元素 //虽然都是O(n)，但若数据元素很大，移动的时间代价会很高，相较而言，查找元素的时间代价更低

4）查：
    顺序表：

按位查找O(1) 按值查找O(n) 若元素有序，可利用一些算法，如折半算法，可达到O(log_2 n)。链表：按位查找O(n) 按值查找O(n)

若表长难以估计，经常要增加、删除元素。 --->链表若表长可预估，查询（搜索）操作较大。 --->顺序表

第八章排序算法

第一节排序的基本概念

一、排序算法的评价指标

稳定性：关键字相同的元素排序后相对位置不变，则称此排序算法是稳定的。稳定性无好坏之分。
时间复杂度：内部排序算法的时间复杂度一般是由比较和移动的次数决定的。

二、排序算法的分类

内部排序：数据都在内存中。（关注时空复杂度更低）
外部排序：数据太多，无法全部放在内存。（关注如何使读写磁盘次数更少）

内部排序
（1）插入排序：按关键字大小插入到前面已排好序的子序列中。
直接插入排序、折半插入排序、希尔排序。
（2）交换排序：根据序列中两个元素关键字的比较结果对换两个记录在序列中的位置。
冒泡排序、快速排序。
（3）选择排序：选取关键字最小（或最大）的元素加入有序子序列。
简单选择排序、堆排序。
（4）归并排序、基数排序。

第二节插入排序

算法思想：每次将一个待排序记录按其关键字大小，插入到前面已排好序的子序列中，直到全部记录插入完成。

一、直接插入排序

思路：将当前待排序记录与前面的子序列依次对比，所有比当前记录大的元素右移，右移后得到空位放入当前记录，直至全部有序。和当前记录相等的不进行右移，可以保证算法的稳定性。

void InsertSort(int A[], int n){
    int i, j, temp;
    for(i = 1; i < n; i++){   // 假设第0个元素是最初的有序序列
        if(A[i] < A[i-1]){    // 如果待排序元素 < 有序序列最大的元素
            temp = A[i];    
            for(j = i-1; j >= 0 && A[j] > temp; --j) // 有序序列中只要比待排序元素大的部分都右移
                A[j+1] = A[j]; 
            A[j+1] = temp;   
        }
    }
}
// i：当前待排序元素    i-1:有序序列最末尾的元素
// j最终的位置+1：待排序元素插入到位置(j多--了之后 判断A[j]>temp不成立 才跳出for循环)

//直接插入排序（带哨兵）
// 0 1 2 ··· i-1 || i ··· n
void InsertSort(int A[],int n){     //从1号位置开始存储，0号位置作为哨兵
    int i,j;				// 0号位置用来 暂存数据元素 和 判断下标是否越界结束循环
    for(i=2; i<=n; i++){		// 左侧初始的有序序列是1号元素
        if(A[i] < A[i-1]){
            A[0] = A[i];
            for(j=i-1; A[j]>A[0]; --j)
                A[j+1] = A[j];
            A[j+1] = A[0];
        }
    }
}

优点：不用每轮循环都判断j>=0 // 不将A[0]设为哨兵时，必须要对j进行判断来决定循环是否结束，否则数组下标会越界。 // 而这里结束循环的方法是A[0]和A[j]是相等的，当j到0的时候，A[0]<A[0]为false，for循环终止。

算法效率分析（1）空间复杂度：O(1) 都是常数级的，与问题规模n没有关系。

（2）时间复杂度：主要来自对比关键字、移动元素。若有n个元素，则需要n-1趟处理。 1）最好情况：所有元素本就有序。共n-1趟处理，每一趟都只需对比关键字1次，不用移动元素。最好时间复杂度O(n)。

2）最坏情况：原来是逆序。5 4 3 2 1 第一趟：关键字对比2次(A[0] A[1])，移动元素3次(A[0]=A[2] A[2]=A[1] A[1]=A[0]) 第二趟：关键字对比3次，移动元素4次第i趟：关键字对比i+1次，移动元素i+2次第n-1趟：关键字对比n次，移动元素n+1次比较(n+2)(n-1)/2 移动(n+1+3)(n-1)/2 最坏时间复杂度O(n^2)

3）平均时间复杂度O(n^2) （好坏加和除2）

算法稳定性：稳定。

二、折半插入排序

思路：先用折半查找找到应插入的位置，再移动元素。 ·情况一：

当low>high时折半查找停止，应将[low,i-1]内的元素全部右移，并将A[0]复制到low所指位置。 // [high+1,i-1]也正确，因为最终low在high的右边，high+1=low。

·情况二：

此时为了保证插入排序的稳定性，当发现和目标元素值相同的元素，应在该元素的右边区间内继续查找。当A[mid]==A[0]时，正常使用折半查找时，此时应该停止。但是为了保证算法的稳定性，应继续再mid所指位置的右边寻找插入位置。

·情况三：最终停在low>high的位置，本来[low,i-1]之间的元素应该右移，但是此时[low,i-1] 中low比i-1大，无需移动。

//折半插入排序
void BinaryInsertSort(int A[],int n){
    int i,j.low,high,mid;
    for(i=2;i<=n;i++){  // i：待排序元素  
        if(A[i]<A[i-1]){
            A[0] = A[i];
            low = 1;        // 有序序列的起始
            high = i-1;     // 有序序列的末尾
            
            while(low <= high){	
                mid = (low+high)/2;  
                if(A[mid] > A[0])   // 中间元素 > 待排序元素	【为了保证稳定性不能加=】
                    high = mid-1;   // 在左子表中找
                else
                    low = mid+1;    // 在右子表中找
            }

            // 最终状态（跳出while时）   high < low      插入位置在high 和 low 中间
            // 0 1 2 3 ··· high low ··· i-1 || i
            // 将 [low,i-1] 之间的元素 右移一个位置
            for(j=i-1;j>=low,--j)   // 写法不唯一
                A[j+1] = A[j];          // j 原始位置   j+1 右移1个的位置
            A[low] = A[0];      // 插入挪出的空挡
        }
    }
}

相比较直接插入排序，折半插入排序比较关键字的次数减少了，但是移动元素的次数没变。折半插入排序的时间复杂度仍为O(n^2)。

对链表进行直接插入排序：只能进行直接插入排序，无法实现折半插入排序。使用链表来存储，移动元素的次数变少了，只需要修改结点的指针即可；但是关键字的对比次数依然是O(n^2)数量级的，整体来看时间复杂度依然是O(n^2)。

三、希尔排序

在直接插入排序中，若表中元素有序，可以得到最好的时间复杂度；若表中元素基本有序，时间复杂度也会有所提升。因此可以先追求表中元素部分有序，再逐渐逼近全局有序。希尔排序：先将待排序表分隔成若干形如L[I,i+d,i+2d,…,i+kd]的特殊子表，对各个子表分别进行直接插入排序。减小增量d，重复上述过程，直到d=1为止。

【第一趟】

【第二趟】

【第三趟】

第三趟时，整个表已经呈现“基本有序”，对整体再进行一次“直接插入排序”。

注：希尔本人建议，第一趟d取元素总数/2，之后每一趟将增量d减小一半。d取其他值也都是可以的。

考点：给出等量序列，分析每一趟排序后的状态。

//希尔排序		 
void ShellSort(int A[],int n){
    int d,i,j;
    for(d=n/2;d>=1;d/=2)       // 控制步长
        for(i=1+d;i<=n;++i)    // 对待排序元素依次进行遍历（每次i++就切换了一个子表）
            if(A[i]<A[i-d]){    // 如果当前待排序元素 < 对应子表中有序部分中的最大者
                A[0] = A[i];    // 暂存当前待排序元素
                for(j=i-d;A[j]>A[0]&&j>0;j-=d)   // 对子表中的元素移位
                    A[j+d] = A[j];
                A[j+d] = A[0];          // 待排序元素就位
            }
}
// i:待排序元素      i-d: 对应子表有序部分的末尾
// d用来控制步长，d将待排序表划分成了若干子表。
// i用来逐个遍历待排序元素，每次i++就相当于切换了一个子表。
// j用来在相应子表中寻找插入位置。

注：A[0]不是哨兵，要对j是否越界进行判断。

算法性能分析：空间复杂度：O(1) 时间复杂度：和增量序列的选择有关，目前无法用数学手段证明确切的时间复杂度。最坏时间复杂度为O(n^2) (d直接取1，退化为直接插入排序)，当n在某个范围内时，可达O(n^1.3)。总体上看是优于直接插入排序的，稳定性：不稳定。适用性：仅适用于顺序表，不适用于链表。因为需要快速找到间隔d的同属于一个子表的元素，存储结构必须具备随机访问的特性。

第三节交换排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果对换两个记录在序列中的位置。

一、冒泡排序

冒泡排序的定义

从后往前（或从前往后）两两比较相邻元素的值，若为逆序则交换它们，直到序列比较完。称这样的过程为“一趟”冒泡排序。每趟冒泡排序的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置。最多n-1次冒泡排序就可以将所有元素排好序。

例子

第1趟：第一趟冒泡排序使得关键字值最小的一个元素“冒”到最前面。

前面已经确定最终位置的元素可以不用再对比。第二趟冒泡排序结束后，最小的两个元素会“冒”到最前面。以此类推

第4趟：如果两个元素的值相同，不应交换它们的位置，以此来保证算法的稳定性。
第5趟：若某一趟排序没有发生交换，说明此时已经整体有序，可以结束算法。

代码实现（从后往前）

//交换
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
//冒泡排序
void BubbleSort(int A[],int n){
    int i,j;
    for(i=0;i<n-1;i++){     // i指示当前有序序列的边界，i之前的元素都是有序的
        bool flag = false;
        for(int j=n-1;j>i;j--){	 // 对无序序列从末尾开始遍历
            if(A[j]<A[j-1]){
                swap(A[j],A[j-1]);
                flag = true;
            }
        }
        if(flag==false)     // 某次未发生交换  --> 待排序部分已经有序
            return;
    }
}
// 每次从待排序序列的末尾开始遍历，将最小的元素交换到待排序序列的最前面（加入到有序序列）。

算法性能分析（1）空间复杂度：O(1)。

（2）时间复杂度： 1）最好情况（有序）：1 2 3 4 5 6 7 8 第一趟未发生交换，直接结束。比较次数n-1，交换次数0。最好时间复杂度：O(n)。 2）最坏情况（逆序）：8 7 6 5 4 3 2 1 比较次数=交换次数=(n-1)+(n-2)+⋯+1=(n(n-1))/2 最坏时间复杂度：O(n^2)。 3）平均时间复杂度：O(n^2 )。注：这里的交换次数是指调用swap的次数，其中每次调用swap需要移动元素3次。

（3）稳定性：稳定。

（4）适用性：适用于链表。可以从链头开始和后面的元素进行对比，每一趟排序可以让最大的元素来到最后。

二、快速排序

冒泡排序使得最大或最小的元素确定最终位置，而快速排序每次使一个中间元素确定最终位置。

算法思想：在待排序表中任取一个元素pivot作为枢轴（或基准，通常选首元素），通过一趟排序将待排序表划分为独立的两部分。使得左半部分的所有元素都小于pivot，右半部分所有元素都大于等于pivot，则pivot放在了其最终位置上，这个过程称为一次“划分”。分别递归地对两个子表重复执行该操作，直至每部分只有一个元素或为空为止，即所有元素放在了其最终位置上。例子

选取49作为枢轴元素，让low和high往中间移动，保证high所指的右边都要大于等于当前基准元素，low左边的元素要保证都小于基准元素。 low所指为空，让high向左移动。high当前所指元素49大于等于数轴元素，无需移动。high左移 high所指的元素27小于枢轴元素，将其放在当前low指针处。

high所指为空，检查low。此时low所指27小于枢轴元素，无需移动。
low右移，low所指38同样小于枢轴元素，无需移动。
low右移，此时low所指65大于枢轴元素，所有大于等于枢轴的元素，都要放在high或high右边，因此移动到high位置处。

即更小的元素交换到左边，更大的元素交换到右边。依此类推。

当low和high碰到一起时，说明已经把所有待排序的元素都扫描了一遍。所有比基准元素更小的，都放在了low指针的左边，所有比基准元素更大或相等的都放在了high指针的右边。此时可以确定基准元素49就是放在3这个位置（low、high相遇）上。即用第一个元素作为枢轴（基准）元素，把待排序序列“划分”为两个部分，左边更小，右边更大。该元素最终位置得以确定。因此接下来无需处理49了，只要对左右两个子表再次用同样方法进行划分即可。

同样的方式对左子表进行处理，由于处理完后的左子表的子表中只有一个元素，无需进行处理，所有元素的最终位置都已确定。
同样的方式对右子表进行处理，右子表的左子表还需要再处理一次。

快速排序本质上就是对待排序表不断进行划分，每一次的划分会使得左边的元素都比枢轴元素小，右边的元素都比枢轴元素大，尤其可以确定枢轴元素的位置。递归对左右子表进行划分，即可实现排序。

代码实现

int Partition(int A[],int low,int high){
    int pivot = A[low];         // 相当于A[low]位置为空
    while(low<high){
        while(low<high && A[high]>=pivot)   // 跳出while时，high所指位置元素小于pivot
            --high;     // 必须要加等号，不然和枢轴相等时，high和low中元素会循环交换
        A[low] = A[high];           // 将小于pivot的元素放在左侧
        while(low<high && A[low]<=pivot)    // 跳出while时，low所指位置元素大于pivot
            ++low;
        A[high] = A[low];           // 将大于pivot的元素放在右侧
    }
    A[low] = pivot;     // 枢轴归位
    return low;     // 返回枢轴         // 6 1 2 9 10
}   // 易错点：选取low作为枢轴，一定要先判断A[high]>=pivot，如果先判断A[low]<=pivot的话就会出现错误。

    //最后一次外层的while循环时，在内层的两个while使得low与high不断移动，直到重合，会导致内层的while条件不满足跳出，然后会执行移动。由于此时low与high指在同一个地方，因此移动元素不产生影响。然后回到外层while循环，也跳出。  

void QuickSort(int A[],int low,int high){
    if(low<high){       //递归调用时，最小的子表是一个元素，此时low=high，必须加以判断跳出递归。
        int pivotpos = Partition(A,low,high);   // 划分，确定枢轴位置
        QuickSort(A,low,pivotpos-1);    // 处理左子表
        QuickSort(A,pivotpos+1,high);   // 处理右子表
    }
}

//以前面的例子为例
//（建议：画函数调用栈，加入行号标注执行到哪一行了，并标注是第几层的函数）
//调用QuickSort   low=0 high=7
//调用Partirion   传入low=0 high=7  得到pivotpos=3 跳出
//回到调用QuickSort 此时low=0 high=7  pivotpos=3

    //调用QuickSort   low=0  high=2
    //调用Partirion   传入low=0 high=2  得到pivotpos=1  跳出
    //回到第二次调用QuickSort 此时low=0 high=2  pivotpos=1
        //调用QuickSort  low=0 high=0 跳出
        //调用QuickSort  low=2 high=2 跳出

    //调用QuickSort   low=4  high=7
    //调用Partirion 传入 4， 7 得到pivotpos=6 跳出
        //调用QuickSort  low=4 high=5
            //调用Partirion 传入 4， 5 得到pivotpos=4 
                //调用QuickSort low=4 high=3 跳出
                //调用QuickSort low=4 high=5 跳出
        //调用QuickSort  low=7 high=7 跳出

算法效率分析：（1）时间效率：每一层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过O(n)。时间复杂度：O(n*递归层数)

（2）空间复杂度=O(递归层数) 在函数栈里面，每一层的函数调用，都要开辟空间来保存这层函数调用相关的局部变量、返回地址等，递归调用的深度越深，空间复杂度就会越高。

调用深度计算：每一层的QuickSort会把当前这层要处理的子区间再次划分成左右两个部分，逐层往下。最终处理后的n个元素组织起来就变成了二叉树，二叉树的层数就是递归调用的深度。 n个结点的二叉树，最小高度=⌊log_2⁡n+1⌋，最大高度=n。

时间复杂度：O(n*递归层数) 空间复杂度：O(递归层数)

最好时间复杂度：O(nlog_2 n) 最坏时间复杂度：O(n^2)

最好空间复杂度：O(log_2 n) 最坏空间复杂度：O(n)

最好情况：若每一次选中的“枢轴”可以将排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。上面的例子就是比较好的情况。

最坏情况：若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低。如1 2 3 4 5 6 7 8，每次选取第一个元素作为枢轴，会调用n层quicksort函数。

若初始序列有序或逆序，则快速排序的性能最差（每次选择的都是最靠边的元素）。

优化思路：尽量选择可以把数据中分的枢轴元素。如：①选头、中、尾三个位置的元素，取中间值作为枢轴元素；②随机选一个元素作为枢轴元素。

快速排序的平均复杂度为：O(nlog_2 n) 快速排序是所有内部排序算法中平均性能最优的排序算法。

（3）稳定性：不稳定。

注：有的题目中，“一次划分”≠“一趟排序”。一次划分：只能确定一个元素的最终位置。一趟排序：可确定多个元素位置。

第四节选择排序

选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

一、简单选择排序

在待排序元素中找到最小的元素，加入有序子序列。

若有两个关键字相同的待排序元素，优先选择最先被扫描到的元素（前面的）进行处理。

前面的有序子序列无需进行处理；最后待排序元素只剩下一个时也无需处理。

n个元素进行简单选择排序需要进行n-1趟处理。

//简单选择排序
void SelectSort(int A[],int n){
    int i,j,min;
    for(i=0;i<n-1;i++){     
        min = i;                // 假设当前待排序元素是最小的
        for(j=i+1;j<n;j++)     // 对其余待排序元素进行遍历
            if(A[j]<A[min])     // 寻找有没有更小的
                min=j;
        if(min!=i)      // 如果有更小的
            swap(A[i],A[min]);  // 把更小的元素换在待排序元素的首位
    }
}

算法效率分析（1）空间复杂度：O(1) （2）时间复杂度：O(n^2) 无论有序、逆序还是乱序，一定需要n-1趟处理。总共需要对比关键字(n-1)+(n-2)+⋯+1=(n(n-1))/2。注：简单选择排序不会因为所给出的序列不同而影响算法的效率。

（3）稳定性：不稳定。交换位置时，可能会改变元素的相对位置。

（4）适用性：既可以用于顺序表，也可用于链表。（所有元素扫描遍历一边挑出最小的，放到链头或者链尾）。

二、堆排序

堆的概念
若n个关键字序列L[1…n]满足下面的某一条性质，则称为堆（Heap）。
	大根堆（大顶堆）：L(i)≥L(2i)且L(i)≥L(2i+1)      (1≤i≤n/2)
	小根堆（小顶堆）：L(i)≤L(2i)且L(i)≤L(2i+1)      (1≤i≤n/2)

回顾完全二叉树的顺序存储：

完全二叉树按照层序顺序存储在数组中，数组下标可以反映结点间的逻辑关系。可以将堆理解为一颗顺序存储的完全二叉树：

编号为1的结点为这棵二叉树的根结点。假设某个结点下标为i，则它的左孩子下标为2i，右孩子下标为2i+1，当i≤n/2时，这一定是一个分支结点。

因此，大根堆：完全二叉树中，根≥左、右；小根堆：完全二叉树中，根≤左、右。对比二叉排序树BST，左≤根≤右。

对大根堆进行排序很简便，可方便地找到最大的元素。问题转化为如何建立大根堆（根≥左、右）。

建立大根堆
大根堆的特点是：根≥左、右。

由于二叉树是递归定义的，所有的非终端结点都可以视为一个根结点。因此，将所有非终端结点都检查一遍，看是否满足大根堆的要求（根≥左、右），若不满足则需要调整。在顺序存储的完全二叉树中，非终端结点编号i≤⌊n/2⌋。

检查当前结点是否满足根≥左、右，若不满足，将当前结点与更大的一个孩子互换。

共8个元素，⌊8/2⌋=4，从后往前检查前四个元素即可。下标为4的根结点9比它下标为8的左孩子32小，需要处理，将9与它最大的孩子互换。

若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断下坠）。

代码实现—建立大根堆

//将以k为根的子树调整为大根堆
void HeapAdjust(int A[],int k,int len){     // 调整根结点k的位置
    A[0] = A[k];    // 暂存根节点
    for(int i=2*k;i<=len;i*=2){         // 指向左孩子
        if(i+1<=len && A[i]<A[i+1])     // 如果有右孩子，并且右孩子比左孩子大
            i++;		
        if(A[0] >= A[i])  // 如果根节点最大
            break;   // 无需调整，直接退出
        else{
            A[k] = A[i];    // 将更大的孩子放在当前根结点的位置上
            k = i;      // 进入下一轮循环：判断根节点在刚才最大的孩子处是否满足条件   -->   寻找根结点的最终位置
        }
    }
    A[k] = A[0];    // 找到了根节点的最终位置，把值放进来
}

//建立大根堆    从后向前调整所有非终端结点
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)       // 二叉树结点下标是从1开始的
        HeadAdjust(A,i,len);
}

堆排序（基于大根堆）

选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列。堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列的最后一个元素交换），并将待排序元素（将之前移动到末尾的元素排除在外）序列再次调整为大根堆（小元素不断下坠）即每一趟把最大元素移到末尾，然后再把排除最大元素后的恢复成大根堆。

每一趟恢复大根堆时，仍调用HeadAdjust。注意每次传入的k值越来越小(k--)，是因为放到末尾排好序的已经被排除在外了。

进行n-1趟即可，最后一趟只剩一个元素时无需进行操作。基于大根堆的堆排序得到递增序列，基于小根堆的堆排序得到递减序列。

	堆排序--代码实现
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len)
//建立大根堆
void BuildMaxHeap(int A[],int len)

//堆排序的完整逻辑
void HeapSort(int A[],int len){   // 0 1 2 3 ··· len      A[0]:暂存     len：结点个数
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){     // |----大根堆----|--有序序列--|
        swap(A[1],A[i]);    // A[1]是大根堆的根结点 将待排序元素中最大的值归入有序序列中
        HeapAdjust(A,1,i-1);    //再次调整
    }   // |----大根堆----|--有序序列--|
}   　　// 0 1 2 3 ··· i-1　i ··· len

算法效率分析

（1）时间复杂度：O(nlog_2 n) 建立大根堆的时候和堆排序的时候都需要调用HeadAdjust，因此需要分析这个“下坠”函数。

1）建立大根堆时调用调整函数若一个结点有两个孩子，下坠一层，需要对比关键字两次：A[i]<A[i+1] A[0]>=A[i] //对比96和32谁更大。将根结点和最大的孩子进行对比。若一个结点只有一个孩子，下坠一层，需要对比关键字一次。i<len为false无需进行A[i]<A[i+1] //09的编号是4，左孩子编号是8，元素总数len=8，8<8为false，不满足if条件，说明左孩子没有右兄弟，无需对比左右孩子关键字。结论：一个结点，每“下坠一层”，最多只需要对比关键字2次。若树高为h，某节点在第i层，则将这个结点向下调整最多只需要“下坠”h-i层，关键字对比次数不超过2(h-i)。 n个结点的二叉树的树高h=⌊log_2⁡n ⌋+1。第i层最多有2^(i-1)个结点，而只有第1~(h-1)层的结点才有可能需要“下坠”调整。 12(h-1)+22(h-2)+⋯+2^(h-2)*2=∑_(i=h-1)^1▒〖2^(i-1) 2(h-i)=〗………≤4n (数学计算) 第1层最多1个结点，最多关键字对比2(h-1)次；第2层最多2个结点，最多关键字对比2(h-2)次……第h-1层最多2^(h-2)个结点，最多关键字对比2次.

建堆的过程，关键字对比次数不超过4n，建堆时间复杂度：O(n)。 2）排序时调用调整函数总共要进行n-1趟，每一趟交换后都需要将根结点下坠、调整，根结点最多下坠h-1层。每下坠一层，最多只需对比关键字2次，树高h=⌊log_2⁡n ⌋，因此每一趟排序复杂度不超过O(h)=O(log_2⁡n)。共n-1趟，排序总的时间复杂度为：O(nlog_2 n)。

因此：堆排序的时间复杂度=O(n)+O(nlog_2⁡n )=O(nlog_2 n)。

（2）堆排序的空间复杂度=O(1)。（3）稳定性：不稳定。排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，有可能改变值相同数据的原始相对顺序。 ……

练习：基于小根堆进行建堆、排序。堆的插入与删除插入对于小根堆，新元素放到表尾，与父结点对比，若新元素比父节点更小，则将二者互换。新元素一路“上升”，直到无法继续上升为止。

对于元素i，i的左孩子为2i，i的右孩子为2i+1，i的父节点为⌊i/2⌋。

插入元素13，对比关键字两次，进行两次移动。

插入元素46，对比关键字一次，无需进行移动。

删除元素

被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到不能下坠为止。删除元素13：

第一次下坠：先对比17和45，选中更小的孩子17。再对比17和46。对比关键字两次。第二次下坠：先对比53和32，选中更小的孩子32。再对比42和36。对比关键字两次。共对比关键字4次。

下方若有两个孩子，则下坠一层，需要对比关键字两次。第一次选择最小的孩子结点，第二次根结点和被选中的那个结点进行对比。下方若只有一个孩子，则下坠一层，只需对比关键字一次。（★代码中通过i<len判定有几个孩子，一旦i<len不满足，后面的关键字对比无需进行）

删除元素65：

将堆底元素46移动到删除产生的空位。先对比78和87，选中最小的孩子78。再对比根结点46和78，根结点比最小的孩子还要小，无需移动。共对比关键字两次。

练习：写出堆的插入和删除的实现代码。

第五节归并排序和基数排序

一、归并排序

归并：

归并(merge)：将两个或多个已经有序的序列合并成一个。 2路归并：将两个有序的序列合并成一个。每选出一个小元素需要对比关键字1次。

对比i、j所指元素，选择更小的一个放入k所指的位置。每次放入之后，k要后移，k后移的同时还需要将放入元素原来位置上的指针也一并后移。当只剩一个子表未合并时，可以将该子表中的剩余元素直接全部加到总表。

2路归并：将两个有序的序列合并成一个。每选出一个小元素需要对比关键字1次。 4路归并：将四个有序的序列合并成一个。每选出一个小元素需要对比关键字3次。结论：m路归并，每选出一个元素需要对比关键字m-1次。

归并排序

内部排序中，一般使用二路归并实现。先将初始序列每一个单独的元素视为一个个已经排好序的序列。第一趟归并排序，会让两个相邻的进行二路归并，出现单独的对其归并相当于什么也没做。第二趟归并排序，会基于第一趟归并排序的结果再次进行二路归并。核心操作：将数组内的两个有序序列归并为1个。

int *B=(int *)malloc(n*sizeof(int));    //辅助数组B

//A[low,mid] 和 A[mid+1,high] 各自有序，将两个部分归并。
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)      // 复制一份
        B[k] = A[k];
    for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){   // k=i 注意不要写错
        if(B[i]<=B[j])      // 优先使用靠前的那个，保证稳定性
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while(i<=mid)       // 将剩余未归并的加入到尾部
        A[k++] = B[i++];
    while(j<=high)
        A[k++] = B[j++];
}//k指示元素赋值过来的位置，i和j分别指示两个序列的首个元素。

// 另一种写法：for循环改成while
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k] = A[k];
    i = low, j = mid+1, k=i;
    while(i<mid && j<=high){
        if(B[i]<=B[j])
            A[k++] = B[i++];
        else
            A[k++] = B[j++];
    }
    while(i<=mid)
        A[k++] = B[i++];
    while(j<=high)
        A[k++] = B[j++];
}

 
//归并排序
void MergeSort(int A[],int low,int high){
    if(low<high){       // 必须加以判断，不然会出现死递归
        int mid = (low+high)/2;
        MergeSort(A,low,mid);       // 对左半部分进行归并排序
        MergeSort(A,mid+1,high);    // 对右半部分进行归并排序
        Merge(A,low,mid,high);      // 将有序的两部分进行归并
    }
}

对左右两部分分别递归的进行归并排序，经过递归的处理之后，左右两个部分都可以变得有序，再将左右两个有序序列进行归并即可。递归：最深入一层的MergeSort，由于只有一个元素49，不会对其操作。low<high为false，直接跳出if，函数退出。

算法效率分析（1）时间复杂度：O(nlog_2 n) 2路归并的“归并树”，形态上就是一棵倒立的二叉树。假设树高为h，归并排序的趟数为h-1。二叉树的第h层最多只会有2^(h-1)个节点。若初始待排序序列有n个元素，树高为h，则应满足n≤2^(h-1)。（把初始序列视为第h层，n个结点都要出现在h层，第h层最多只会有2^(h-1)个结点）。解得h-1=⌈log_2⁡n ⌉。故趟数为⌈log_2⁡n ⌉。结论：n个元素进行2路归并排序，归并趟数为⌈log_2⁡n ⌉。每趟归并中，第一次归并，最多n/2次关键字对比，最后一次最多进行n-1次关键字对比，不管哪一趟归并，时间复杂度都为O(n)。因此，算法的时间复杂度为O(nlog_2 n)。

（2）空间复杂度：O(n) 递归带来的工作栈会产生空间开销，递归调用的深度不会超过log_2⁡n，递归带来的空间复杂度为O(log_2⁡〖n)〗。辅助数组B产生的空间复杂度为O(n)。 O(log_2⁡〖n)〗+ O(n)=O(n)

（3）稳定性：稳定 if(B[i]<=B[j]) //两个元素相等时，优先使用靠前的那个，保证稳定性。 A[k]=B[i++]; //将较小值复制到A中

二、基数排序

基数排序的定义

假设长度为n的线性表中每个结点a_j的关键字由d元组(k_j^(d-1),k_j^(d-2),k_j^(d-3),… ,k_j^1,k_j^0)组成，其中，0≤k_j^i≤r-1 (0≤j<n ,0≤i≤d-1),r称为基数。 k_j^(d-1)为最高位关键字（最主位关键字），k_j^0为最低位关键字（最次位关键字）。

基数排序得到递减序列的过程：初始化：设置r个空队列，Q_(r-1),Q_(r-2),…,Q_0。按照各个关键字位权重递增的次序(个十百)，对d个关键字分别做“分配”和“收集”。分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Q_x队尾。收集：按照Q_(r-1),Q_(r-2),… ,Q_0的顺序，将各个队列中的结点依次出队并链接。

基数排序得到递增序列的过程：初始化：设置r个空队列，Q_0,Q_1,…,Q_(r-1)。按照各个关键字位权重递增的次序(个十百)，对d个关键字分别做“分配”和“收集”。分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Q_x队尾。收集：按照Q_0,Q_1,…,Q_(r-1)的顺序，将各个队列中的结点依次出队并链接。

基数排序不是基于比较的排序算法，一般不考察代码，手算即可。

【例】基数r=10 第一趟分配：按照个位进行分配

第一趟收集：由于要得到递减的序列，从个位值更大的开始收集。

第二趟分配：按照十位进行分配。注：十位相同的时候，个位越大的越先入队，个位越小的越后入队。因为第二趟是基于第一趟进行的，个位数大的会排在前面，个位数小的会排在后面。

第二趟收集：十位相同的按个位递减排列。

第三趟分配：按照百位进行分配。注：百位相同的时候，十位越大的越先入队，十位越小的越后入队。因为第三趟是基于第二趟进行的，十位数大的会排在前面，十位数小的会排在后面。

第三趟收集：

算法效率分析

基数排序通常基于链式存储实现。 typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkNode,*LinkList;

typedef struct{ //链式队列 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue;

LinkQueue Q[10]; 一个名为Q的数组，长度为10。数组的每个单元存放着叫LinkQueue的结构体，LinkQueue结构体存着叫做rear和front的头指针和尾指针，指针指向的是LinkNode这种结构体。LinkNode这个结构体里面存着data和指向LinkQueue 的名为next的指针。

（1）空间复杂度需要r个辅助队列，每新增一个队列，就是相当于增加两个指针域，每个队列需要的空间都是O(1)的数量级，因此空间复杂度为O(r)。

（2）时间复杂度一趟分配O(n)，一趟收集O(r)，总共d趟分配、收集，总的时间复杂度为O(d(n+r)) 分配时，处理n个元素；收集时，处理r个队列。 d：关键字拆分成几个部分。r:每个部分可能取到r个值。

收集队列Q6的元素，将其全部拆下，连到链尾。收集一个队列仅需O(1)时间，r个队列需要O(r)的时间。 
	p->next=Q[6].front;		Q[6].front=NULL;			Q[6].rear=NULL;

（3）稳定性：稳定的。

基数排序的应用

将10000名学生信息按照年龄递减排序，生日可拆分为三组关键字：年(1991-2005)、月、日。权重：年>月>日。先从日开始操作，即按照权重递增进行分配和收集。由于日越小的年龄越大，因此应该先收集日更小的，再收集日更大的。

基数排序处理的数据可以是多样的，取值范围并不一定，处理方式不同，因此辅助队列也要根据具体需求来定义。此例中：d=3 n=10000 r=31/12/15

基数排序擅长解决的问题：数据元素的关键字可以方便地拆分为d组，且d较小。每组关键字的取值范围不大，即r较小。数据元素个数n较大。

	基数排序的时间复杂度=O(d(n+r))。
反例：
	给五个人的身份证号排序。18位身份证号需要分配回收18趟。d较大，且n较小。但是给十亿个人身份证号排序就很适合。
	给中文人名排序。汉字过多有上万种，即r过多。时空复杂度都很高。

第六节内部排序算法的比较与应用

内部排序算法的比较
时间复杂度

·O(n^2)：（平均情况下）简单选择排序、直接插入排序、冒泡排序。但是直接插入排序和冒泡排序最好情况下可达到O(n)。简单选择排序与序列的初始状态无关。 ·希尔排序作为插入排序的拓展，对较大规模的排序可达到很高的效率，但无法得出精确时间。 ·堆排序：线性时间内建堆，O(nlog_2 n)。 ·快速排序：基于分治，虽然最坏会达到O(n^2)，但平均性能可达到O(nlog_2 n)，实际应用常优于其他。 ·归并排序：基于分治的思想，其分割子序列与初始序列的排列无关，其好坏平均都为O(nlog_2 n)。

空间复杂度

·O(1)：简单选择排序、插入排序、冒泡排序、希尔排序、堆排序。仅需常数个辅助空间。 ·快速排序：需要一个小的辅助栈用于实现递归，平均情况下为O(log_2 n)，最坏会增长到O(n)。 ·2路归并排序：需要借助较多辅助空间用于元素复制，大小为O(n)，虽然可以克服但代价过高。

稳定性

·稳定：直接插入排序、冒泡排序、归并排序、基数排序。 ·不稳定：简单选择排序、快速排序、希尔排序、堆排序。

平均时间复杂度为O(nlog_2 n)的稳定排序算法只有归并排序。

过程特征

·冒泡排序、堆排序，每趟处理后都能产生当前的最大值、最小值。 ·快速排序一趟处理可以确定一个元素的最终位置。算法种类时间复杂度空间复杂度是否稳定最好情况平均情况最坏情况直接插入排序 O(n) O(n^2) O(n^2) O(1) √ 冒泡排序 O(n) O(n^2) O(n^2) O(1) √ 简单选择排序 O(n^2) O(n^2) O(n^2) O(1) × 希尔排序 O(1) × 快速排序 O(nlog_2 n) O(nlog_2 n) O(n^2) O(log_2 n) × 堆排序 O(nlog_2 n) O(nlog_2 n) O(nlog_2 n) O(1) × 2路归并排序 O(nlog_2 n) O(nlog_2 n) O(nlog_2 n) O(n) √ 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) √

直接插入排序：正序：对比一趟关键字即可，无需移动。O(n) 逆序：比较(n+2)(n-1)/2 移动(n+1+3)(n-1)/2 冒泡：正序：第一次未发生交换直接结束。 O(n) 逆序：比较n(n-1)/2 移动3n(n-1)/2 简单选择：不存在提前结束的情况，不管顺序如何，次数都一样。O(n^2) 希尔：时间复杂度无法确定。快速排序：取决于枢轴的选取，如果枢轴选取恰好正中，二叉树高度最小高度=⌊log_2⁡n+1⌋。反之最大高度=n。每一层最多处理n个元素。最好时间复杂度：O(nlog2n) 最坏空间复杂度：O(n^2) 最好空间复杂度：O(nlog2n) 最坏空间复杂度：O(n) 函数调用栈堆排序：时间复杂度=O(n)+O(nlog_2⁡n )=O(nlog_2 n)。建堆+调整空间复杂度=O(1) 二路归并： n个元素进行2路归并排序，归并趟数为⌈log_2⁡n ⌉。每趟归并中关键字对比次数不超过n 时间复杂度为O(nlog_2 n)。空间复杂度：递归O(log_2⁡〖n)〗辅助数组B O(n)。 O(log_2⁡〖n)〗+ O(n)=O(n) 基数排序： d：关键字拆分成几个部分。r：每个部分可能取到r个值。

二、内部排序算法的应用选取排序方法要考虑的因素待排序的元素数目n、元素本身信息量大小、关键字结构及分布、稳定性、语言工具的条件、存储结构及辅助空间的大小。

排序算法小结
若n较小，可采用直接插入排序或简单选择排序。

//直接插入排序移动记录的次数比简单选择排序多，若记录信息量大，简单选择排序更好。

初始状态已按关键字基本有序，选用直接插入或冒泡排序。

若n较大，使用时间复杂度为O(nlog_2 n)的算法，快速排序、堆排序、归并排序。

快速排序：认为是基于比较的内部排序算法中最好的。待排序的关键字随机分布时，其平均时间最短。堆排序：所需辅助空间少于快速排序，且不会出现最坏情况。上面两种都不稳定，若要求稳定，可选用归并排序。本章介绍的从单个记录起进行两两归并的排序算法不提倡，可以和直接插入排序结合使用。可以先用直接插入排序求得较长的有序子文件，再两两归并。直接插入排序是稳定的，改进后的归并排序仍稳定。

当n个关键字随机分布时，任何借助比较的排序算法都需要O(nlog_2 n)。

每次比较两个关键字大小后，仅可能出现两种可能的转移，可用二叉树描述这一过程，并加以证明。

若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

若记录本身信息量大，为避免耗费大量时间移动记录，可用链表作为存储结构。

第二章 线性表

第二章线性表