- 归并排序
- 归并排序的基本思想
- 归并排序的实现代码
- 归并排序的性能分析
- 完整代码
归并排序 归并排序的基本思想
归并排序与前面讲到的基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。
二路归并的基本思想：
假定待排序表含有
n
n
n 个记录，可将其视为
n
n
n 个有序的子表，每个子表的长度为1，然后两两归并，得到
⌈
n
/
2
⌉
lceil n/2 rceil
⌈n/2⌉个长度为2或1的有序表；再两两归并……如此重读，直到合并成一个长度为
n
n
n 的有序表为止。
这种排序方法称为2路归并排序。
2路归并排序的例子：
归并排序的实现代码
归并排序的实现需要两个算法，一个是按 l e n len len做一趟两两归并，另一个是归并排序。
M
e
r
g
e
(
)
Merge()
Merge()的功能是将前后相邻的两个有序表归并为一个有序表。
设两段有序表
L
.
d
a
t
a
[
l
o
w
.
.
.
m
i
d
]
L.data[low...mid]
L.data[low...mid]、
L
.
d
a
t
a
[
m
i
d
+
1...
h
i
g
h
]
L.data[mid+1...high]
L.data[mid+1...high]存在放同一顺序表中的相邻位置，先将它们复制到辅助数组
B
[
]
B[]
B[]中。每次从对应B中的两个段取出一个记录进行关键字的比较，较小者放入
L
.
d
a
t
a
[
]
L.data[]
L.data[]中，当数组
B
[
]
B[]
B[]中有一段的下标超出其对应的表长（即该段元素已经完全复制到
L
.
d
a
t
a
[
]
L.data[]
L.data[]中）时，将另一端中的剩余部分直接复制到
L
.
d
a
t
a
[
]
L.data[]
L.data[]中。
//合并
void Merge(SeqList &L, int low, int mid, int high){
int B[L.n]; //辅助数组B
int i,j,k;
for(k=low; k<=high; k++)
B[k] = L.data[k]; //将L.data中的所有元素复制到B中
for(i=low, j=mid+1, k=i; i<=mid&&j<=high; k++){
if(B[i] <= B[j]) //比较B的左右两段中的元素
L.data[k] = B[i++]; //较小的值复制到L.data中
else
L.data[k] = B[j++];
}
while(i<=mid) L.data[k++] = B[i++]; //若第一个表未检测完，复制
while(j<=high) L.data[k++] = B[j++]; //若第二个表未检测完，复制
}
归并排序（递归）：
//归并排序
void MergeSort(SeqList &L, int low, int high){
if(low
归并排序的性能分析
空间复杂度
由于辅助空间占用
n
n
n 个单元，故归并排序的空间复杂度为
O
(
n
)
O(n)
O(n)。
时间复杂度
每趟归并的时间复杂度为
O
(
n
)
O(n)
O(n)，总共需要进行
⌈
l
o
g
2
n
⌉
lceil log_2n rceil
⌈log2n⌉趟归并，所以算法的时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)。
稳定性
由于
M
e
r
g
e
(
)
Merge()
Merge() *** 作不会改变相同关键字记录的相对次序，故二路归并排序算法是一种稳定的排序方法。
完整代码
#include
using namespace std;
#define maxSize 20
typedef struct{
int data[maxSize];
int n;
}SeqList;
void PrintList(SeqList L){
for(int i=0; i>n;
for(int i=0; i>L.data[i];
}
L.n = n;
cout<
运行结果：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）