第 八 章 排 序
基本概念
排序是计算机程序设计中的一种重要运算,其功能是将一
个数据元素 (或记录 )的任意序列,重新排列成一个按关键字有
序的序列,
排序的确切定义为, 设含有 n个记录的序列为 ? ?nRRR,,,21 ?
其相应的关键字序列为 ? ?
nKKK,,,21 ?,需确定一种排列
,,,2,1 pnpp ? 使其相应的关键字满足如下的非递减关系
? ?pnpp KKK ??? ?21,或非递增关系 ? ?pnpp KKK ??? ?21
即使原来的序列 ? ?
nRRR,,,21 ?
成为一个按关键字有序的序列
? ?pnpp RRR,,,21 ?,这样的一种操作称为排序,
定义中的关键字
iK
可以是记录 ),,2,1( niR
i ??
主关键字
此时任何一个记录的无序序列经排序后得到的结果是唯一的,
当 是记录
iK iR
的次关键字时,则排序的结果不唯一,因待
排序的记录序列中可能存在两个或两个以上关键字相等的
记录, 关键字
iK
可以是记录中的单个数据项,也可是若干
数据项的组合,
假设 ),1,1( jinjniKK
ji ??????
,且在排列前的
序列中
iR
领先于
jR
(即 ji? ),若在排序后的序列中
iR
仍领
领先于
jR
,则称所用的排序方法是稳定的 ;反之,若可能使
排序后的序列中
jR
领先于
iR,则称所用的排序方法是不稳
定的,
由于待排序的记录数量不同,使排序过程中涉及的存
储器不同,由此排序方法分为两大类,
1,内部排序, 待排序记录存放在计算机随机存储器中进行
的排序过程,
2,外部排序, 当待排序记录数量很大,以至内存一次无法
容纳全部记录,排序过程中需对外存进行访问的排序过程,
本章只讨论内排序, 在排序过程中需进行两种操作,
(1)比较两个关键字的大小,这对大多数排序方法都是必
要的,
(2)将记录从一个位置移动到另一个位置,并非必需,可
通过改变记录的存储方式予以避免,
待排序的记录序列可有三种存储方式,
(1)以一维数组作为存储结构,排序过程是对记录本身进
行物理重排,即通过比较和判定,把记录移到合适的
位置,
(2)以链表 (动态链表或静态链表 )作为存储结构,排序过程
中无需移动记录,仅需修改指针即可,
(3)有的排序方法难于在链表上实现,若仍需 避免 排序过程
中记录的移动,可建立一辅助表 (如包括关键字和指向
记录的指针组成的索引表 ),从而,排序过程中只需对
辅助表的表目进行物理重排,只移动辅助表的表目,而
不移动记录本身,
8.1 插入排序
8.1.1直接插入排序
这是一种最简单的排序方法,具体做法是在插入第 i
个记录时,? ?
121,,,?iRRR ?
已排好序,这时将关键字
iK
依
次与关键字 ? ?
121,,,KKK ii ??? 进行比较,从而找到应插入
的位置,然后将
iK
对应的记录
iR 插入,原位置的记录向后
顺推, 下面举例说明其手工操作的过程,
要求将下面一组以其关键字值表示的初始排列无序的
记录,用 直接插入法排序成非递减有序序列,
在手工操作的过程中,i的值 表示第几趟插入,[ ]中的
序列表示已排好序的记录序列,
序列的初始状态为,
下面给出直
接插入排序
的 C函数,其
功能是对以
一维数组存
储的一组无
序记录排列
成非递减有
序序列,
? ? 4725117282613347
? ? 47251172826147331?i
? ? 47251172826147332?i
? ? 47251172826147333?i
? ? 47251182726147334?i
? ? 47258272614733115?i
? ? 47827261473325116?i
]8272614747332511[7?i
struct node
{ int key; int data; };
typedef struct node NODE;
void insertsort(r,n)
NODE r[ ]; int n; /* r[ ]为具有 n+1个单元的数组,n为记录个数 */
{ int i,j;
for(i=2;i<=n;i++)
{ r[0]=r[i]; /* 将待排序记录赋予下监视哨 */
j=i-1;
while(r[0].key<r[j].key) /*待排序记录的关键字值与有序子序列 */
/*的各记录的关键字值进行比较 /*
r[j+1]=r[j--]; /*若条件真,则 r[j]记录后移 */
r[j+1]=r[0]; /*若条件假,则待排序记录插入到相应位置 */
}
}
算法简洁 ﹑ 容易实现是直接插入排序的两大特点,
下面 分析其时间效率,
整个排序过程中只有比较关键字和移动记录两种运
算, 当原始记录已按关键字非递减有序,即为正序时,
时间效率最高,因完成每趟排序仅需进行一次比较及两
次移动记录操作 (即开始时将记录移至监视哨中和最后将
记录移入适当位置 ),整个排序过程总的比较次数为 n-1,
记录总的移动次数为 2(n-1),故其时间复杂度为 O(n);
反之,如果原始记录是按关键字非增减有序的,即为
逆序时,时间效率最低,因要插入的第 i个记录,均要与
前 i –1个记录及监视哨的关键字进行比较,即每趟要进行
i次比较,总的比较次数为,
2/)1)(2(
2
????
?
nnin
i
从移动记录的次数来看,每趟排序中除了上面提到的两
次移动外,还需将有序子序列中关键字值大于待排序记
录的关键字值的记录后移一个位置,总的移动次数为,
2/)1)(4()1(
2
?????
?
nnin
i故其时间复杂度为
).( 2nO
若在随机情况下,设待排序记录序列可能出现的各
种排列的概率相同,则可取上述两种极端情况的平均值
作为比较和移动记录的平均次数,约为 4/2n, 由此,直
接插入排序的时间复杂度为 ).( 2nO
直接插入排序是稳定的排序方法,
对于直接插入排序,补充一 C函数,其功能为, 将
以带头结点的单链表存储的一组无序记录,排序成非递
减序列,
struct node
{ int key; struct node *next; };
typedef struct node NODE;
void insertsort(h)
NODE *h;
{ NODE *p,*r,*l,*q;
int exchang;
l= h->next; /*l指向有序子表的表尾 */
q=l->next; /*q指向待排序的结点 */
while(q!=null)
{ p=h->next; /* p指向有序子表的表头,排序过程中可向表尾移动 */
r=h; /* r指向 p的直接前趋结点 */
exchang=0;/*标识结点未交换 */
while(p!=q && exchang==0)
{ if(p->key<=q->key)
{ r=p; p=r->next; } /*结点后移 */
else
{ l->next=q->next;
q->next=p;
r->next=q; /*待排序的结点前插 */
exchang=1; /*标识结点有交换 */
}
}
if(p==q) l=q;/*一趟排序未交换,q指向的待排序结点成为有 */
/*序子表的表尾结点 */
q=l->next; /*q指向下一趟排序的待排序结点 */
}
}
8.1.1希尔排序
希尔排序是对直接插入排序法的一种改进,提高了
排序的效率, 希尔排序的作法是, 先取定一个小于待排
序记录个数 n的整数 1d 作为第一个增量,将 待排序的所有
记录分成 个组,将所有距离为
1d 1d
倍数的记录放在同一
个组中,在各组内进行直接插入排序 ; 然后取第二个增
量
12 dd ?
重复上述分组和排序工作,依此类推,直至所
取的增量 )(1
121 ddddd iii ???? ? ?,即所有记录放在
同一组中进行直接插入排序为止, 因此,希尔排序又叫
“缩小增量排序”,
对增量有多种取法,希尔给出的取法为,
? ? ? ?2/,2/ 11 ii ddnd ?? ?
上式中,n为待排序记录的个数,? ?ni 2lo g,,2,1 ??
下面通过一个具体例子来看 希尔排序的过程,
设有一组初始关键字如下所示,
47 33 61 82 72 11 25 47 57 02
n =10,? ? 52/
1 ?? nd
排序过程如下,
47 33 61 82 72 11 25 47 57 0251 ?d
47 11
33 25
61 47
82 57
72 02
对上面分成的五组记录,分别在各组内进行直接插入排序,
第一趟排序结果, 11 4725 3347 6157 8202 72
对第一趟排序结果进行第二次分组,取增量
? ? ? ? 22/52/12 ??? dd
11 25 47 57 02 47 33 61 82 72
11对上面分成的二组记录,分别在各组内进行直接插入
排序,
22 ?d
11 47 02 33 82
25 57 47 61 72
第二趟排序结果, 02 11 33 47 8225 47 57 61 72
对第二趟排序结果进行第三次分组,取增量
? ? ? ? 12/22/23 ??? dd
第三趟排序结果, 02 11 25 33 47 47 55 61 72 82
由上例结果,似乎 希尔排序是稳定的,其实不然,它是不
稳定的, 对于一种排序方法,只要举出一个例子是不稳定
的,则这种排序方法就是不稳定的, 例如,对于下例,
5 3 4 5 1
增量分别取 2,1,希尔排序结果为 1 3 4 5 5,不 稳定,
所以,希尔排序是不稳定的,
希尔排序的时间复杂度约为
8.2 交换排序
交换排序的基本思想是, 两两比较待排序记录的关
键字,发现两个记录的次序相反时即进行交换,直至没
有反序的记录为止,
8.2.1冒泡排序
冒泡排序也是一种简单的排序方法,其基本操作是,
通过对相邻关键字的比较和交换,使全部记录排列有序,
冒泡排序的过程, 为形象地表示关键字值最小的记
录象汽泡一样往上冒 (或关键字值最大的记录象石块一样
往下沉 ),将一组按关键字值无序的记录纵向排列,然后
自下而上地对每两个相邻的关键字进行比较,若为逆序
)( 3.1nO
)2,,1,(1 ????? nnjKK jj,则将两个记录交换位置,这样
的操作反复进行,直至全部记录都比较 ﹑ 交换完毕为止
经过第一趟冒泡排序之后,就将关键字值最小的记录
安排在第一个记录的位置上,显然,对于有 n个记录的
一组序列,第一趟排序需比较 n-1次,而交换记录位置的
次数与待排序记录的初始排列状态有关 ; 然后,对后 n-1
个记录重复进行同样的操作,则将具有次小关键字值的
记录安排在第二个记录的位置上, 重复以上过程,直至
在某趟排序中没有记录需要交换为止, 举例,
初
始
47
33
61
82
72
11
25
47
47
33
61
82
11
72
25
47
47
33
61
11
82
72
25
47
47
33
11
61
82
72
25
47
47
11
33
61
82
72
25
47
一
趟
11
47
33
61
82
72
25
47
二
趟
11
25
47
33
61
82
72
47
三
趟
11
25
33
47
47
61
82
72
四
趟
11
25
33
47
47
61
72
82
五
趟
11
25
33
47
47
61
72
82
分析冒泡排
序的过程可
见,若初始
记录的顺序
是按关键字
非递减有序
的,则只需
进行一趟排
序,比较次数为 n-1次,记录的移动次数为 0,即比较次
数和移动次数均为最小值 ; 若初始记录按关键字为逆序
即非递增有序时,则需进行 n-1趟排序,总比较次数为
22
)1()( 21
1
nnninn
i
??????
?
,总移动次数为,
22
)1)(4()1( 2
2
nnnin
i
??????
?
,也即比较和移动次数次
数均为最大值,因此,冒泡排序的时间复杂度为 )( 2nO
冒泡排序也是一种稳定的排序方法,
下面先补充以顺序存储结构即一维数组存储待排序
记录的 C函数,
struct node
{ int key,data;}
typedef struct node NODE;
void bubblesort(r,n)
NODE r[ ]; int n;
{ NODE temp; int i,top,boolean;
top=0;
do
{ boolean=0;
for(i=n-1; i>top; i--)
if(r[i].key<r[i-1].key)
{ temp= r[i]; r[i]=r[i-1];
r[i-1]= temp; boolean=1;}
top++;
}
while(boolean==1); }
再补充以带头结点的单链表存储待排序记录的 C函数,
struct node
{ int key,data; struct node *next;}
typedef struct node NODE;
void bubbllinkesort(h)
NODE *h;
{ NODE *f,*p,*q,*r ; int boolean=0;
f=h; p=head->next; q=p->next; r=null;
while(boolean==0)
{ boolean=1;
while(q!=r)
{ if(p->key>q->key)
{ f->next=q; p->next=q->next; q->next=p; f=q; boolean=0;}
else
{ f=p; p=q; }
q=p->next;
}
r=p; f=head; p=f->next; q=p->next;
}
}
8.2.2 快速排序
快速排序也是一种籍助交换进行排序的方法,由冒
泡排序改进而得,是目前内部排序中速度较快的方法,
快速排序又称为分区交换排序,其基本思想是, 设
待排序的一组记录中含有 n个记录,任取其中一个记录 (通
常选取第一个记录 )的关键字作为控制关键字 (相应的记录
称为控制记录 ),以控制记录为分界点,经一趟排序后,
将全部记录分为两部分, 所有关键字值比控制关键字值
小的记录都安置在控制记录之前,所有关键字值比控制
关键字值大的记录都安置在控制记录之后,然后再分别
对这两部分无序子区间中的记录重复上述过程,直至每
一部分子区间中只剩下一个记录为止,
下面举例介绍快速排序的具体做法,
设两个整数类型指针 i和 j,其初态分别指向一组待排
序记录的第一个记录和最后一个记录,如下所示,
47 33 61 82 72 11 25 47 57 02初始状态
i j
选第一个记录为控制记录,并将其送入暂存变量 x中,用
空的方框代替控制记录, 一趟排序的过程如下,
初始状态 33 61 82 72 11 25 47 57 02
i j
令 j自 n起向左扫描,因 02<47,将
02放入 i所指位置,j不变,i = i +1,
[02] 33 61 82 72 11 25 47 57
i j
令 i自当前位置起向右扫描,33<47
i = i +1.
i
61>47,61放入 j 所指位置
i不变,j = j -1.
[02 33] 82 72 11 25 47 57 [61]
i j
[02 33 25] 82 72 11 [47 57 61]
i j
令 j自当前位置起向左扫描,直至 j
所指记录的关键字值比控制关键
j
字值小为止,25放入 i所指位置,i = i +1.
令 i自当前位置起向右扫描,82>47
82放入 j 所指位置,i不变,j = j -1.
令 j自当前位置起向左扫描,直至 j
所指记录的关键字值比控制关键
字值小为止,11<47,11放入 i所指
位置,i = i +1,j不变,
[02 33 25] 72 11 [82 47 57 61]
i j
[02 33 25 11] 72 [82 47 57 61]
i j
令 i自当前位置起向右扫描,72>47
72放入 j 所指位置,i不变,j = j -1.
[02 33 25 11] [ 72 82 47 57 61]
i j
当一趟排序过程中的某次扫描结束后,出现 i = j则表明此趟排序
结束,将暂存在变量 x中的控制记录放入 i或 j所指的位置上,
47
一趟排序结束后,以控制记录所在位置为分界点,将一组记录分
左右两个用方括弧括起的无序子区间,如下所示,
[02 33 25 11] 47 [ 72 82 47 57 61]一趟排序之后,
然后对上面结果的左右无序子区间再分别反复进行快
速排序,直至每一部分子区间中只剩下一个记录为止,
将各趟排序后的结果演示于下,
一趟排序之后,
二趟排序之后,
[02 33 25 11] 47 [ 72 82 47 57 61]
02 [33 25 11] 47 [61 57 47] 72 [ 82]
三趟排序之后,02 [11 25] 33 47 [47 57] 61 72 82
四趟排序之后, 02 11 25 33 47 47 57 61 72 82
快速排序的 C函数如下,
struct node
{ int key,data; }
typedef struct node NODE;
void quicksort(r,n)
NODE r[ ]; int n;
{struct stack
{ int left,right; }
typedef struct stack STACK;
STACK s[1000],e;
int top,i,j,y;
NODE temp;
top=0;
s[top].left=0;
s[top].right=n-1;
while(top>=0)
{ e.left= s[top].left;
e.right= s[top].right;
top--;
while(e.left< e.right)
{ i= e.left;
j= e.right;
temp=r[i];
while(i<j)
{ while(i<j && r[j].key>=temp.key)
j--;
if(i<j )
{ r[i]=r[j];
i++;
}
while(i<j && r[i].key<=temp.key)
i++;
if(i<j )
{ r[j ]=r[i];
j--;
}
}
r[i]=temp;
top++;
if((i-e.left)>(e.right-i))
{ y= e.right; e.right=i-1; s[top]=e;
e.left=i+1; e.right=y; }
else
{ y= e.left; e.left=i+1; s[top]=e;
e.right=i-1; e.leftt=y; }
}
}
}
一般来说,快速排序有非常好的时间复杂度,对 n个
记录进行快速排序的平均时间复杂度为 ).lo g( 2 nnO
但当一组待排序的记录已按关键字值有序或基本有序时
(非递减有序或非递增有序 ),情况反而恶化,原因是在第
一趟快速排序中,经过 n –1次比较后,将第一个记录仍定
位在它原来的位置上,并得到一个有 n –1个记录的子区间
第二趟快速排序时,经过 n –2次比较,将第二个记录仍定
位在它原来的位置上,并得到一个有 n –2个记录的子区间
依此类推,总比较次数为,
使快速排序蜕变为冒泡排序,其时间复杂度为
2/2/)1(1)2()1( 2nnnnn ???????? ?
).( 2nO
快速排序是不稳定的,请同学自行验证反例 5 5 3.
8.3 选择排序
8.3.1 直接选择排序
直接选择排序的具体做法是, 通过比较,首先在所有
记录中选出关键字值最小的记录,把它与第一个记录交换
位置,然后在其余的记录中在选出关键字值次小的记录,
与第二个记录交换位置,依此类推,直至所有的记录成为
有序序列,
下面举例介绍直接选择排序的具体做法,
设一组无序记录的初态如下所示,
初始状态,
第一躺结果,
47 33 61 82 72 11 25 47 57 02
[02] 33 61 82 72 11 25 47 57 47
第二躺结果,[02 11] 61 82 72 33 25 47 57 47
第三躺结果,[02 11 25] 82 72 33 61 47 57 47
第四躺结果, [02 11 25 33] 72 82 61 47 57 47
第五躺结果, [02 11 25 33 47] 82 61 72 57 47
第六躺结果,[02 11 25 33 47 47] 61 72 57 82
第七躺结果,[02 11 25 33 47 47 57] 72 61 82
第八躺结果,[02 11 25 33 47 47 57 61] 72 82
第九躺结果,[02 11 25 33 47 47 57 61 72] 82
最后排序结果, 02 11 25 33 47 47 57 61 72 82
由排序过程可见,
其比较次数与记录
的初始排列无关,
第一趟找出最小关
键字值的记录需进
行 n –1次比较,第
二趟找出次小关键
字值的记录需进行
n –1次比较,因此
总的比较次数为,
2
2
)1(
)(
2
1
n
nn
in
n
ii
?
?
???
?
?
由于每趟选择后要
执行两个记录的交
换,而每次交换要
进行三次记录的移动,因此对 n个记录 进行 直接选择排序
时,记录移动次数的最大值为 3(n –1),最小值为 0,直接选
择排序的平均时间复杂度为 ).( 2nO
直接选择排序是不稳定的,
下面先给出以顺序存储结构存储待排序记录的 C函数,
struct node
{ int key,data;}
typedef struct node NODE;
void direct_selection_sort(r,n)
NODE r[ ]; int n;
{ NODE temp; int i,j,m;
for(i=1; i<n; i++)
{ j=i;
for(m=i+1; m<=n; m++)
if(r[j].key>r[m].key)
j=m;
if(j!=i)
{ temp=r[i];
r[i]=r[j];
r[j]=temp;
}
}
}
下面再补充以带头结点的单链表存储待排序记录的 C
函数,
struct node
{ int key; struct node *next;}
typedef struct node NODE;
void direct_selection_ link_sort(h)
NODE *h;
{ NODE *r,*p,*q;
int temp;
r=h->next;
while(r->next!=null)
{ q=r;
p=r->next;
while(p!=null)
{ if(p->key<q->key)
q=p;
p=p->next;
}
if(q!=r)
{ temp=q->key;
q->key=r->key;
r->key=temp;
}
r=r->next;
}
8.3 归并排序
归并排序的基本思想,是将两个或两个以上的有序子
序列合并成一个新的有序序列,在此只介绍两路归并排序
两路归并是把一个有 n个记录的无序序列看成是由 n个
长度为 1的有序子序列组成,然后进行两两归并,得到
个长度为 2或 1的有序子序列,再两两归并,…,如此
重复,直至最后形成包含 n个记录的一组有序记录为止,
下面仍举例说明两路归并排序的过程,
设一组无序记录的初态如下所示,
? ?2/n
初始状态,
[47] [33] [61] [82] [72] [11] [25] [47] [57] [02]n =10个子序列,
47 33 61 82 72 11 25 47 57 02
第一趟归并后, [33 47] [61 82] [11 72] [ 25 47] [02 57]
第二趟归并后, [33 47 61 82] [11 25 47 72] [02 57]
第三趟归并后, [11 25 33 47 47 61 72 82] [02 57]
第四趟归并后, [02 11 25 33 47 47 57 61 72 82]
两路归并的平均时间复杂度为 ).lo g(
2 nnO
两路归并排序是稳定的,
最后将各种排序方法的效率及稳定性列成下表,
课外习题,教材 P.227第 4题,(题中 (3)堆排序 和 (5)基数排序
不做 ! 增加直接插入排序,
冒泡排序,
直接选择排序 )
)( 2nO )(nO )( 2nO
)( 3.1nO
)( 2nO )(nO )( 2nO
)log( 2 nnO )( 2nO
)( 2nO
)log( 2 nnO
排序类别 排序方法 时间复杂度 稳定性
平均情况 最好情况 最坏情况
插入 直接插入 稳定
希尔排序 不稳定
交换 冒泡排序 稳定
快速排序 不稳定
选择 直接选择 不稳定
归并 两路归并 稳定
基本概念
排序是计算机程序设计中的一种重要运算,其功能是将一
个数据元素 (或记录 )的任意序列,重新排列成一个按关键字有
序的序列,
排序的确切定义为, 设含有 n个记录的序列为 ? ?nRRR,,,21 ?
其相应的关键字序列为 ? ?
nKKK,,,21 ?,需确定一种排列
,,,2,1 pnpp ? 使其相应的关键字满足如下的非递减关系
? ?pnpp KKK ??? ?21,或非递增关系 ? ?pnpp KKK ??? ?21
即使原来的序列 ? ?
nRRR,,,21 ?
成为一个按关键字有序的序列
? ?pnpp RRR,,,21 ?,这样的一种操作称为排序,
定义中的关键字
iK
可以是记录 ),,2,1( niR
i ??
主关键字
此时任何一个记录的无序序列经排序后得到的结果是唯一的,
当 是记录
iK iR
的次关键字时,则排序的结果不唯一,因待
排序的记录序列中可能存在两个或两个以上关键字相等的
记录, 关键字
iK
可以是记录中的单个数据项,也可是若干
数据项的组合,
假设 ),1,1( jinjniKK
ji ??????
,且在排列前的
序列中
iR
领先于
jR
(即 ji? ),若在排序后的序列中
iR
仍领
领先于
jR
,则称所用的排序方法是稳定的 ;反之,若可能使
排序后的序列中
jR
领先于
iR,则称所用的排序方法是不稳
定的,
由于待排序的记录数量不同,使排序过程中涉及的存
储器不同,由此排序方法分为两大类,
1,内部排序, 待排序记录存放在计算机随机存储器中进行
的排序过程,
2,外部排序, 当待排序记录数量很大,以至内存一次无法
容纳全部记录,排序过程中需对外存进行访问的排序过程,
本章只讨论内排序, 在排序过程中需进行两种操作,
(1)比较两个关键字的大小,这对大多数排序方法都是必
要的,
(2)将记录从一个位置移动到另一个位置,并非必需,可
通过改变记录的存储方式予以避免,
待排序的记录序列可有三种存储方式,
(1)以一维数组作为存储结构,排序过程是对记录本身进
行物理重排,即通过比较和判定,把记录移到合适的
位置,
(2)以链表 (动态链表或静态链表 )作为存储结构,排序过程
中无需移动记录,仅需修改指针即可,
(3)有的排序方法难于在链表上实现,若仍需 避免 排序过程
中记录的移动,可建立一辅助表 (如包括关键字和指向
记录的指针组成的索引表 ),从而,排序过程中只需对
辅助表的表目进行物理重排,只移动辅助表的表目,而
不移动记录本身,
8.1 插入排序
8.1.1直接插入排序
这是一种最简单的排序方法,具体做法是在插入第 i
个记录时,? ?
121,,,?iRRR ?
已排好序,这时将关键字
iK
依
次与关键字 ? ?
121,,,KKK ii ??? 进行比较,从而找到应插入
的位置,然后将
iK
对应的记录
iR 插入,原位置的记录向后
顺推, 下面举例说明其手工操作的过程,
要求将下面一组以其关键字值表示的初始排列无序的
记录,用 直接插入法排序成非递减有序序列,
在手工操作的过程中,i的值 表示第几趟插入,[ ]中的
序列表示已排好序的记录序列,
序列的初始状态为,
下面给出直
接插入排序
的 C函数,其
功能是对以
一维数组存
储的一组无
序记录排列
成非递减有
序序列,
? ? 4725117282613347
? ? 47251172826147331?i
? ? 47251172826147332?i
? ? 47251172826147333?i
? ? 47251182726147334?i
? ? 47258272614733115?i
? ? 47827261473325116?i
]8272614747332511[7?i
struct node
{ int key; int data; };
typedef struct node NODE;
void insertsort(r,n)
NODE r[ ]; int n; /* r[ ]为具有 n+1个单元的数组,n为记录个数 */
{ int i,j;
for(i=2;i<=n;i++)
{ r[0]=r[i]; /* 将待排序记录赋予下监视哨 */
j=i-1;
while(r[0].key<r[j].key) /*待排序记录的关键字值与有序子序列 */
/*的各记录的关键字值进行比较 /*
r[j+1]=r[j--]; /*若条件真,则 r[j]记录后移 */
r[j+1]=r[0]; /*若条件假,则待排序记录插入到相应位置 */
}
}
算法简洁 ﹑ 容易实现是直接插入排序的两大特点,
下面 分析其时间效率,
整个排序过程中只有比较关键字和移动记录两种运
算, 当原始记录已按关键字非递减有序,即为正序时,
时间效率最高,因完成每趟排序仅需进行一次比较及两
次移动记录操作 (即开始时将记录移至监视哨中和最后将
记录移入适当位置 ),整个排序过程总的比较次数为 n-1,
记录总的移动次数为 2(n-1),故其时间复杂度为 O(n);
反之,如果原始记录是按关键字非增减有序的,即为
逆序时,时间效率最低,因要插入的第 i个记录,均要与
前 i –1个记录及监视哨的关键字进行比较,即每趟要进行
i次比较,总的比较次数为,
2/)1)(2(
2
????
?
nnin
i
从移动记录的次数来看,每趟排序中除了上面提到的两
次移动外,还需将有序子序列中关键字值大于待排序记
录的关键字值的记录后移一个位置,总的移动次数为,
2/)1)(4()1(
2
?????
?
nnin
i故其时间复杂度为
).( 2nO
若在随机情况下,设待排序记录序列可能出现的各
种排列的概率相同,则可取上述两种极端情况的平均值
作为比较和移动记录的平均次数,约为 4/2n, 由此,直
接插入排序的时间复杂度为 ).( 2nO
直接插入排序是稳定的排序方法,
对于直接插入排序,补充一 C函数,其功能为, 将
以带头结点的单链表存储的一组无序记录,排序成非递
减序列,
struct node
{ int key; struct node *next; };
typedef struct node NODE;
void insertsort(h)
NODE *h;
{ NODE *p,*r,*l,*q;
int exchang;
l= h->next; /*l指向有序子表的表尾 */
q=l->next; /*q指向待排序的结点 */
while(q!=null)
{ p=h->next; /* p指向有序子表的表头,排序过程中可向表尾移动 */
r=h; /* r指向 p的直接前趋结点 */
exchang=0;/*标识结点未交换 */
while(p!=q && exchang==0)
{ if(p->key<=q->key)
{ r=p; p=r->next; } /*结点后移 */
else
{ l->next=q->next;
q->next=p;
r->next=q; /*待排序的结点前插 */
exchang=1; /*标识结点有交换 */
}
}
if(p==q) l=q;/*一趟排序未交换,q指向的待排序结点成为有 */
/*序子表的表尾结点 */
q=l->next; /*q指向下一趟排序的待排序结点 */
}
}
8.1.1希尔排序
希尔排序是对直接插入排序法的一种改进,提高了
排序的效率, 希尔排序的作法是, 先取定一个小于待排
序记录个数 n的整数 1d 作为第一个增量,将 待排序的所有
记录分成 个组,将所有距离为
1d 1d
倍数的记录放在同一
个组中,在各组内进行直接插入排序 ; 然后取第二个增
量
12 dd ?
重复上述分组和排序工作,依此类推,直至所
取的增量 )(1
121 ddddd iii ???? ? ?,即所有记录放在
同一组中进行直接插入排序为止, 因此,希尔排序又叫
“缩小增量排序”,
对增量有多种取法,希尔给出的取法为,
? ? ? ?2/,2/ 11 ii ddnd ?? ?
上式中,n为待排序记录的个数,? ?ni 2lo g,,2,1 ??
下面通过一个具体例子来看 希尔排序的过程,
设有一组初始关键字如下所示,
47 33 61 82 72 11 25 47 57 02
n =10,? ? 52/
1 ?? nd
排序过程如下,
47 33 61 82 72 11 25 47 57 0251 ?d
47 11
33 25
61 47
82 57
72 02
对上面分成的五组记录,分别在各组内进行直接插入排序,
第一趟排序结果, 11 4725 3347 6157 8202 72
对第一趟排序结果进行第二次分组,取增量
? ? ? ? 22/52/12 ??? dd
11 25 47 57 02 47 33 61 82 72
11对上面分成的二组记录,分别在各组内进行直接插入
排序,
22 ?d
11 47 02 33 82
25 57 47 61 72
第二趟排序结果, 02 11 33 47 8225 47 57 61 72
对第二趟排序结果进行第三次分组,取增量
? ? ? ? 12/22/23 ??? dd
第三趟排序结果, 02 11 25 33 47 47 55 61 72 82
由上例结果,似乎 希尔排序是稳定的,其实不然,它是不
稳定的, 对于一种排序方法,只要举出一个例子是不稳定
的,则这种排序方法就是不稳定的, 例如,对于下例,
5 3 4 5 1
增量分别取 2,1,希尔排序结果为 1 3 4 5 5,不 稳定,
所以,希尔排序是不稳定的,
希尔排序的时间复杂度约为
8.2 交换排序
交换排序的基本思想是, 两两比较待排序记录的关
键字,发现两个记录的次序相反时即进行交换,直至没
有反序的记录为止,
8.2.1冒泡排序
冒泡排序也是一种简单的排序方法,其基本操作是,
通过对相邻关键字的比较和交换,使全部记录排列有序,
冒泡排序的过程, 为形象地表示关键字值最小的记
录象汽泡一样往上冒 (或关键字值最大的记录象石块一样
往下沉 ),将一组按关键字值无序的记录纵向排列,然后
自下而上地对每两个相邻的关键字进行比较,若为逆序
)( 3.1nO
)2,,1,(1 ????? nnjKK jj,则将两个记录交换位置,这样
的操作反复进行,直至全部记录都比较 ﹑ 交换完毕为止
经过第一趟冒泡排序之后,就将关键字值最小的记录
安排在第一个记录的位置上,显然,对于有 n个记录的
一组序列,第一趟排序需比较 n-1次,而交换记录位置的
次数与待排序记录的初始排列状态有关 ; 然后,对后 n-1
个记录重复进行同样的操作,则将具有次小关键字值的
记录安排在第二个记录的位置上, 重复以上过程,直至
在某趟排序中没有记录需要交换为止, 举例,
初
始
47
33
61
82
72
11
25
47
47
33
61
82
11
72
25
47
47
33
61
11
82
72
25
47
47
33
11
61
82
72
25
47
47
11
33
61
82
72
25
47
一
趟
11
47
33
61
82
72
25
47
二
趟
11
25
47
33
61
82
72
47
三
趟
11
25
33
47
47
61
82
72
四
趟
11
25
33
47
47
61
72
82
五
趟
11
25
33
47
47
61
72
82
分析冒泡排
序的过程可
见,若初始
记录的顺序
是按关键字
非递减有序
的,则只需
进行一趟排
序,比较次数为 n-1次,记录的移动次数为 0,即比较次
数和移动次数均为最小值 ; 若初始记录按关键字为逆序
即非递增有序时,则需进行 n-1趟排序,总比较次数为
22
)1()( 21
1
nnninn
i
??????
?
,总移动次数为,
22
)1)(4()1( 2
2
nnnin
i
??????
?
,也即比较和移动次数次
数均为最大值,因此,冒泡排序的时间复杂度为 )( 2nO
冒泡排序也是一种稳定的排序方法,
下面先补充以顺序存储结构即一维数组存储待排序
记录的 C函数,
struct node
{ int key,data;}
typedef struct node NODE;
void bubblesort(r,n)
NODE r[ ]; int n;
{ NODE temp; int i,top,boolean;
top=0;
do
{ boolean=0;
for(i=n-1; i>top; i--)
if(r[i].key<r[i-1].key)
{ temp= r[i]; r[i]=r[i-1];
r[i-1]= temp; boolean=1;}
top++;
}
while(boolean==1); }
再补充以带头结点的单链表存储待排序记录的 C函数,
struct node
{ int key,data; struct node *next;}
typedef struct node NODE;
void bubbllinkesort(h)
NODE *h;
{ NODE *f,*p,*q,*r ; int boolean=0;
f=h; p=head->next; q=p->next; r=null;
while(boolean==0)
{ boolean=1;
while(q!=r)
{ if(p->key>q->key)
{ f->next=q; p->next=q->next; q->next=p; f=q; boolean=0;}
else
{ f=p; p=q; }
q=p->next;
}
r=p; f=head; p=f->next; q=p->next;
}
}
8.2.2 快速排序
快速排序也是一种籍助交换进行排序的方法,由冒
泡排序改进而得,是目前内部排序中速度较快的方法,
快速排序又称为分区交换排序,其基本思想是, 设
待排序的一组记录中含有 n个记录,任取其中一个记录 (通
常选取第一个记录 )的关键字作为控制关键字 (相应的记录
称为控制记录 ),以控制记录为分界点,经一趟排序后,
将全部记录分为两部分, 所有关键字值比控制关键字值
小的记录都安置在控制记录之前,所有关键字值比控制
关键字值大的记录都安置在控制记录之后,然后再分别
对这两部分无序子区间中的记录重复上述过程,直至每
一部分子区间中只剩下一个记录为止,
下面举例介绍快速排序的具体做法,
设两个整数类型指针 i和 j,其初态分别指向一组待排
序记录的第一个记录和最后一个记录,如下所示,
47 33 61 82 72 11 25 47 57 02初始状态
i j
选第一个记录为控制记录,并将其送入暂存变量 x中,用
空的方框代替控制记录, 一趟排序的过程如下,
初始状态 33 61 82 72 11 25 47 57 02
i j
令 j自 n起向左扫描,因 02<47,将
02放入 i所指位置,j不变,i = i +1,
[02] 33 61 82 72 11 25 47 57
i j
令 i自当前位置起向右扫描,33<47
i = i +1.
i
61>47,61放入 j 所指位置
i不变,j = j -1.
[02 33] 82 72 11 25 47 57 [61]
i j
[02 33 25] 82 72 11 [47 57 61]
i j
令 j自当前位置起向左扫描,直至 j
所指记录的关键字值比控制关键
j
字值小为止,25放入 i所指位置,i = i +1.
令 i自当前位置起向右扫描,82>47
82放入 j 所指位置,i不变,j = j -1.
令 j自当前位置起向左扫描,直至 j
所指记录的关键字值比控制关键
字值小为止,11<47,11放入 i所指
位置,i = i +1,j不变,
[02 33 25] 72 11 [82 47 57 61]
i j
[02 33 25 11] 72 [82 47 57 61]
i j
令 i自当前位置起向右扫描,72>47
72放入 j 所指位置,i不变,j = j -1.
[02 33 25 11] [ 72 82 47 57 61]
i j
当一趟排序过程中的某次扫描结束后,出现 i = j则表明此趟排序
结束,将暂存在变量 x中的控制记录放入 i或 j所指的位置上,
47
一趟排序结束后,以控制记录所在位置为分界点,将一组记录分
左右两个用方括弧括起的无序子区间,如下所示,
[02 33 25 11] 47 [ 72 82 47 57 61]一趟排序之后,
然后对上面结果的左右无序子区间再分别反复进行快
速排序,直至每一部分子区间中只剩下一个记录为止,
将各趟排序后的结果演示于下,
一趟排序之后,
二趟排序之后,
[02 33 25 11] 47 [ 72 82 47 57 61]
02 [33 25 11] 47 [61 57 47] 72 [ 82]
三趟排序之后,02 [11 25] 33 47 [47 57] 61 72 82
四趟排序之后, 02 11 25 33 47 47 57 61 72 82
快速排序的 C函数如下,
struct node
{ int key,data; }
typedef struct node NODE;
void quicksort(r,n)
NODE r[ ]; int n;
{struct stack
{ int left,right; }
typedef struct stack STACK;
STACK s[1000],e;
int top,i,j,y;
NODE temp;
top=0;
s[top].left=0;
s[top].right=n-1;
while(top>=0)
{ e.left= s[top].left;
e.right= s[top].right;
top--;
while(e.left< e.right)
{ i= e.left;
j= e.right;
temp=r[i];
while(i<j)
{ while(i<j && r[j].key>=temp.key)
j--;
if(i<j )
{ r[i]=r[j];
i++;
}
while(i<j && r[i].key<=temp.key)
i++;
if(i<j )
{ r[j ]=r[i];
j--;
}
}
r[i]=temp;
top++;
if((i-e.left)>(e.right-i))
{ y= e.right; e.right=i-1; s[top]=e;
e.left=i+1; e.right=y; }
else
{ y= e.left; e.left=i+1; s[top]=e;
e.right=i-1; e.leftt=y; }
}
}
}
一般来说,快速排序有非常好的时间复杂度,对 n个
记录进行快速排序的平均时间复杂度为 ).lo g( 2 nnO
但当一组待排序的记录已按关键字值有序或基本有序时
(非递减有序或非递增有序 ),情况反而恶化,原因是在第
一趟快速排序中,经过 n –1次比较后,将第一个记录仍定
位在它原来的位置上,并得到一个有 n –1个记录的子区间
第二趟快速排序时,经过 n –2次比较,将第二个记录仍定
位在它原来的位置上,并得到一个有 n –2个记录的子区间
依此类推,总比较次数为,
使快速排序蜕变为冒泡排序,其时间复杂度为
2/2/)1(1)2()1( 2nnnnn ???????? ?
).( 2nO
快速排序是不稳定的,请同学自行验证反例 5 5 3.
8.3 选择排序
8.3.1 直接选择排序
直接选择排序的具体做法是, 通过比较,首先在所有
记录中选出关键字值最小的记录,把它与第一个记录交换
位置,然后在其余的记录中在选出关键字值次小的记录,
与第二个记录交换位置,依此类推,直至所有的记录成为
有序序列,
下面举例介绍直接选择排序的具体做法,
设一组无序记录的初态如下所示,
初始状态,
第一躺结果,
47 33 61 82 72 11 25 47 57 02
[02] 33 61 82 72 11 25 47 57 47
第二躺结果,[02 11] 61 82 72 33 25 47 57 47
第三躺结果,[02 11 25] 82 72 33 61 47 57 47
第四躺结果, [02 11 25 33] 72 82 61 47 57 47
第五躺结果, [02 11 25 33 47] 82 61 72 57 47
第六躺结果,[02 11 25 33 47 47] 61 72 57 82
第七躺结果,[02 11 25 33 47 47 57] 72 61 82
第八躺结果,[02 11 25 33 47 47 57 61] 72 82
第九躺结果,[02 11 25 33 47 47 57 61 72] 82
最后排序结果, 02 11 25 33 47 47 57 61 72 82
由排序过程可见,
其比较次数与记录
的初始排列无关,
第一趟找出最小关
键字值的记录需进
行 n –1次比较,第
二趟找出次小关键
字值的记录需进行
n –1次比较,因此
总的比较次数为,
2
2
)1(
)(
2
1
n
nn
in
n
ii
?
?
???
?
?
由于每趟选择后要
执行两个记录的交
换,而每次交换要
进行三次记录的移动,因此对 n个记录 进行 直接选择排序
时,记录移动次数的最大值为 3(n –1),最小值为 0,直接选
择排序的平均时间复杂度为 ).( 2nO
直接选择排序是不稳定的,
下面先给出以顺序存储结构存储待排序记录的 C函数,
struct node
{ int key,data;}
typedef struct node NODE;
void direct_selection_sort(r,n)
NODE r[ ]; int n;
{ NODE temp; int i,j,m;
for(i=1; i<n; i++)
{ j=i;
for(m=i+1; m<=n; m++)
if(r[j].key>r[m].key)
j=m;
if(j!=i)
{ temp=r[i];
r[i]=r[j];
r[j]=temp;
}
}
}
下面再补充以带头结点的单链表存储待排序记录的 C
函数,
struct node
{ int key; struct node *next;}
typedef struct node NODE;
void direct_selection_ link_sort(h)
NODE *h;
{ NODE *r,*p,*q;
int temp;
r=h->next;
while(r->next!=null)
{ q=r;
p=r->next;
while(p!=null)
{ if(p->key<q->key)
q=p;
p=p->next;
}
if(q!=r)
{ temp=q->key;
q->key=r->key;
r->key=temp;
}
r=r->next;
}
8.3 归并排序
归并排序的基本思想,是将两个或两个以上的有序子
序列合并成一个新的有序序列,在此只介绍两路归并排序
两路归并是把一个有 n个记录的无序序列看成是由 n个
长度为 1的有序子序列组成,然后进行两两归并,得到
个长度为 2或 1的有序子序列,再两两归并,…,如此
重复,直至最后形成包含 n个记录的一组有序记录为止,
下面仍举例说明两路归并排序的过程,
设一组无序记录的初态如下所示,
? ?2/n
初始状态,
[47] [33] [61] [82] [72] [11] [25] [47] [57] [02]n =10个子序列,
47 33 61 82 72 11 25 47 57 02
第一趟归并后, [33 47] [61 82] [11 72] [ 25 47] [02 57]
第二趟归并后, [33 47 61 82] [11 25 47 72] [02 57]
第三趟归并后, [11 25 33 47 47 61 72 82] [02 57]
第四趟归并后, [02 11 25 33 47 47 57 61 72 82]
两路归并的平均时间复杂度为 ).lo g(
2 nnO
两路归并排序是稳定的,
最后将各种排序方法的效率及稳定性列成下表,
课外习题,教材 P.227第 4题,(题中 (3)堆排序 和 (5)基数排序
不做 ! 增加直接插入排序,
冒泡排序,
直接选择排序 )
)( 2nO )(nO )( 2nO
)( 3.1nO
)( 2nO )(nO )( 2nO
)log( 2 nnO )( 2nO
)( 2nO
)log( 2 nnO
排序类别 排序方法 时间复杂度 稳定性
平均情况 最好情况 最坏情况
插入 直接插入 稳定
希尔排序 不稳定
交换 冒泡排序 稳定
快速排序 不稳定
选择 直接选择 不稳定
归并 两路归并 稳定
