歸并排序是穩定的
時間復雜度：O(NlogN)
空間復雜度：O(N)
合并 + 遞歸
http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
http://baike.baidu.com/view/90797.htm
http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.5.1.html
http://www.zjhyzx.net/Article/ShowArticle.asp?ArticleID=924
http://learn.akae.cn/media/ch11s04.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 void merge(int array[], int low, int mid, int high)
7 {
8 int i, k;
9 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
10 int begin1 = low;
11 int end1 = mid;
12 int begin2 = mid + 1;
13 int end2 = high;
14
15 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
16 if(array[begin1]<=array[begin2])
17 temp[k] = array[begin1++];
18 else
19 temp[k] = array[begin2++];
20 if(begin1 <= end1) //若第一個序列有剩余，直接拷貝出來粘到合并序列尾
21 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
22 if(begin2 <= end2) //若第二個序列有剩余，直接拷貝出來粘到合并序列尾
23 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
24 memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
25 free(temp);
26 }
27
28 void merge_sort(int array[], unsigned int first, unsigned int last)
29 {
30 int mid = 0;
31 if(first<last)
32 {
33 mid = (first+last)/2;
34 merge_sort(array, first, mid);
35 merge_sort(array, mid+1,last);
36 merge(array,first,mid,last);
37 }
38 }
39
40 int main()
41 {
42 int a[8] = {4, 7, 5, 3, 2, 8, 6, 1};
43 for (int i = 0; i != 8; ++i)
44 {
45 cout << a[i] << ' ';
46 }
47 cout << endl;
48 merge_sort(a, 0, 7);
49 for (int i = 0; i != 8; ++i)
50 {
51 cout << a[i] << ' ';
52 }
53 cout << endl;
54 }
posted on 2011-06-22 00:13
unixfy 閱讀(113)
評論(0) 編輯 收藏 引用