数据结构-归并排序与基数排序

归并排序与基数排序

归并排序

对于大列表数据的排序,一个有效的排序算法是归并排序。其基本思想就是,将两个或两个以上的的有序子序列“归并”为一个有序序列。在内部排序中,通常采用的是二路归并排序,即将两个位置相邻的有序子序列“归并”为一个有序序列。

二路归并排序基本思想

将有n个记录的原始序列看作n个有序子序列,每个子序列的长度为1,然后从第一个子序列看是,把相邻的子序列两两合并后排序,得到n/2个长度为2或1的有序子序列,把这一过程称为一次归并排序,对一次归并排序的n/2个子序列采用上述方法继续顺序成对归并排序,如此重复,当最后得到长度为n的一个子序列时,该子序列便是原始序列归并排序后的有序序列。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public int[] mergeSort(int[] data){
int k = 1;
while(k<data.length){
merge(data,k);
k *= 2;
}
return data;
}
public void merge(int[] data,int len){
int m = 0; //临时顺序表的起始位置
int l1 = 0; //第一个有序表的起始位置
int h1; //第一个有序表的结束位置
int l2; //第二个有序表的起始位置
int h2; //第二个有序表的结束位置
int i = 0;
int j = 0;
//临时表
int[] tmp = new int[data.length];
//一次归并处理
while(l1 + len < data.length){
h1 = l1 + len - 1; //第一个有序表的结束位置
l2 = l1 + len; //第二个有序表的起始位置
//第二个有序表结束位置
h2 = (l2 + len - 1 < data.length) ? l2 + len -1 :data.length - 1;
j = l2;
i = l1;
//两个有序表中的记录没有排序
while((i<=h1)&&(j<=h2)){
//第一个有序表中记录的关键码小于第二个有序表记录的关键码
if(data[i] <= data[j]) tmp[m++] = data[i++];
//第二个有序表记录的关键码小于第一个有序表记录的关键码
else tmp[m++] = data[j++];
}
//第一个有序表中还有记录没有排序
while(i<=h1) tmp[m++] = data[i++];
//第二个有序表中还有记录没有排序
while(j<=h2) tmp[m++] = data[j++];
l1 = h2 + 1;
}
i = l1;
//原顺序表中还有记录没有被排序
while(i<data.length) tmp[m++] = data[i++];
//复制回来
for(i=0;i<data.length;i++){
data[i] = tmp[i];
}
}

时间复杂度:O(nlog2n)

基数排序

前面介绍的排序算法主要是通过关键码的比较和记录的移动两种操作来实现排序,都属于“比较性”的排序法,也就是每次排序时,都比较整个键值的大小来排序。基数排序则是属于“分配式排序”,排序过程无需比较关键字值,而是通过“分配”和“收集”过程来实现排序。

基本思想

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------