?概述
插入排序
快速排序
选择排序
归并排序
基数排序
各种内排方法比较第十章内部排序概 述
排序,将一个数据元素的任意序列,重新排列成一个按关键字有序的序列 。
数据表 (datalist),它是待排序数据对象的有限集合 。
主关键字 (key),数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据,称为关键字 。 也称为 排序码 。
排序方法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],
且在排序之前,对象 r[i]排在 r[j]前面。如果在排序之后,对象 r[i]仍在对象 r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的 。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
内排序分类
依不同原则插入排序,交换排序,选择排序,归并排序,和计数排序等 。
依所须工作量简单排序 ---时间复杂度 o(n2)
先进排序方法 ---时间复杂度 o(n logn)
基数排序 ---时间复杂度 o(d.n)
插入排序 (Insert Sorting)
基本思想 当插入第 i (i? 1) 个对象时,前面的
V[0],V[1],…,V[i -1]已经排好序。这时,用
V[i]的排序码与 V[i-1],V[i-2],… 的排序码顺序进行比较,找到插入位臵即将 V[i]插入,原来位臵上的对象向后顺移。
基本思想 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位臵上,直到对象全部插入为止。
直接插入排序 (Insert Sort)
直接插入 排序过程
0 1 2 3 4 5 temp i = 1
i = 2
0 1 2 3 4 5 temp
21 0825 49 25* 16
21 25 0849 25* 16 25
21 25 0849 25* 16
21 25 0849 25* 16 49
21 25 0849 25* 16
i = 3 21 25 0849 25* 16 25*
21 25 084925* 16
i = 4
i = 5
21 25 084925* 16 16
21 25 084925*16
21 25 084925*16
21 2508 4925*16
08
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
算法分析
设待排序对象个数为 n,则该算法的主程序执行
n-1趟。
排序码比较次数和对象移动次数与对象排序码的初始排列有关。
最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较 1次,移动 2次对象,总的排序 码比较次数为 n-1,对象移动次数为 2(n-1)。
最坏情况下,第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较,并且每做 1次比较就要做 1次数据移动 。 则总排序码比较次数 KCN和对象移动次数 RMN分别为
在平均情况下的排序码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。
直接插入排序是一种稳定的排序方法。
1
1
1
1
22142
221
n
i
n
i
nnniR M N
nnniKCN
//))(()(
,//)(
2
2
折半插入排序 (Binary Insertsort)
基本思想 设在顺序表中有一 个对象序列 V[0],
V[1],…,V[n -1]。其中,V[0],V[1],…,V[i -1]
是已经排好序的对象。在插入 V[i] 时,利用折半搜索法寻找 V[i] 的插入位臵。
折半插入排序的算法
typedef int SortData;
void BinInsSort ( SortData V[ ],int n ) {
SortData temp; int Left,Right;
for ( int i = 1; i < n; i++) {
Left = 0; Right = i-1; temp = V[i];
while ( Left <= Right ) {
int mid = ( Left + Right )/2;
if ( temp < V[mid] ) Right = mid - 1;
else Left = mid + 1;
}
for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k];//
记录后移
V[Left] = temp; //插入
}
}
折半插入排序
0 1 2 3 4 5 temp
i = 1
i = 2
0 1 2 3 4 5 temp
5
21 33
i = 3
5
5
2153
21
4 4
i = 4 2153 8 8
i = 5 2153 16 168
4
4
213 84 5 16
折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。
它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第 i 个对象时,需要经过?log2i?+1 次排序码比较,才能确定它应插入的位臵。因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半插入排序所进行的排序码比较次数为：
1
1
22 lo g1lo g
n
i
nni
算法分析
当 n 较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差 。
在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少 。 折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列 。
折半插入排序是一个稳定的排序方法。
折半插入排序的时间复杂度为 o(n2)。
希尔排序 (Shell Sort)
基本思想 设待排序对象序列有 n 个对象,首先取一个整数 gap < n 作为间隔,将全部对象分为 gap 个子序列,所有距离为 gap 的对象放在同一个子序列中,在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap,
例如取 gap =?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1,将所有对象放在同一个序列中排序为止。
希尔排序方法又称为缩小增量排序。
i = 3
Gap = 3
0 1 2 3 4 5
21 0825 49 25* 16
0 1 2 3 4 5
21 08 25 4925*16
i = 2
Gap = 2 21 08 25 4925*16
2108 25 4925*16
i = 1
Gap = 1
2108 25 4925*16
2108 25 4925*16
希尔排序过程
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
希尔排序的算法
开始时 gap 的值较大,子序列中的对象较少,排序速度较快 ; 随着排序进展,gap 值逐渐变小,子序列中对象个数逐渐变多,由于前面大多数对象已基本有序,所以排序速度仍然很快。
Gap的取法有多种。 shell 提出取 gap =?n/2?,gap =
gap/2?，直到 gap = 1。
对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。
希尔排序所需的比较次数和移动次数约为 n 1.3
当 n趋于无穷时可减少到 n(log2 n)2
快速排序 ( Exchange Sort )
基本方法 设待排序对象序列中的对象个数为 n。
一般地,第 i趟起泡排序从 1到 n-i+1依次比较相邻两个记录地关键字,如果发生逆序，则交换之，
其结果是这 n-i+1个记录中，关键字最大的记录被交换到第 n-i+1的位臵上,最多作 n-1趟。
基本思想 是两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之,直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21
08
25
49
25
16
21
49
25
25
16
08
21
49
25
25
16
08
21
49
25
25
16
08 21
49
25
25
16
08
21
49
25
25
16
08
起泡排序的过程起泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1;
int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志臵为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
Swap ( V[j-1],V[j] ); //交换
exchange = 1; //标志臵为 1,有交换
}
i++;
}
}
思考题：如何实现双起泡
第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-
1]进行排序,结果将该序列中排序码最小的对象交换到序列的第一个位臵 (i-1),其它对象也都向排序的最终位臵移动 。。
最多做 n-1趟起泡就能把所有对象排好序 。
在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做 n-1次排序码比较,不移动对象 。 这是最好的情形 。
最坏的情形是算法执行 n-1趟起泡,第 i趟 (1?
i? n) 做 n- i 次排序码比较,执行 n-i 次对象交换 。 这样在最坏情形下总的排序码比较次数 KCN和对象移动次数 RMN为：
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninK C N
)()(
)()(
起泡排序是一个稳定的排序方法。
快速排序 (Quick Sort)
基本思想 是任取待排序对象序列中的某个对象 (例如取第一个对象 ) 作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：
左侧子序列中所有对象的排序码都小于或等于基准对象的排序码
右侧子序列中所有对象的排序码都大于基准对象的排序码
基准对象则排在这两个子序列中间 (这也是该对象最终应安放的位臵 )。
然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位臵上为止。
基准对象也称为 枢轴（或支点）记录。
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
快速排序算法描述快速排序的过程
21 0825 49 25* 16初始关键字
08 25 49 25* 1621
08 2549 25* 16
08 2549 25*16
08 254925*16
08 254925*16 21
prikey
一次交换二次交换三次交换四次交换完成一趟排序
i j
i
j
j
i
i j
j
i j
i
08 254925*16 21完成一趟排序分别进行快速排序 08 25 4925*16 21
有序序列 08 25 4925*16 21
快速排序的算法
void QuickSort ( SqList &L,int low,int high ){
//在序列 low?high 中递归地进行快速排序
if ( low < high) {
int pivotloc= Partition (L,low,high); //划分
QuickSort ( L,low,pivotloc-1); //对左序列同样处理
QuickSort ( 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;
}
算法 quicksort是一个递归的算法,其递归树如图所示。
算法 partition利用序列第一个对象作为基准，
将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准对象排序码的对象都移到序列左侧,最后基准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
算法分析
快速排序的趟数取决于递归树的高度。
如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
在 n个元素的序列中,对一个对象定位所需时间为 O(n)。若设 t (n) 是对 n 个元素的序列进行排序所需的时间,而且每次对一个对象正确定位后,正好把序列划分为长度相等的两个子序列,此时,总的计算时间为：
T(n)? cn + 2T(n/2 ) // c 是一个常数
cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)
2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8)
………
cn log2n + nT(1) = O(n log2n )
可以证明,函数 quicksort的平均计算时间也是 O(nlog2n)。 实验结果表明,就平均计算时间而言,快速排序是所有内排序方法中最好的一个 。
快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数 。
最大递归调用层次数与递归树的高度一致,
理想情况为?log2(n+1)? 。 因此,要求存储开销为 O(log2n)。
在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 总的排序码比较次数将达
快速排序是一种不稳定的排序方法 。
212
1 21
1
nnninn
i
)()(
基本思想 每一趟 (例如第 i 趟,
i = 0,1,…,n -2) 在后面 n-i 个待排序记录中选出排序码最小的记录,作为有序序列中的第 i 个记录。待到第
n-2 趟作完,待排序记录只剩下 1个,
就不用再选了。
选择排序
直接选择排序是一种简单的排序方法,它的基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最小排序码的对象；
② 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码的对象 。 在剩下的对象 V[i+1]～ V[n-1]中重复执行第 ①,② 步,直到剩余对象只有一个为止 。
直接选择排序 (Select Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2 08 16 25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
直接选择排序的过程最小者 25*
无交换49
25*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3 08 16 2521
最小者 25
无交换252116
08
各趟排序后的结果直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位臵
Swap ( V[i],V[k] );
}
}
直接选择排序的排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象,
则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为
2
0 2
11n
i
nninKCN )()(
对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数 RMN = 0，达到最少。
最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。
直接选择排序是一种不稳定的排序方法。
堆排序 ( Heap sort )
堆 ( Heap )设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 0开始连续编号。若满足
Ki? K2i+1 && Ki? K2i+2
或 Ki? K2i+1 && Ki? K2i+2,
则称该关键字集合构成一个堆。
前者成为最小堆，后者称为最大堆。
完全二叉树顺序表示
Ki? K2i+1 &
Ki? K2i+2
完全二叉树顺序表示
Ki? K2i+1 &&
Ki? K2i+2
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
堆排序 (Heap Sort)
利用堆及其运算,可以很容易地实现选择排序的思路。
堆排序分为两个步骤
根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
通过一系列的对象交换和重新调整堆进行排序。
自下向上逐步调整为小顶堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
i = 4 i = 3
i
初始小顶堆的建立过程
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
i = 2
i
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
i = 1
i
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i53
建成堆
void Crt_MinHeap ( MinHeap *H,
HeapData arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆
for ( int i = 0; i < n; i++ ) H->data[i] = arr[i];
H->CSize = n; //数组传送及当前堆大小
int CPos = (H->CSize-2)/2; //最后分支结点
while ( CPos >= 0 ) { //从下到上逐步扩大堆
FilterDown ( &H,CPos,H->CSize-1 );
CPos--;
}
}
堆的建立
void FilterDown ( MinHeap *H,int start,
int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
HeapData temp = H->data[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap && //两子女中选小者
H->data[j] > H->data[j+1] ) j++;
if ( temp <= H->data[j] ) break;
else { H->data[i] = H->data[j];
i = j; j = 2*j+1; } //向下滑动
}
H->data[i] = temp;
}
最小堆的向下调整算法初始大顶堆的建立过程
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
初始排序码集合 i = 2 时的局部调整
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
i = 0 时的局部调整形成最大堆
i = 1 时的局部调整最大堆的向下调整算法
void FilterDown ( MaxHeap *H,
int start,int EndOfHeap ) {
int i = start; int j = 2*i+1;
HeadData temp = H->data[i];
while ( j <= EndOfHeap ) { //最后位臵
if ( j < EndOfHeap &&
H->data[j] < H->data[j+1] )
j = j+1; //选两子女的大者
if ( temp >= H->data[j] ) break;
else {
H->data[i] = H->data[j]; //大 子女上移
i = j; j = 2*j+1; //向下继续调整
}
}
H->data[i] = temp; //回放到合适位臵
}
将表转换成堆
for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 );
基于初始堆 (大顶堆 )进行堆排序
最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换到最后,再对前面的 n-1个对象,使用堆的调整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位臵。
再对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位初始最大堆基于初始堆进行堆排序
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位从 0 号到 4 号 重新调整为最大堆
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位从 0 号到 3 号 重新调整为最大堆
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位从 0 号到 2 号 重新调整为最大堆
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位从 0 号到 1 号 重新调整为最大堆堆排序的算法
void HeapSort ( MaxHeap *H ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序。
for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 ); //初始堆
for ( i = H->CSize-1; i >= 1; i--) {
Swap ( H->data[0],H->data[i] ); //交换
FilterDown ( H,0,i-1 ); //重建最大堆
}
}
若设堆中有 n 个结点,且 2k-1? n? 2k,则对应的完全二叉树有 k 层。在第 i 层上的结点数? 2i (i = 0,1,…,k -1)。 在第一个形成初始堆的 for 循环中对每一个非叶结点调用了一次堆调整算法 FilterDown( ),因此该循环所用的计算时间为：
其中,i 是层序号,2i 是第 i 层的最大结点数,
(k-i-1)是第 i 层结点能够移动的最大距离。
2
0
22
k
i
i ik 1
堆排序的算法分析
第二个 for循环中调用了 n-1次 FilterDown( )算法,该循环的计算时间为 O(nlog2n)。因此,堆排序的时间复杂性为 O(nlog2n)。
该算法的附加存储主要是在第二个 for循环中用来执行对象交换时所用的一个临时对象。
因此，该算法的空间复杂性为 O(1)。
堆排序是一个不稳定的排序方法。
n
j
n
j
jik
k
j
k
j
jj
k
k
j
jk
k
i
i
4
1
1
1
1
1
1
1
1
2
0
2
2
2
22
22122 )(
归并排序 (Merge Sort)
归并 将两个或两个以上的有序表合并成一个新的有序表。
两路归并 (2-way merging)原始序列
initList[ ]中两个有序表 initList[l] …
initList[m]和 initList[m+1] … initList[n],它们可归并成一个有序表,存于另一对象序列
mergedList的 l … n 中。
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
设变量 i 和 j 是表 initList[l … m] 和 initList [m+1…
n]的当前检测指针。 k 是存放指针。
当 i 和 j 都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的对象排放到新表 k 所指位臵 中；
当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。
i j
typedef int SortData;
void merge ( SortData InitList[ ],SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较将较小的并入
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }//将 mid前剩余的并入
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; } //将 mid后剩余的并入
}
两路归并算法一趟归并排序的情形
设 initList[0]到 initList[n-1]中 n 个对象已经分为一些长度为 len 的归并项,将这些归并项两两归并,归并成长度为 2len 的归并项,
结果放到 mergedList[ ]中。
如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
剩下一个长度为 len的归并项和另一个长度不足 len的归并项,可用 merge算法将它们归并成一个长度小于 2len 的归并项。
只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList[ ]中。
迭代的归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到?n / 2? 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为 1)；再做两两归并,…,如此重复，最后得到一个长度为 n 的有序序列。
迭代的归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
void MergePass ( SortData initList[ ],SortData
mergedList[ ],int len ) {
int i = 0;
while (i+2*len-1 <= n-1) {
merge( initList,mergedList,
i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= n-1 )
merge( initList,mergedList,i,i+len-1,n-1);
else for ( int j = i; j <= n-1; j++)
mergedList [j] = initList[j];
}
归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
n/(2*len) O(n/len) 次,函数 MergeSort( )调用 MergePass( )正好?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂度为 O(nlog2n)。
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个稳定的排序方法 。
基数排序
多关键字排序例 对 52张扑克牌按以下次序排序：
2<?3<……<?A<?2<?3<……<?A<
2<?3<……<?A<?2<?3<……<?A
两个关键字：花色 （?<?<?<?）
面值 （ 2<3<……<A ）
并且“花色”地位高于“面值”
多关键字排序方法最高位优先法（ MSD),先对最高位关键字 k1（ 如花色）排序，将序列分成若干子序列，每个子序列有相同的 k1值；然后让每个子序列对次关键字 k2
（ 如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字 kd排序；
最后将所有子序列依次连接在一起成为一个有序序列最低位优先法 (LSD)：从最低位关键字 kd起进行排序，然后再对高一位的关键字排序,…… 依次重复，直至对最高位关键字 k1排序后，便成为一个有序序列
链式基数排序
基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法
链式基数排序 方法,用链表作存储结构的基数排序
设臵 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾指针
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至 10个链队列中，每个队列记录的关键字的个位相同
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将 10个队列链成一个链表
重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列例,初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一趟分配
930 063 083 184 505 278 008 109 589 269
一趟收集：
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二趟分配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集：
008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三趟分配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集：
各种排序方法的比较比较次数 移动次数 附加存储排 序 方 法最好 最差最好 最差稳定性最好 最差直接插入排序 n n
2
0 n
2
1
折半插入排序 n l o g
2
n 0 n
2
1
起泡排序
n n
2
0 n
2
1
快速排序 n l o g
2
n n
2
n l o g
2
n n
2
l o g
2
n n
2
简单选择排序 n
2
0 n? 1
锦标赛排序 n l o g
2
n n l o g
2
n? n
堆排序 n l o g
2
n n l o g
2
n? 1
归并排序
n l o g
2
n n l o g
2
n? n
插入排序
快速排序
选择排序
归并排序
基数排序
各种内排方法比较第十章内部排序概 述
排序,将一个数据元素的任意序列,重新排列成一个按关键字有序的序列 。
数据表 (datalist),它是待排序数据对象的有限集合 。
主关键字 (key),数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据,称为关键字 。 也称为 排序码 。
排序方法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],
且在排序之前,对象 r[i]排在 r[j]前面。如果在排序之后,对象 r[i]仍在对象 r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的 。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
内排序分类
依不同原则插入排序,交换排序,选择排序,归并排序,和计数排序等 。
依所须工作量简单排序 ---时间复杂度 o(n2)
先进排序方法 ---时间复杂度 o(n logn)
基数排序 ---时间复杂度 o(d.n)
插入排序 (Insert Sorting)
基本思想 当插入第 i (i? 1) 个对象时,前面的
V[0],V[1],…,V[i -1]已经排好序。这时,用
V[i]的排序码与 V[i-1],V[i-2],… 的排序码顺序进行比较,找到插入位臵即将 V[i]插入,原来位臵上的对象向后顺移。
基本思想 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位臵上,直到对象全部插入为止。
直接插入排序 (Insert Sort)
直接插入 排序过程
0 1 2 3 4 5 temp i = 1
i = 2
0 1 2 3 4 5 temp
21 0825 49 25* 16
21 25 0849 25* 16 25
21 25 0849 25* 16
21 25 0849 25* 16 49
21 25 0849 25* 16
i = 3 21 25 0849 25* 16 25*
21 25 084925* 16
i = 4
i = 5
21 25 084925* 16 16
21 25 084925*16
21 25 084925*16
21 2508 4925*16
08
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
算法分析
设待排序对象个数为 n,则该算法的主程序执行
n-1趟。
排序码比较次数和对象移动次数与对象排序码的初始排列有关。
最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较 1次,移动 2次对象,总的排序 码比较次数为 n-1,对象移动次数为 2(n-1)。
最坏情况下,第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较,并且每做 1次比较就要做 1次数据移动 。 则总排序码比较次数 KCN和对象移动次数 RMN分别为
在平均情况下的排序码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。
直接插入排序是一种稳定的排序方法。
1
1
1
1
22142
221
n
i
n
i
nnniR M N
nnniKCN
//))(()(
,//)(
2
2
折半插入排序 (Binary Insertsort)
基本思想 设在顺序表中有一 个对象序列 V[0],
V[1],…,V[n -1]。其中,V[0],V[1],…,V[i -1]
是已经排好序的对象。在插入 V[i] 时,利用折半搜索法寻找 V[i] 的插入位臵。
折半插入排序的算法
typedef int SortData;
void BinInsSort ( SortData V[ ],int n ) {
SortData temp; int Left,Right;
for ( int i = 1; i < n; i++) {
Left = 0; Right = i-1; temp = V[i];
while ( Left <= Right ) {
int mid = ( Left + Right )/2;
if ( temp < V[mid] ) Right = mid - 1;
else Left = mid + 1;
}
for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k];//
记录后移
V[Left] = temp; //插入
}
}
折半插入排序
0 1 2 3 4 5 temp
i = 1
i = 2
0 1 2 3 4 5 temp
5
21 33
i = 3
5
5
2153
21
4 4
i = 4 2153 8 8
i = 5 2153 16 168
4
4
213 84 5 16
折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。
它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第 i 个对象时,需要经过?log2i?+1 次排序码比较,才能确定它应插入的位臵。因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半插入排序所进行的排序码比较次数为：
1
1
22 lo g1lo g
n
i
nni
算法分析
当 n 较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差 。
在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少 。 折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列 。
折半插入排序是一个稳定的排序方法。
折半插入排序的时间复杂度为 o(n2)。
希尔排序 (Shell Sort)
基本思想 设待排序对象序列有 n 个对象,首先取一个整数 gap < n 作为间隔,将全部对象分为 gap 个子序列,所有距离为 gap 的对象放在同一个子序列中,在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap,
例如取 gap =?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1,将所有对象放在同一个序列中排序为止。
希尔排序方法又称为缩小增量排序。
i = 3
Gap = 3
0 1 2 3 4 5
21 0825 49 25* 16
0 1 2 3 4 5
21 08 25 4925*16
i = 2
Gap = 2 21 08 25 4925*16
2108 25 4925*16
i = 1
Gap = 1
2108 25 4925*16
2108 25 4925*16
希尔排序过程
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
希尔排序的算法
开始时 gap 的值较大,子序列中的对象较少,排序速度较快 ; 随着排序进展,gap 值逐渐变小,子序列中对象个数逐渐变多,由于前面大多数对象已基本有序,所以排序速度仍然很快。
Gap的取法有多种。 shell 提出取 gap =?n/2?,gap =
gap/2?，直到 gap = 1。
对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。
希尔排序所需的比较次数和移动次数约为 n 1.3
当 n趋于无穷时可减少到 n(log2 n)2
快速排序 ( Exchange Sort )
基本方法 设待排序对象序列中的对象个数为 n。
一般地,第 i趟起泡排序从 1到 n-i+1依次比较相邻两个记录地关键字,如果发生逆序，则交换之，
其结果是这 n-i+1个记录中，关键字最大的记录被交换到第 n-i+1的位臵上,最多作 n-1趟。
基本思想 是两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之,直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21
08
25
49
25
16
21
49
25
25
16
08
21
49
25
25
16
08
21
49
25
25
16
08 21
49
25
25
16
08
21
49
25
25
16
08
起泡排序的过程起泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1;
int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志臵为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
Swap ( V[j-1],V[j] ); //交换
exchange = 1; //标志臵为 1,有交换
}
i++;
}
}
思考题：如何实现双起泡
第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-
1]进行排序,结果将该序列中排序码最小的对象交换到序列的第一个位臵 (i-1),其它对象也都向排序的最终位臵移动 。。
最多做 n-1趟起泡就能把所有对象排好序 。
在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做 n-1次排序码比较,不移动对象 。 这是最好的情形 。
最坏的情形是算法执行 n-1趟起泡,第 i趟 (1?
i? n) 做 n- i 次排序码比较,执行 n-i 次对象交换 。 这样在最坏情形下总的排序码比较次数 KCN和对象移动次数 RMN为：
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninK C N
)()(
)()(
起泡排序是一个稳定的排序方法。
快速排序 (Quick Sort)
基本思想 是任取待排序对象序列中的某个对象 (例如取第一个对象 ) 作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：
左侧子序列中所有对象的排序码都小于或等于基准对象的排序码
右侧子序列中所有对象的排序码都大于基准对象的排序码
基准对象则排在这两个子序列中间 (这也是该对象最终应安放的位臵 )。
然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位臵上为止。
基准对象也称为 枢轴（或支点）记录。
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
快速排序算法描述快速排序的过程
21 0825 49 25* 16初始关键字
08 25 49 25* 1621
08 2549 25* 16
08 2549 25*16
08 254925*16
08 254925*16 21
prikey
一次交换二次交换三次交换四次交换完成一趟排序
i j
i
j
j
i
i j
j
i j
i
08 254925*16 21完成一趟排序分别进行快速排序 08 25 4925*16 21
有序序列 08 25 4925*16 21
快速排序的算法
void QuickSort ( SqList &L,int low,int high ){
//在序列 low?high 中递归地进行快速排序
if ( low < high) {
int pivotloc= Partition (L,low,high); //划分
QuickSort ( L,low,pivotloc-1); //对左序列同样处理
QuickSort ( 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;
}
算法 quicksort是一个递归的算法,其递归树如图所示。
算法 partition利用序列第一个对象作为基准，
将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准对象排序码的对象都移到序列左侧,最后基准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
算法分析
快速排序的趟数取决于递归树的高度。
如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
在 n个元素的序列中,对一个对象定位所需时间为 O(n)。若设 t (n) 是对 n 个元素的序列进行排序所需的时间,而且每次对一个对象正确定位后,正好把序列划分为长度相等的两个子序列,此时,总的计算时间为：
T(n)? cn + 2T(n/2 ) // c 是一个常数
cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)
2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8)
………
cn log2n + nT(1) = O(n log2n )
可以证明,函数 quicksort的平均计算时间也是 O(nlog2n)。 实验结果表明,就平均计算时间而言,快速排序是所有内排序方法中最好的一个 。
快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数 。
最大递归调用层次数与递归树的高度一致,
理想情况为?log2(n+1)? 。 因此,要求存储开销为 O(log2n)。
在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 总的排序码比较次数将达
快速排序是一种不稳定的排序方法 。
212
1 21
1
nnninn
i
)()(
基本思想 每一趟 (例如第 i 趟,
i = 0,1,…,n -2) 在后面 n-i 个待排序记录中选出排序码最小的记录,作为有序序列中的第 i 个记录。待到第
n-2 趟作完,待排序记录只剩下 1个,
就不用再选了。
选择排序
直接选择排序是一种简单的排序方法,它的基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最小排序码的对象；
② 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码的对象 。 在剩下的对象 V[i+1]～ V[n-1]中重复执行第 ①,② 步,直到剩余对象只有一个为止 。
直接选择排序 (Select Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2 08 16 25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
直接选择排序的过程最小者 25*
无交换49
25*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3 08 16 2521
最小者 25
无交换252116
08
各趟排序后的结果直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位臵
Swap ( V[i],V[k] );
}
}
直接选择排序的排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象,
则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为
2
0 2
11n
i
nninKCN )()(
对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数 RMN = 0，达到最少。
最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。
直接选择排序是一种不稳定的排序方法。
堆排序 ( Heap sort )
堆 ( Heap )设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 0开始连续编号。若满足
Ki? K2i+1 && Ki? K2i+2
或 Ki? K2i+1 && Ki? K2i+2,
则称该关键字集合构成一个堆。
前者成为最小堆，后者称为最大堆。
完全二叉树顺序表示
Ki? K2i+1 &
Ki? K2i+2
完全二叉树顺序表示
Ki? K2i+1 &&
Ki? K2i+2
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
堆排序 (Heap Sort)
利用堆及其运算,可以很容易地实现选择排序的思路。
堆排序分为两个步骤
根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
通过一系列的对象交换和重新调整堆进行排序。
自下向上逐步调整为小顶堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
i = 4 i = 3
i
初始小顶堆的建立过程
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
i = 2
i
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
i = 1
i
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i53
建成堆
void Crt_MinHeap ( MinHeap *H,
HeapData arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆
for ( int i = 0; i < n; i++ ) H->data[i] = arr[i];
H->CSize = n; //数组传送及当前堆大小
int CPos = (H->CSize-2)/2; //最后分支结点
while ( CPos >= 0 ) { //从下到上逐步扩大堆
FilterDown ( &H,CPos,H->CSize-1 );
CPos--;
}
}
堆的建立
void FilterDown ( MinHeap *H,int start,
int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
HeapData temp = H->data[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap && //两子女中选小者
H->data[j] > H->data[j+1] ) j++;
if ( temp <= H->data[j] ) break;
else { H->data[i] = H->data[j];
i = j; j = 2*j+1; } //向下滑动
}
H->data[i] = temp;
}
最小堆的向下调整算法初始大顶堆的建立过程
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
初始排序码集合 i = 2 时的局部调整
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
i = 0 时的局部调整形成最大堆
i = 1 时的局部调整最大堆的向下调整算法
void FilterDown ( MaxHeap *H,
int start,int EndOfHeap ) {
int i = start; int j = 2*i+1;
HeadData temp = H->data[i];
while ( j <= EndOfHeap ) { //最后位臵
if ( j < EndOfHeap &&
H->data[j] < H->data[j+1] )
j = j+1; //选两子女的大者
if ( temp >= H->data[j] ) break;
else {
H->data[i] = H->data[j]; //大 子女上移
i = j; j = 2*j+1; //向下继续调整
}
}
H->data[i] = temp; //回放到合适位臵
}
将表转换成堆
for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 );
基于初始堆 (大顶堆 )进行堆排序
最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换到最后,再对前面的 n-1个对象,使用堆的调整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位臵。
再对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位初始最大堆基于初始堆进行堆排序
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位从 0 号到 4 号 重新调整为最大堆
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位从 0 号到 3 号 重新调整为最大堆
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位从 0 号到 2 号 重新调整为最大堆
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位从 0 号到 1 号 重新调整为最大堆堆排序的算法
void HeapSort ( MaxHeap *H ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序。
for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 ); //初始堆
for ( i = H->CSize-1; i >= 1; i--) {
Swap ( H->data[0],H->data[i] ); //交换
FilterDown ( H,0,i-1 ); //重建最大堆
}
}
若设堆中有 n 个结点,且 2k-1? n? 2k,则对应的完全二叉树有 k 层。在第 i 层上的结点数? 2i (i = 0,1,…,k -1)。 在第一个形成初始堆的 for 循环中对每一个非叶结点调用了一次堆调整算法 FilterDown( ),因此该循环所用的计算时间为：
其中,i 是层序号,2i 是第 i 层的最大结点数,
(k-i-1)是第 i 层结点能够移动的最大距离。
2
0
22
k
i
i ik 1
堆排序的算法分析
第二个 for循环中调用了 n-1次 FilterDown( )算法,该循环的计算时间为 O(nlog2n)。因此,堆排序的时间复杂性为 O(nlog2n)。
该算法的附加存储主要是在第二个 for循环中用来执行对象交换时所用的一个临时对象。
因此，该算法的空间复杂性为 O(1)。
堆排序是一个不稳定的排序方法。
n
j
n
j
jik
k
j
k
j
jj
k
k
j
jk
k
i
i
4
1
1
1
1
1
1
1
1
2
0
2
2
2
22
22122 )(
归并排序 (Merge Sort)
归并 将两个或两个以上的有序表合并成一个新的有序表。
两路归并 (2-way merging)原始序列
initList[ ]中两个有序表 initList[l] …
initList[m]和 initList[m+1] … initList[n],它们可归并成一个有序表,存于另一对象序列
mergedList的 l … n 中。
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
设变量 i 和 j 是表 initList[l … m] 和 initList [m+1…
n]的当前检测指针。 k 是存放指针。
当 i 和 j 都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的对象排放到新表 k 所指位臵 中；
当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。
i j
typedef int SortData;
void merge ( SortData InitList[ ],SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较将较小的并入
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }//将 mid前剩余的并入
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; } //将 mid后剩余的并入
}
两路归并算法一趟归并排序的情形
设 initList[0]到 initList[n-1]中 n 个对象已经分为一些长度为 len 的归并项,将这些归并项两两归并,归并成长度为 2len 的归并项,
结果放到 mergedList[ ]中。
如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
剩下一个长度为 len的归并项和另一个长度不足 len的归并项,可用 merge算法将它们归并成一个长度小于 2len 的归并项。
只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList[ ]中。
迭代的归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到?n / 2? 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为 1)；再做两两归并,…,如此重复，最后得到一个长度为 n 的有序序列。
迭代的归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
void MergePass ( SortData initList[ ],SortData
mergedList[ ],int len ) {
int i = 0;
while (i+2*len-1 <= n-1) {
merge( initList,mergedList,
i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= n-1 )
merge( initList,mergedList,i,i+len-1,n-1);
else for ( int j = i; j <= n-1; j++)
mergedList [j] = initList[j];
}
归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
n/(2*len) O(n/len) 次,函数 MergeSort( )调用 MergePass( )正好?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂度为 O(nlog2n)。
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个稳定的排序方法 。
基数排序
多关键字排序例 对 52张扑克牌按以下次序排序：
2<?3<……<?A<?2<?3<……<?A<
2<?3<……<?A<?2<?3<……<?A
两个关键字：花色 （?<?<?<?）
面值 （ 2<3<……<A ）
并且“花色”地位高于“面值”
多关键字排序方法最高位优先法（ MSD),先对最高位关键字 k1（ 如花色）排序，将序列分成若干子序列，每个子序列有相同的 k1值；然后让每个子序列对次关键字 k2
（ 如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字 kd排序；
最后将所有子序列依次连接在一起成为一个有序序列最低位优先法 (LSD)：从最低位关键字 kd起进行排序，然后再对高一位的关键字排序,…… 依次重复，直至对最高位关键字 k1排序后，便成为一个有序序列
链式基数排序
基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法
链式基数排序 方法,用链表作存储结构的基数排序
设臵 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾指针
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至 10个链队列中，每个队列记录的关键字的个位相同
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将 10个队列链成一个链表
重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列例,初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一趟分配
930 063 083 184 505 278 008 109 589 269
一趟收集：
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二趟分配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集：
008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三趟分配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集：
各种排序方法的比较比较次数 移动次数 附加存储排 序 方 法最好 最差最好 最差稳定性最好 最差直接插入排序 n n
2
0 n
2
1
折半插入排序 n l o g
2
n 0 n
2
1
起泡排序
n n
2
0 n
2
1
快速排序 n l o g
2
n n
2
n l o g
2
n n
2
l o g
2
n n
2
简单选择排序 n
2
0 n? 1
锦标赛排序 n l o g
2
n n l o g
2
n? n
堆排序 n l o g
2
n n l o g
2
n? 1
归并排序
n l o g
2
n n l o g
2
n? n
