測(cè)試代碼

創(chuàng)建BST

若從一顆空樹T出發(fā)，依次插入節(jié)點(diǎn)，那么可以創(chuàng)建一個(gè)二叉排序樹

測(cè)試代碼

如下圖

#include \"BSTree.h\"

int main(void) {

BSTree T = NULL;

CreatBTree(&T); //以先序遍歷的順序創(chuàng)建二叉樹，0表示為虛空節(jié)點(diǎn)

Insert_BST(&T, 66);

InOrder_BST(T);

system(\"pause\");

return 0;

}

//// 45 12 3 0 0 37 24 0 0 0 53 0 100 61 0 90 78 0 0 0 0

void Creat_BST(BSTree *T) {

*T = NULL; //初始化為NULL，以便Inser——BST可以運(yùn)行

BSTKeyType key;

scanf(\" %d\", &key);

while (key != ENDFLAG) { // ENDFALG 為 0

Insert_BST(T, key);

scanf(\" %d\", &key); //注意：while內(nèi)部必須要有輸入

}

}

#include \"BSTree.h\"

int main(void) {

BSTree T = NULL;

Creat_BST(&T);

// Insert_BST(&T, 66);

InOrder_BST(T);

system(\"pause\");

return 0;

}

// 45 24 53 12 90 0

By: LI LIANGJI (Wechat:llj907015000)

No. 14 / 52

注意：

不同序列產(chǎn)生的二叉排序樹的形態(tài)不一樣

45 24 53 12 90 (如上圖)和 12 24 45 90 53 (如下圖)中序遍歷的順序一樣，但是形態(tài)不一樣

已知插入的 為 ，一共有個(gè)節(jié)點(diǎn)則需要 次循環(huán)

所以創(chuàng)建時(shí)間效率為

BST刪除

從BST刪除一個(gè)節(jié)點(diǎn)，不能把以該節(jié)點(diǎn)為根的子樹都刪除，只能刪除該節(jié)點(diǎn)，并且還要保證刪除后的

二叉樹仍然為BST

BST的刪除操作分為三種情況

令被刪除節(jié)點(diǎn)的地址為p，p的雙親結(jié)點(diǎn)為f且p為f的左孩子

當(dāng)p為葉子節(jié)點(diǎn)時(shí)， f->lchild = NULL;

當(dāng)p只有一個(gè)左子樹或右子樹時(shí)， f->lchild = p->lchild; 或 f->lchild = p->rchild;

當(dāng)p擁有左右子樹時(shí),此種情況較為復(fù)雜，需要具體分析

前置知識(shí)，若已知一個(gè)二叉排序樹的節(jié)點(diǎn)m，m的直接前驅(qū)節(jié)點(diǎn)為m的左子樹上右分支最后一個(gè)右孩

子為空的節(jié)點(diǎn)，如下圖

By: LI LIANGJI (Wechat:llj907015000)

No. 15 / 52

由圖可知，n沒有右孩子(如果n一旦有了有孩子，那么m的直接前驅(qū)必然會(huì)發(fā)生變化)，但n可以有左孩

子(即使有左孩子也并不影響n是m的直接前驅(qū))

同時(shí)也要考慮n的左子樹沒有右分支的情況，如下圖

由圖可知，如果n沒有右分支，那么m的直接前驅(qū)為n

利用對(duì)稱性可知直接后繼節(jié)點(diǎn)則為：m的右子樹上左分支上最后一個(gè)左孩子為空的節(jié)點(diǎn)

考慮下圖：

中序遍歷所得到的序列為:

By: LI LIANGJI (Wechat:llj907015000)

No. 16 / 52

由圖可知 P 的直接前驅(qū)為 S，如果把序列中P刪除并且 P 的數(shù)據(jù)用 S 代替

此時(shí) 變成了 的直接前驅(qū)為 的右子樹上的左分支最后一個(gè)左孩子為空的節(jié)點(diǎn)為 即 Q-

>right = S->left

void Delete_BST(BSTree *T, BSTKeyType key) {

BSTree p = *T;

BSTree parent = NULL;

while (p) { //若循環(huán)結(jié)束則直接return，說明沒找key

if (p->data.key == key)

break; //退出循環(huán)此時(shí)p指向要?jiǎng)h除節(jié)點(diǎn)

else if (key < p->data.key) {

parent = p; //通過比較key值定位要?jiǎng)h除節(jié)點(diǎn)

p = p->lchild;

} else {

parent = p;

p = p->rchild;

}

}

if (!p) {

return;

}

//當(dāng)控制來(lái)到次行時(shí)，說明p指向了要?jiǎng)h除的節(jié)點(diǎn)

BSTree pfree;

BSTree node;

if (p->lchild && p->rchild) { //第一種情況 p的左右子樹不為空

BSTree prior = p->lchild; // p的直接前驅(qū)一定在p的左子樹上，所以prior = p的左孩子

BSTree parent_prior = p; //需要一個(gè)節(jié)點(diǎn)來(lái)定位prior的雙親結(jié)點(diǎn)

while (prior->rchild) { //在右分支上尋找要?jiǎng)h除節(jié)點(diǎn)p的直接前驅(qū)

parent_prior = prior;

prior = prior->rchild;

}

p->data.key = prior->data.key; //把前驅(qū)節(jié)點(diǎn)的值賦給要?jiǎng)h除節(jié)點(diǎn)

//此時(shí)問題轉(zhuǎn)化成了：在保持序列順序的前提下，如果鏈接二叉排序樹

if (parent_prior != p) {

parent_prior->rchild = prior->lchild;

} else { //此種情況p的直接前驅(qū)為p的左孩子，

parent_prior->lchild = prior->lchild;

}

free(prior);

return;

} else if (!p->lchild) {

pfree = p; // pfree用于存放 要?jiǎng)h除節(jié)點(diǎn)的地址

node = p->rchild; // node存放需要鏈接節(jié)點(diǎn)的地址

} else if (!p->rchild) {

pfree = p;

node = p->lchild;

}

//當(dāng)控制來(lái)到此行時(shí)，pfree保存要?jiǎng)h除節(jié)點(diǎn)的地址，node存放需要連接的節(jié)點(diǎn)地址

if (!parent) { //如果parent域仍然為空，說明要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)

*T = node;

By: LI LIANGJI (Wechat:llj907015000)

No. 17 / 52

測(cè)試代碼

AVL樹(Balance Binary Tree)

平衡二叉樹排序樹(AVL樹)：

需要滿足如下的三個(gè)性質(zhì):

有一個(gè)樹 ，令 的左子樹的高度為 ，右子樹高度為

平衡因子

的左右子樹也為平衡二叉排序樹

如果插入節(jié)點(diǎn)使得

則必須旋轉(zhuǎn) 為 的節(jié)點(diǎn)

} else if (parent->rchild == p) {

parent->rchild = node;

} else {

parent->lchild = node;

}

free(pfree);

}

#include \"BSTree.h\"

int main(void) {

BSTree T = NULL;

Creat_BST(&T);

Delete_BST(&T, 53);

Delete_BST(&T, 12);

InOrder_BST(T);

system(\"pause\");

return 0;

}

// 45 24 53 12 90 0

By: LI LIANGJI (Wechat:llj907015000)

No. 18 / 52

定理1：

若一個(gè) 樹 在添加一個(gè)節(jié)點(diǎn) 后， 則 的雙親結(jié)點(diǎn) 的 不能為 葉子節(jié)點(diǎn)除外

令一顆 樹 在添加一個(gè)節(jié)點(diǎn) 后 ，且 的雙親節(jié)點(diǎn) 的

若刪去 節(jié)點(diǎn)，則 的高度并未發(fā)生變化，且 未發(fā)生變化

即 說明 在添加 節(jié)點(diǎn)之前不是 樹

不是一顆 樹

LL型旋轉(zhuǎn)(右旋轉(zhuǎn))

情況

且 ，以 的左孩子 為中心，向右旋轉(zhuǎn)

如下圖 為插入節(jié)點(diǎn)

定理2

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則旋轉(zhuǎn)后

情況

且 以 的左孩子 為中心向右旋轉(zhuǎn)，此時(shí) 成為 的左孩子， 稱成為 的左孩子

則 節(jié)點(diǎn)脫落 使 成為 的右孩子

如下圖 為插入節(jié)點(diǎn)

By: LI LIANGJI (Wechat:llj907015000)

No. 19 / 52

定理3

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則旋轉(zhuǎn)后

RR旋轉(zhuǎn)(左旋轉(zhuǎn))

情況

且 ，以 的右孩子 為中心，向左旋轉(zhuǎn)

如下圖 為插入節(jié)點(diǎn)

定理4

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則旋轉(zhuǎn)后

情況

且 以 的右孩子 為中心向左旋轉(zhuǎn)，此時(shí) 成為 的右孩子， 稱成為 的左孩子

則 節(jié)點(diǎn)脫落 使 成為 的右孩子

如下圖 為插入節(jié)點(diǎn)

By: LI LIANGJI (Wechat:llj907015000)

No. 20 / 52

定理5

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則旋轉(zhuǎn)后

LR旋轉(zhuǎn)(左右旋轉(zhuǎn))

情況

即將進(jìn)行旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) ，再 旋轉(zhuǎn)

如下圖， 為插入節(jié)點(diǎn)

定理6

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

情況

節(jié)點(diǎn) 有右孩子 ，即

即將進(jìn)行旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) 節(jié)點(diǎn)脫落 ，再 旋轉(zhuǎn) ，使 成為 的左孩子

如下圖， 為插入節(jié)點(diǎn)

By: LI LIANGJI (Wechat:llj907015000)

No. 21 / 52

定理7

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

情況

節(jié)點(diǎn) 有左孩子 ，即

即將進(jìn)行 旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) 節(jié)點(diǎn)脫落 ，再 旋轉(zhuǎn) ，使 成為 的有孩子

如下圖， 為插入節(jié)點(diǎn)

By: LI LIANGJI (Wechat:llj907015000)

No. 22 / 52

定理8

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

RL旋轉(zhuǎn)(右左旋轉(zhuǎn))

情況

即將進(jìn)行 旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) ，再 旋轉(zhuǎn)

如下圖， 為插入節(jié)點(diǎn)

定理9

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

By: LI LIANGJI (Wechat:llj907015000)

No. 23 / 52

情況

節(jié)點(diǎn) 有左孩子 ，即

即將進(jìn)行 旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) 節(jié)點(diǎn)脫落 ，再 旋轉(zhuǎn) ，使 成為 的左孩子

如下圖， 為插入節(jié)點(diǎn)

定理10

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

情況

節(jié)點(diǎn) 有右孩子 ，即

即將進(jìn)行 旋轉(zhuǎn)的樹 且 ，則 旋轉(zhuǎn) 節(jié)點(diǎn)脫落 ，再 旋轉(zhuǎn) ，使 成為 的左孩子

如下圖， 為插入節(jié)點(diǎn)

By: LI LIANGJI (Wechat:llj907015000)

No. 24 / 52

定理11

即將進(jìn)行 旋轉(zhuǎn)的樹 ， 且

則 旋轉(zhuǎn)后

總結(jié)

如果一個(gè) 樹 參入一個(gè)節(jié)點(diǎn)使得 的某個(gè)子樹的 ，則需要對(duì)該子樹進(jìn)行旋轉(zhuǎn)

令這顆子樹為

如果 ，且 的左子樹 為 ，則對(duì) 進(jìn)行 旋轉(zhuǎn)

如果 ，且 的左子樹 為 ，則對(duì) 進(jìn)行 旋轉(zhuǎn)

如果 ，且 的左子樹 為 ，則對(duì) 進(jìn)行 旋轉(zhuǎn)

如果 ，且 的左子樹 為 ，則對(duì) 進(jìn)行 旋轉(zhuǎn)

代碼實(shí)現(xiàn)

數(shù)據(jù)類型：

#define LH 1 //平衡因子1

#define EH 0 //平衡因子0

#define RH -1 //平衡因子-1

typedef int AVLElemtype;

typedef struct __AVLNode {

AVLElemtype key;

int bf; // balence factor

__AVLNode *lchild, *rchild;

} AVLNode, *AVLTree;

By: LI LIANGJI (Wechat:llj907015000)

No. 25 / 52

左旋轉(zhuǎn)和右旋轉(zhuǎn)(參照LL，RR旋轉(zhuǎn))

左旋轉(zhuǎn)樹 代表著：以 的右孩子為中心，向左旋轉(zhuǎn)

右旋轉(zhuǎn)樹 代表著：以 的左孩子為中心，向右旋轉(zhuǎn)

左平衡和右平衡

根據(jù)總結(jié)可知，大體上可以分成左平衡(LL,LR)和右平衡(RR,RL)

左平衡

#include \"AVLTree.h\"

void LeftRotate(AVLTree *T) {

AVLTree Rchild = (*T)->rchild; // Rchild代表T的右孩子

(*T)->rchild = Rchild->lchild; //參照RR旋轉(zhuǎn)

Rchild->lchild = *T; //旋轉(zhuǎn)后T成為Rchild的左孩子(定理3)

*T = Rchild;

//! 上行代碼不可省略，如果省略，則只改動(dòng)了節(jié)點(diǎn)間的關(guān)系，而未改變指針之間的關(guān)系

}

void RightRotate(AVLTree *T) {

AVLTree Lchild = (*T)->lchild;

(*T)->lchild = Lchild->rchild;

Lchild->rchild = *T;

*T = Lchild;

}

void LeftBalance(AVLTree *T) {

AVLTree L = (*T)->lchild; // L->bf絕對(duì)不可能為EH(定理1)

AVLTree Lr; // T的左孩子的右孩子

switch (L->bf) {

// LL 旋轉(zhuǎn)

case LH:

//! 定理2

(*T)->bf = L->bf = EH;

//! 此行的上下兩行不可對(duì)調(diào)

RightRotate(T);

break;

case RH:

// LR旋轉(zhuǎn)

Lr = L->rchild; //

switch (Lr->bf) {

case LH:

//定理8

(*T)->bf = RH;

L->bf = EH;

break;

case EH:

//定理6

(*T)->bf = L->bf = EH;

break;

By: LI LIANGJI (Wechat:llj907015000)

No. 26 / 52

右平衡

case RH:

//定理7

(*T)->bf = EH;

L->bf = LH;

break;

}

//根據(jù)定理6，7，8可知，旋轉(zhuǎn)后Lr的BF必定為0

Lr->bf = EH;

LeftRotate(&(*T)->lchild);

RightRotate(T);

break;

}

}

// 和左平衡同理

void RightBalance(AVLTree *T) {

AVLTree R = (*T)->rchild;

AVLTree Rl;

switch (R->bf) {

case RH:

(*T)->bf = R->bf = EH;

LeftRotate(T);

break;

case LH: {

Rl = R->lchild; //

switch (Rl->bf) {

case LH:

(*T)->bf = EH;

R->bf = RH;

break;

case EH:

(*T)->bf = R->bf = EH;

break;

case RH:

(*T)->bf = LH;

R->bf = EH;

break;

}

Rl->bf = EH;

RightRotate(&(*T)->rchild);

LeftRotate(T);

}

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 27 / 52

插入節(jié)點(diǎn)和及時(shí)平衡

//! 全局變量taller記錄高度是否發(fā)生變化，如果未發(fā)生變化為false，發(fā)生則true

bool __taller = false;

void Insert_AVL(AVLTree *T, AVLElemtype key, bool *taller) {

// T為要插入節(jié)點(diǎn)的雙親節(jié)點(diǎn)，key為要插入數(shù)據(jù)的值

//若T為空，則創(chuàng)建一個(gè)節(jié)點(diǎn)，并初始化

if (!(*T)) {

*T = (AVLTree)malloc(sizeof(AVLNode));

(*T)->lchild = (*T)->rchild = NULL;

(*T)->bf = EH;

(*T)->key = key;

*taller = true;

}

if (key < (*T)->key) {

//如果插入值小于T的key值，則遞歸T的左子樹，直到找到一個(gè)NULL節(jié)點(diǎn)

Insert_AVL(&(*T)->lchild, key, taller);

//判斷樹是否變高了

if (*taller) {

//以T為根插入節(jié)點(diǎn)，則T的bf發(fā)生變化

switch ((*T)->bf) {

case LH:

// T的bf == -1，向T的左孩子插入節(jié)點(diǎn)則T的bf = 2，需要左平衡

LeftBalance(T);

*taller = false;

//經(jīng)過平衡后taller = false，因?yàn)門經(jīng)過左調(diào)整后，變得平衡了

break;

case EH:

// 如果T的bf == 0，向T的左孩子插入節(jié)點(diǎn)，則T的bf = 1

(*T)->bf = LH;

//此時(shí)T的高度發(fā)生變化

*taller = true;

break;

case RH:

// 如果T的bf == -1，向T的左孩子插入節(jié)點(diǎn)，則T的bf = 0

(*T)->bf = EH;

//高度未發(fā)生變化

*taller = false;

break;

}

}

} else {

//和上面同理

Insert_AVL(&(*T)->rchild, key, taller);

if (*taller) {

switch ((*T)->bf) {

case LH:

(*T)->bf = EH;

*taller = false;

break;

case EH:

(*T)->bf = RH;

*taller = true;

break;

case RH:

RightBalance(T);

By: LI LIANGJI (Wechat:llj907015000)

No. 28 / 52

測(cè)試代碼

output:

哈希表(Hash Table)

記錄存儲(chǔ)位置與關(guān)鍵字之間存在對(duì)應(yīng)關(guān)系

用 表示

優(yōu)點(diǎn)：查找效率高

*taller = false;

break;

}

}

}

}

#include \"AVLTree.h\"

void Creat_AVL(AVLTree *T);

extern bool __taller;

int main(void) {

AVLTree T = NULL;

Creat_AVL(&T);

printf(\"In-order:\");

Traverse_Inorder(T);

printf(\"\

Pre-order:\");

Traverse_Preorder(T);

system(\"pause\");

return 0;

}

// 輸入數(shù)據(jù)：16 3 7 11 9 26 18 14 15 0

void Creat_AVL(AVLTree *T) {

*T = NULL;

AVLElemtype key;

scanf(\" %d\", &key);

// 0 代表輸入結(jié)束

while (key != 0) {

Insert_AVL(T, key, &__taller);

scanf(\" %d\", &key);

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 29 / 52

缺點(diǎn)：空間效率低

沖突：通過Hash函數(shù)，不同的關(guān)鍵字映射到同一個(gè)地址上

hash函數(shù)的構(gòu)造方法

需要考慮的因素：

執(zhí)行速度(計(jì)算時(shí)間)

關(guān)鍵字長(zhǎng)度

Hash Table的大小

關(guān)鍵字的分布情況

朝朝頻率

主要構(gòu)造方法 ：

直接定址法

數(shù)字分析法

平方取中法

折疊法

除留余數(shù)法

隨機(jī)數(shù)法

直接定址法：

優(yōu)點(diǎn)：以關(guān)鍵字key的某個(gè)線性函數(shù)值為散列地址，不會(huì)產(chǎn)生沖突

缺點(diǎn)：要占用連續(xù)地址空間，空間效率低

例

散列函數(shù)

處理沖突的方法

除留余數(shù)法：

為增量序列 表長(zhǎng)，且 是個(gè) 質(zhì)數(shù)

開放定址法：

基本思想：有沖突時(shí)就去尋找下一個(gè)空的散列地址，只要表足夠大，總能找到空的地址

常用方法：

By: LI LIANGJI (Wechat:llj907015000)

No. 30 / 52

線性探測(cè)法 為 ， ， ，

二次探測(cè)法 為

偽隨機(jī)數(shù)探測(cè)法 為偽隨機(jī)數(shù)數(shù)列

鏈地址法：

基本思想，相同散列地址的記錄鏈成一單鏈表

例：

已知一組關(guān)鍵字為 令

鏈地址法的優(yōu)點(diǎn)：

非同義詞不會(huì)沖突，無(wú)聚集現(xiàn)象

鏈表上空間動(dòng)態(tài)申請(qǐng)，更適用于表長(zhǎng)不確定的情況

除留余數(shù)法構(gòu)造Hash Table

類型定義：

初始化并構(gòu)造：

#define __m 11 // __m是表長(zhǎng)

#define __n 9 // 元素個(gè)數(shù)

#define NULLKEY 0 // 0意味著表空

typedef int HashElemType;

typedef char HashOther;

typedef struct __HashTable {

HashElemType key;

HashOther other;

} HashTable[__m];

void InitHashTable(HashTable hash) {

printf(\"Please input %d integer(s):\", __n);

int key;

// 初始化

memset(hash, 0, sizeof(HashTable));

By: LI LIANGJI (Wechat:llj907015000)

No. 31 / 52

搜索：

查找效率分析

Hash Table的ASL取決于：

散列函數(shù)

處理沖突的方法

散列表的裝填因子 表中元素個(gè)數(shù)

表長(zhǎng)

越接近 說明發(fā)生沖突的可能性越大

所以說Hash Table的查找效率 既不是 也不是

for (int i = 1; i < __n + 1; i++) {

scanf(\" %d\", &key);

int m_i = Hash(key);

if (hash[m_i].key == NULLKEY) {

hash[m_i].key = key;

} else {

for (int j = 1; j < __m; j++) {

int m_j = Hash(key + j);

if (hash[m_j].key == NULLKEY) {

hash[m_j].key = key;

break;

}

}

}

}

}

int Hash_Search(HashTable hash, HashElemType key) {

int m_i = Hash(key);

if (hash[m_i].key == NULLKEY)

return -1;

else if (hash[m_i].key == key)

return m_i;

else {

for (int i = 1; i < __m; i++) {

int m_j = Hash(key + i);

if (hash[m_j].key == NULLKEY)

return -1;

else if (hash[m_j].key == key)

return m_j;

}

return -1;

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 32 / 52

順序查找 折半查找 分塊查找

時(shí)間

復(fù)雜

度

與確定所在塊的查找方法有關(guān)

特點(diǎn) 算法簡(jiǎn)單，對(duì)結(jié)構(gòu)無(wú)要

求，效率底

對(duì)表結(jié)構(gòu)有要求，效

率高

對(duì)結(jié)構(gòu)有一定要求，效率介于順

序查找和折半查找之間

適用

情況

任何結(jié)構(gòu)的線性表，不

經(jīng)常做插入和刪除

有序的順序表，不經(jīng)

常做插入和刪除

塊間有序，塊內(nèi)無(wú)序的循序表，

經(jīng)常做插入和刪除

折半查找 二叉排序樹

時(shí)間復(fù)

雜度

特點(diǎn) 有序的順序表，插入和刪除需要移動(dòng)

大量元素

用二叉鏈表，插入和刪除無(wú)需移動(dòng)元素，只

需修改指針

適用情

況

不經(jīng)常插入刪除 經(jīng)常插入和刪除

拉鏈法

線性探測(cè)法

隨機(jī)探測(cè)法

幾點(diǎn)結(jié)論

散列表技術(shù)具有很好的平均性能，優(yōu)于一些傳統(tǒng)技術(shù)

鏈地址法優(yōu)于開地址法

除留余數(shù)法作散列函數(shù)優(yōu)于其他類型函數(shù)

查找總結(jié)

順序查找，折半查找，分塊查找比較

折半查找和二叉排序樹比較

哈希表:開地址法和鏈地址法比較

By: LI LIANGJI (Wechat:llj907015000)

No. 33 / 52

開地址法 鏈地址法

空間 無(wú)指針域，存儲(chǔ)效率高 附加指針域

時(shí)間復(fù)雜度 有二次聚集現(xiàn)象，查找效率低 無(wú)二次聚集現(xiàn)象，查找效率高

插入刪除 不易實(shí)現(xiàn) 易于實(shí)現(xiàn)

適用情況 表的大小固定，適用于表長(zhǎng)無(wú)變化 節(jié)點(diǎn)動(dòng)態(tài)生成，適用于表長(zhǎng)經(jīng)常變化

排序

排序方法的分類：

按數(shù)據(jù)存儲(chǔ)介質(zhì)：內(nèi)部排序和外部排序

內(nèi)部排序：數(shù)據(jù)量不大，數(shù)據(jù)在內(nèi)存，無(wú)需內(nèi)外存交換數(shù)據(jù)

外部排序：數(shù)據(jù)量較大，數(shù)據(jù)在外存(文件排序)

外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)存入外存

按比較器個(gè)數(shù)：串行排序和并行排序

串行排序：?jiǎn)翁幚頇C(jī)(同一時(shí)刻比較一對(duì)元素)

并行排序：多處理機(jī)(同一時(shí)刻比較多對(duì)元素)

按主要操作：比較排序和基數(shù)排序

比較排序：用比較的方法

基數(shù)排序：僅僅根據(jù)數(shù)據(jù)本身的取值

按輔助空間排序：原地排序和非原地排序

原地排序：輔助空間為 的排序

非原地排序：輔助空間大于 的排序

按穩(wěn)定性：穩(wěn)定排序和非穩(wěn)定排序

穩(wěn)定排序：任何數(shù)值相等的元素，排序以后相對(duì)次序不變

排序方法是否穩(wěn)定，并不能衡量一個(gè)排序算法的優(yōu)劣

按自然性：自然排序和非自然排序

自然排序：輸入數(shù)據(jù)越有序，排序的速度越快

排序類型定義：

#define SORTSIZE 20

typedef int SortType;

typedef char SortOther;

typedef struct __RecordType {

SortType key;

SortOther other;

} RecordType;

typedef struct __RecordList {

RecordType r[SORTSIZE + 1]; //數(shù)組中的0號(hào)位置作guard

int length;

} RecordList;

By: LI LIANGJI (Wechat:llj907015000)

No. 34 / 52

直接插入排序

若有 個(gè)元素需要進(jìn)行排序，令 到 為有序表 非遞減 ， 元素與該有序表比較，插入到適當(dāng)位置

為有序表 只有一個(gè)元素 ， 與該有序表比較，進(jìn)行插入，此時(shí)有序表變成 到

依此進(jìn)行插入

此時(shí) 到 為非遞減序列

代碼實(shí)現(xiàn)：

測(cè)試代碼：

void InsertSort(RecordList *List) {

for (int i = 2; i <= List->length; i++) {

// 因?yàn)橛術(shù)uard所以，i = 2，而不是 i = 1;

if (List->r[i].key < List->r[i - 1].key) {

// 判斷下標(biāo)為i的元素是否大于i-1，如果大于則不需要進(jìn)行排序

// 如果小于則需要進(jìn)行如下排序

List->r[0].key = List->r[i].key; //設(shè)置guard

List->r[i] = List->r[i - 1]; // 向后移動(dòng)

int j;

for (j = i - 2; List->r[0].key < List->r[j].key; j--) {

List->r[j + 1] = List->r[j];

}

// 當(dāng)上面循環(huán)結(jié)束后，下標(biāo)為j的元素此時(shí)小于guard，則向j的直接后繼(j+1)插入

List->r[j + 1] = List->r[0];

}

}

}

#include \"InsertSort.h\"

void input(RecordList *RL);

int main(void) {

RecordList RL;

RL.length = 9;

input(&RL);

InsertSort(&RL);

for (int i = 1; i <= RL.length; i++) {

printf(\"%d \", RL.r[i].key);

}

system(\"pause\");

return 0;

}

// 輸入數(shù)據(jù)：47 7 29 11 16 92 22 8 3

void input(RecordList *RL) {

RecordType *p = RL->r + 1;

for (int i = 1; i <= RL->length; i++) {

By: LI LIANGJI (Wechat:llj907015000)

No. 35 / 52

性能分析：

最壞情況

比較的次數(shù)

移動(dòng)的次數(shù)

平均情況

比較次數(shù)

移動(dòng)次數(shù)

最壞情況下

平均

折半插入排序(Binary Insert Sort)

在直接插入排序的基礎(chǔ)上，對(duì)已經(jīng)排序好的有序表進(jìn)行折半操作，隨著折半的進(jìn)行，right+1就是插入

的位置

SortType key;

scanf(\" %d\", &key);

p->key = key;

p++;

}

p = NULL;

}

void InserSotr_Binary(RecordList *List) {

for (int i = 2; i <= List->length; i++) {

List->r[0] = List->r[i];

int left = 1;

int right = i - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (List->r[0].key > List->r[mid].key) {

left = mid + 1;

} else {

right = mid - 1;

}

}

for (int j = i - 1; j >= right + 1; j--) {

List->r[j + 1] = List->r[j];

}

List->r[right + 1] = List->r[0];

By: LI LIANGJI (Wechat:llj907015000)

No. 36 / 52

折半插入性能：

時(shí)間復(fù)雜度

空間復(fù)雜度

是一種穩(wěn)定排序

直接插入和折半插入的比較

折半插入的比較次數(shù)和待排序序列的初始排列無(wú)關(guān)，僅依賴序列元素個(gè)數(shù)

折半插入減少了比較次數(shù)，但是沒有減少移動(dòng)次數(shù)

折半插入平均性能優(yōu)于直接插入排序

直接插入在基本有序時(shí)，效率更高

希爾排序(Shell's Sort)

希爾排序思路

增量序列 并且

對(duì)每個(gè) 進(jìn)行間隔插入排序

例如

則依此對(duì)將要排序的序列進(jìn)行間隔為 ， ， 的直接插入排序

希爾排序特點(diǎn)：

移動(dòng)位置較大，跳躍式地接近排序后的最終位置

最后一次只需要少量移動(dòng)

增量序列必須是遞減的，最后一個(gè)必須是1

增量序列必須是互質(zhì)的

代碼實(shí)現(xiàn)：

}

}

void ShellInsert(RecordList *L, int dk) {

for (int i = 1 + dk; i <= L->length; i++) {

if (L->r[i].key < L->r[i - dk].key) {

L->r[0] = L->r[i];

L->r[i] = L->r[i - dk];

int j;

for (j = i - (2 * dk); j > 0 && L->r[0].key < L->r[j].key; j -= dk) {

L->r[j + dk] = L->r[j];

}

L->r[j + dk] = L->r[0];

}

}

}

void ShellSort(RecordList *L, int *dt, int t) {

for (int i = 0; i < t; i++) {

ShellInsert(L, dt[i]);

}

By: LI LIANGJI (Wechat:llj907015000)

No. 37 / 52

測(cè)試代碼：

效率分析

增量序列 ，相鄰元素互質(zhì)

最壞情況

猜想

增量序列

或

猜想

最壞情況

}

#include \"InsertSort.h\"

void input(RecordList *RL);

int main(void) {

RecordList RL;

RL.length = 10;

int dt[3] = {5, 3, 1};

input(&RL);

ShellSort(&RL, dt, 3);

for (int i = 1; i <= RL.length; i++) {

printf(\"%d \", RL.r[i].key);

}

system(\"pause\");

return 0;

}

// 輸入數(shù)據(jù)：49 38 65 97 76 13 27 49 55 4

void input(RecordList *RL) {

RecordType *p = RL->r + 1;

for (int i = 1; i <= RL->length; i++) {

SortType key;

scanf(\" %d\", &key);

p->key = key;

p++;

}

p = NULL;

}

By: LI LIANGJI (Wechat:llj907015000)

No. 38 / 52

交換排序

冒泡排序

冒泡排序算法效率分析：

最好情況 正序

比較次數(shù)

移動(dòng)次數(shù)

最壞情況 逆序

比較次數(shù)

移動(dòng)次數(shù)

綜上

冒泡排序

最好

最壞

平均

需要輔助空間一個(gè)

冒泡排序是穩(wěn)定的

快速排序

基本思路：

選取序列 中第一個(gè)元素 作為 ，依此掃描序列，如果 小于 則排在 后面，反之排在前面

此時(shí)以 為中心，序列被分成兩個(gè)子序列

依此對(duì) 進(jìn)行取 操作，以此類推直到 中只有一個(gè)元素，此時(shí) 為有序序列

void BubbleSort(RecordList *L) {

bool flag = true;

for (int i = 1; i <= L->length - 1 && flag; i++) {

// 注意此行flag的位置,不要寫在j循環(huán)里面

flag = false;

for (int j = 1; j <= L->length - i; j++) {

if (L->r[j].key > L->r[j + 1].key) {

//只要發(fā)生一次交換，flag就為true

flag = true;

RecordType temp = L->r[j];

L->r[j] = L->r[j + 1];

L->r[j + 1] = temp;

}

}

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 39 / 52

代碼實(shí)現(xiàn):

//找pivot

int Partition(RecordList *L, int left, int right) {

L->r[0] = L->r[left];

while (left < right) {

while (left < right && L->r[0].key <= L->r[right].key)

// 必須<=，如果不加等于號(hào)，則死循環(huán)

right--;

L->r[left] = L->r[right];

while (left < right && L->r[0].key >= L->r[left].key)

left++;

L->r[right] = L->r[left];

}

//此時(shí) left和right重疊

L->r[left] = L->r[0];

return left;

}

//排序模型

void QSort(RecordList *L, int left, int right) {

if (left < right) {

//獲取pivot位置

int pivot = Partition(L, left, right);

// pivot把序列分成兩塊，并分別遞歸

QSort(L, left, pivot - 1);

By: LI LIANGJI (Wechat:llj907015000)

No. 40 / 52

快速排序算法效率：

平均效率為

快速排序不是原地排序

需要借助遞歸來(lái)實(shí)現(xiàn)，調(diào)用棧

平均情況下需要 的棧空間

最快情況

快速排序不是一種穩(wěn)定排序

若對(duì) 或 進(jìn)行快速排序

以 為中心，必然有一側(cè)的子序列個(gè)數(shù)為 ，那么此時(shí)退化成冒泡排序

所以快速排序不適用于原本有序或基本有序的序列

總結(jié)

的選取直接影響快排性能

數(shù)據(jù)次序越亂，快排越快，效率越高

快速排序不是自然排序方法

改變 的選取方法，至多只能改變算法平均情況下的效率，無(wú)法改變最快情況下的效率

即最壞情況

選則排序

QSort(L, pivot + 1, right);

}

}

// 為了使用方便，封裝函數(shù)

void QuickSort(RecordList *L) {

QSort(L, 1, L->length);

}

void SelectionSort(RecordList *L) {

int i, j;

for (i = 1; i < L->length; i++) {

int k = i; // k記錄最大值或最小值

for (j = i + 1; j <= L->length; j++) {

By: LI LIANGJI (Wechat:llj907015000)

No. 41 / 52

測(cè)試代碼

算法效率分析:

時(shí)間復(fù)雜度

記錄移動(dòng)次數(shù)

最好情況

最壞情況

比較次數(shù)

無(wú)論待排序處于什么狀態(tài)，選則排序所需進(jìn)行的比較次數(shù)都相同

算法特點(diǎn)

就選則排序本身來(lái)講，是一種穩(wěn)定的排序方法，穩(wěn)定取決于是否在在比較時(shí)加入等號(hào)

可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

移動(dòng)記錄次數(shù)較少，當(dāng)每一記錄占用空間較多時(shí)，此方法比直接插入排序塊

if (L->r[k].key < L->r[j].key) //從大到小排序

k = j; // k記錄最大值

}

if (k != i) { //如果k!=i 說明有值比i大

SortType temp = L->r[i].key;

L->r[i].key = L->r[k].key;

L->r[k].key = temp;

}

}

}

#include \"ExchangeSort.h\"

void input(RecordList *RL);

int main(void) {

RecordList RL;

RL.length = 10;

input(&RL);

SelectionSort(&RL);

for (int i = 1; i <= RL.length; i++) {

printf(\"%d \", RL.r[i].key);

}

system(\"pause\");

return 0;

}

// 輸入數(shù)據(jù)：49 38 65 97 76 13 27 49 55 4

By: LI LIANGJI (Wechat:llj907015000)

No. 42 / 52

堆

堆定義

若 個(gè)元素的序列為

滿足如下條件

小根堆 或 大根堆

從上述定義可知，堆實(shí)質(zhì)上就是一個(gè)完全二叉樹 二叉樹中任意非葉子節(jié)點(diǎn)均小于 大于 它的孩子節(jié)點(diǎn)

如下圖

定理1:

若有數(shù)列 有 個(gè)元素，若按照按下標(biāo) 存入一顆樹中，則此顆樹為完全二叉樹

定理2:

若有數(shù)列 有 個(gè)元素，若按照按下標(biāo) 存入一顆完全二叉樹中，令

為堆

根據(jù)完全二叉樹的性質(zhì)可知 為序號(hào)最大的非葉子節(jié)點(diǎn)

葉子節(jié)點(diǎn)本身為堆，所以 到 為堆

初始化堆

若在輸出堆頂?shù)淖钚≈?最大之后 ，使剩余 個(gè)元素的序列重新組成一個(gè)堆

則得到 個(gè)元素中的次小值 次大值

對(duì) 執(zhí)行如上操作，得到一個(gè)有序序列，此過程為堆排序

By: LI LIANGJI (Wechat:llj907015000)

No. 43 / 52

堆調(diào)整

根據(jù)定理 可知， 到 為堆，那么只需要判斷 到 是否為堆

如果 到 不為堆，選取 和 交換，此時(shí) 為堆

但是交換了 和 ，無(wú)法保證交換后的序列是否為堆，所以還要繼續(xù)調(diào)整

令 繼續(xù)調(diào)整，直到

堆排序

堆初始化雖然完成并且有序，但是 到 并不是有序

此時(shí)堆頂元素為 交換堆頂元素和 號(hào)元素

并且對(duì) 到 進(jìn)行堆調(diào)整，此時(shí) 號(hào)元素為

依此類推，繼續(xù)交換堆頂和 ，并對(duì) 到 進(jìn)行堆調(diào)整

直到

堆排序算法效率分析

void HeapAdjust(RecordList *L, int s, int n) {

RecordType temp = L->r[s]; // temp暫存，用來(lái)作哨兵

for (int j = 2 * s; j <= n; j *= 2) {

//此處 j<n 確保了如果j是序列最后的元素不進(jìn)行比較

if (j < n && L->r[j].key < L->r[j + 1].key)

j++; // j記錄最大值

//如果j的key<=temp 說明temp為根的大根堆

if (L->r[j].key <= temp.key)

break;

//因?yàn)閖.key > s.key 所以把j賦給s

L->r[s] = L->r[j];

//! 注意并不需要更改j

// 因?yàn)楫?dāng)發(fā)生堆調(diào)整時(shí)j會(huì)賦值給s，并且s=j,即再次循環(huán)發(fā)生堆調(diào)整時(shí)，s變動(dòng)，也就是說上一個(gè)j發(fā)

生變動(dòng)

//所以不用特地給j賦值。

s = j;

}

//當(dāng)循環(huán)結(jié)束再給s賦值，也就是給上一個(gè)j賦值

L->r[s] = temp;

}

void HeapSort(RecordList *L) {

InitHeap(L);

for (int i = L->length; i > 1; i--) {

RecordType temp = L->r[1];

L->r[1] = L->r[i];

L->r[i] = temp;

HeapAdjust(L, 1, i - 1);

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 44 / 52

初始化堆

交換堆頂元素和 元素，并重新堆調(diào)整

所以堆排序

具體推導(dǎo)過程在書中 第二版 頁(yè)

堆排序的特點(diǎn)

不是穩(wěn)定排序

只能用于順序結(jié)構(gòu)，不能用于鏈?zhǔn)浇Y(jié)構(gòu)

堆排序在最壞情況下時(shí)間復(fù)雜度也為 ，無(wú)論待排序序列是正序還是逆序都一樣

初始化堆時(shí)，需要比較的次數(shù)較多，因此記錄較少時(shí)不宜采用。堆排序在最壞情況下 ，

相對(duì)于快速排序最壞情況 而言是一個(gè)優(yōu)點(diǎn)，當(dāng)記錄較多時(shí)效率高

其他類型排序

并歸排序 Merge Sort

基本思想

若有序列

其中 為非遞減序列 也為非遞減序列

依此比較 取較小值放入新建序列

依此類推得到的序列 為有序序列

但是如果一個(gè)雜亂無(wú)章的序列應(yīng)該如何應(yīng)用

若有序列

依此對(duì)該序列進(jìn)行二分，直到獲得只有一個(gè)元素的子序列

如下圖

比較 和 較小值放入 充當(dāng) ，較大值則充當(dāng) ，此時(shí) 為有序序列

按照此方法遞歸，可以得到有序序列

例子

By: LI LIANGJI (Wechat:llj907015000)

No. 45 / 52

實(shí)現(xiàn)代碼

合并兩個(gè)有序序列

//令R的1到mid為有序序列，mid+1到n為有序序列

void Merge(RecordType *R, RecordType *Temp, int left, int mid, int right) {

int i = left, j = mid + 1, k = left;

while (i <= mid && j <= right) {

//利用三目運(yùn)算符簡(jiǎn)化語(yǔ)句

// <= 保證了穩(wěn)定性

Temp[k++] = (R[i].key <= R[j].key ? R[i++] : R[j++]);

}

while (i <= mid)

Temp[k++] = R[i++];

while (j <= right)

Temp[k++] = R[j++];

}

By: LI LIANGJI (Wechat:llj907015000)

No. 46 / 52

分割序列并進(jìn)行合并

函數(shù)封裝

算法效率

時(shí)間復(fù)雜度

空間復(fù)雜度

是穩(wěn)定排序

可以用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，且不需要附加存儲(chǔ)空間，但遞歸的實(shí)現(xiàn)仍要需要開辟相應(yīng)的工作棧

基數(shù)排序

前面的算法都是基于比較，而基數(shù)排序則不需要比較，通過關(guān)鍵字中的信息進(jìn)行分類，進(jìn)行分配和采

集來(lái)實(shí)現(xiàn)排序

如下圖

先按照個(gè)位排序

void MSort(RecordType *R, RecordType *Temp, int left, int right) {

//遞歸函數(shù)的出口為left = right = 1 和 left = right = mid+1

if (left >= right)

return;

int mid = (left + right) >> 1;

MSort(R, Temp, left, mid);

MSort(R, Temp, mid + 1, right);

Merge(R, Temp, left, mid, right);

//! 注意：此函數(shù)的核心語(yǔ)句為下行的循環(huán)

//! 每一次遞歸都需要更新R數(shù)組，因?yàn)檫M(jìn)行棧底遞歸時(shí)，R必須為以mid為中心，兩側(cè)都是有序序列

for (int i = left; i < right + 1; ++i) {

R[i] = Temp[i];

}

}

void MergeSort(RecordList *L) {

RecordType Temp[L->length + 1];

MSort(L->r, Temp, 1, L->length);

}

By: LI LIANGJI (Wechat:llj907015000)

No. 47 / 52

再按照十位排序

再按百位排序

By: LI LIANGJI (Wechat:llj907015000)

No. 48 / 52

數(shù)據(jù)類型定義

采用靜態(tài)鏈表來(lái)對(duì)3位數(shù)字排序

分配函數(shù)

收集函數(shù)

#define MAXBIT 3 //排序的關(guān)鍵字為3位

#define RADIX 10 //對(duì)10進(jìn)制進(jìn)行排序

#define MAX_SPACE 100 //最多可以有99個(gè)待排序元素，因?yàn)橛幸粋€(gè)頭節(jié)點(diǎn)

struct SLCell { //元素類型

SortType keys[MAXBIT]; //存儲(chǔ)個(gè)位，十位，百位

SortOther other; //其他信息

int next; //存放下一個(gè)元素在數(shù)組中的位置

};

struct SLList {

SLCell r[MAX_SPACE]; // r[0]不存放數(shù)據(jù)，類似于鏈表的頭指針

int bitnumber; //表示此靜態(tài)鏈表對(duì)n位數(shù)排序

int length; //表中有效元素個(gè)數(shù)

};

typedef int RadixArr[RADIX]; //用于創(chuàng)建first, end 數(shù)組

void Distrubute(SLCell *r, int i, RadixArr first, RadixArr end) {

// r表示 SLCell數(shù)組的首地址，i=0,i=1,i=2 分別表示對(duì)百位，十位，個(gè)位進(jìn)行分配

// first數(shù)組存放首個(gè)被分配的下標(biāo)，end存放first指向的最后元素

memset(first, 0, sizeof(int) * RADIX); //初始化為0

memset(end, 0, sizeof(int) * RADIX);

for (int p = r[0].next; p; p = r[p].next) {

//因?yàn)閞[0]為頭指針，所以p指向表中第一個(gè)元素

int j = r[p].keys[i]; // j為下標(biāo)，等式右邊則表示映射關(guān)系

//如果first[j]==0說明first指向任何元素，直接把p賦給first[j]，

if (!first[j])

first[j] = p;

else {

// first[j]已經(jīng)有指向，那么需要找到end[j]，并把它們連起來(lái)

r[end[j]].next = p;

}

//因?yàn)閜指向新加入的元素，所以最后一個(gè)元素變成p

end[j] = p;

}

}

void Collect(SLCell *r, int i, RadixArr first, RadixArr end) {

//此時(shí)分配已經(jīng)完成，需要做的是按順序把分配的元素連起來(lái)，即收集

int j = 0;

//尋找第一個(gè)非空的first子表

By: LI LIANGJI (Wechat:llj907015000)

No. 49 / 52

排序函數(shù)

初始化和輸出函數(shù)

while (!first[j])

j++;

//此時(shí)j指向第一個(gè)非空子表

r[0].next = first[j]; //讓頭指針指向此子表

int tail = end[j]; // tail代表此子表最后元素的下標(biāo)

//尋找第2個(gè)非空子表，依此類推，直到j(luò)>=Radix

for (j = j + 1; j < RADIX; j++) {

if (!first[j])

continue; //如果子表為空則跳過

else { //當(dāng)不為空時(shí)

r[tail].next = first[j]; //讓上一個(gè)子表的最后一個(gè)元素指向first[j]

tail = end[j]; //此時(shí)更新尾部下標(biāo)

}

}

//當(dāng)下面循環(huán)結(jié)束后，說明收集完畢

r[tail].next = 0;

}

void RadixSort(SLList *L) {

//創(chuàng)建first,end數(shù)組，不需要初始化，因?yàn)镈istrubute(函數(shù)會(huì)進(jìn)行初始化)

RadixArr first, end;

//因?yàn)槭庆o態(tài)鏈表，需要更新next

for (int i = 0; i < L->length; ++i) {

L->r[i].next = i + 1;

}

L->r[L->length].next = 0; //設(shè)置結(jié)束表示0

//因?yàn)槭菍?duì)三位數(shù)進(jìn)行分配，依此對(duì)個(gè)位，十位，百位進(jìn)行分配并收集

for (int i = L->bitnumber - 1; i >= 0; --i) {

Distrubute(L->r, i, first, end);

Collect(L->r, i, first, end);

}

}

void Init_Radix_3(SLList *L, int n) {

int hundreds, tens, ones;

printf(\"Please input %d intergers(tree digits):\", n);

for (int i = 1; i < n + 1; ++i) {

int value;

scanf(\" %d\", &value);

ones = value % 10;

tens = (value / 10) % 10;

hundreds = value / 100;

L->r[i].keys[0] = hundreds;

L->r[i].keys[1] = tens;

L->r[i].keys[2] = ones;

By: LI LIANGJI (Wechat:llj907015000)

No. 50 / 52

排序方法 最好情況 最壞情況 平均情況 空間復(fù)雜度 穩(wěn)定性

直接插入排序 穩(wěn)定

折半插入排序 穩(wěn)定

希爾排序 不穩(wěn)定

冒泡排序 穩(wěn)定

簡(jiǎn)單選擇排序 穩(wěn)定

快速排序 不穩(wěn)定

堆排序 不穩(wěn)定

歸并排序 穩(wěn)定

基數(shù)排序 穩(wěn)定

算法效率

令基數(shù)為 有 個(gè)記錄，每個(gè)記錄含有 個(gè)關(guān)鍵字，則分配需要 ，收集則需要

所以

需要兩個(gè)長(zhǎng)度為 的 數(shù)組，且還增加了個(gè) 個(gè) 元素

所以空間復(fù)雜度

算法特點(diǎn)：

穩(wěn)定排序

可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

只要基數(shù)選取合適，時(shí)間復(fù)雜度是線性的可以達(dá)到

有嚴(yán)格的使用要求：需要直到各級(jí)關(guān)鍵字的主次關(guān)系和取值范圍

排序總結(jié)

}

L->length = n;

L->bitnumber = 3;

}

void Display_Radix(SLList *L) {

for (int p = L->r[0].next; p != NULL; p = L->r[p].next) {

for (int i = 0; i < L->bitnumber; i++) {

printf(\"%d\", L->r[p].keys[i]);

}

printf(\" \");

}

}

By: LI LIANGJI (Wechat:llj907015000)

No. 51 / 52

按照時(shí)間性能來(lái)區(qū)分：

有 快速排序，歸并排序，堆排序，其中快速排序最好

有 直接插入排序，冒泡排序，簡(jiǎn)單選擇排序，其中直接插入最好

特別是對(duì)于關(guān)鍵字近似有序的記錄

只有 基數(shù)排序

當(dāng)待排記錄有序時(shí)，直接插入排序和冒泡排序能達(dá)到 ，而對(duì)于快速排序而言，這是最不好的情況

此時(shí)快速排序

簡(jiǎn)單選則排序，堆排序，歸并排序的效率并不能根據(jù)關(guān)鍵字的分布而改變

按空間性能來(lái)區(qū)分

所有簡(jiǎn)單排序方法 直接插入，冒泡，簡(jiǎn)單選擇排序 和堆排序?yàn)?/p>

快速排序?yàn)?需要借助棧

歸并排序需要輔助空間最多，

鏈?zhǔn)交鶖?shù)排序需要 ， 數(shù)組和 變量

按穩(wěn)定性來(lái)區(qū)分

快速排序和堆排序不是穩(wěn)定的方法

By: LI LIANGJI (Wechat:llj907015000)

No. 52 / 52