数组的几种排序算法的实现(3)
算法描述
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
归并排序
归并排序具体工作原理如下(假设序列共有n个元素):
将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素
将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
重复步骤2,直到所有元素排序完毕
示例代码
C语言
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
//归并操作 void Merge( int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{ int i, j, k;
for (i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
{
if (sourceArr[startIndex] < sourceArr[i])
{
targetArr[j] = sourceArr[startIndex++];
}
else
{
targetArr[j] = sourceArr[i++];
}
}
if (startIndex <= midIndex)
{
for (k = 0; k <= midIndex-startIndex; k++)
{
targetArr[j+k] = sourceArr[startIndex+k];
}
}
if (i <= endIndex)
{
for (k = 0; k <= endIndex- i; k++)
{
targetArr[j+k] = sourceArr[i+k];
}
}
} //内部使用递归,空间复杂度为n+logn void MergeSort( int sourceArr[], int targetArr[], int startIndex, int endIndex)
{ int midIndex;
int tempArr[100]; //此处大小依需求更改
if (startIndex == endIndex)
{
targetArr[startIndex] = sourceArr[startIndex];
}
else
{
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(tempArr, targetArr,startIndex, midIndex, endIndex);
}
} //调用 int _tmain( int argc, _TCHAR* argv[])
{ int a[8]={50,10,20,30,70,40,80,60};
int b[8];
MergeSort(a, b, 0, 7);
for ( int i = 0; i < sizeof (a) / sizeof (*a); i++)
cout << b[i] << ' ' ;
cout << endl;
system ( "pause" );
return 0;
} |