1
/**//*
2
名称：归并排序
3 最坏时间复杂度（降序）：O(n * lg (n))
4 最好时间复杂度（升序）：O(n)
5
*/
6
#include <iostream>
7#include <time.h>
8#include <stdlib.h>
9using namespace std;
10void mergeSort(int*, int);
11void __mergeSort(int*, int, int);
12void merge(int*, int, int, int);
13int main(void)
14
{
15 int n;
16 int *array;
17
srand(time(NULL)); /**//*void srand(unsigned seed)；*/
18 while (true)
19 {
20 cin >> n;
21 array = new int[n];
22 /**//*随机生成数组*/
23 for (int i = 0; i < n; ++i)
24 {
25 array[i] = rand() % 100; /**//*int rand(void)；*/
26
}
27
28 /**//*排序前*/
29 for (int i = 0; i < n; ++i)
30 {
31 cout << array[i] << ' ';
32 }
33 cout << endl;
34
35 /**//*归并排序*/
36 mergeSort(array, n);
37
38 /**//*排序后*/
39 for (int i = 0; i < n; ++i)
40 {
41 cout << array[i] << ' ';
42 }
43 cout << endl;
44
45 delete array;
46 }
47 return 0;
48}
49void mergeSort(int* array, int length)
50{
51 __mergeSort(array, 0, length - 1);
52}
53void __mergeSort(int* array, int first, int last)
54{
55 /**//*只有有两个元素*/
56 if (first < last)
57 {
58 int middle = first + (last - first) / 2;
59 __mergeSort(array, first, middle);
60 __mergeSort(array, middle + 1, last);
61 merge(array, first, middle, last);
62 }
63}
64void merge(int* array, int first, int middle, int last)
65{
66 int* temp = new int[last - first + 1];
67 int i = first;
68 int j = middle + 1;
69 int k = 0;
70 while (i <= middle && j <= last)
71 {
72 /**//*取较小者*/
73 if (array[i] <= array[j])
74 {
75 temp[k] = array[i];
76 ++i;
77 }
78 else
79 {
80 temp[k] = array[j];
81 ++j;
82 }
83 ++k;
84 }
85 /**//*前半部分没有复制完*/
86 if (i <= middle)
87 {
88 while (i <= middle)
89 {
90 temp[k] = array[i];
91 ++i;
92 ++k;
93 }
94 }
95 /**//*后半部分没有复制完*/
96 if (j <= last)
97 {
98 while (j <= last)
99 {
100 temp[k] = array[j];
101 ++j;
102 ++k;
103 }
104 }
105 /**//*复制回原数组*/
106 for (int p = first, q = 0; p <= last; ++p, ++ q)
107 {
108 array[p] = temp[q];
109 }
110 /**//*释放内存*/
111 delete temp;
112}
posted on 2012-10-21 23:46
zhuxin 阅读(233)
评论(0) 编辑 收藏 引用 所属分类:
排序算法