归并排序

 1 //自己编写的各种排序算法的头文件。
 2 #ifndef _SORT_H
 3 #define _SORT_H
 4 //冒泡排序
 5 class bubble_sort{
 6 private:
 7     int *Array,Length;
 8 public:
 9     bubble_sort(int *Array1,int Length);
10     int *sort_bubble();
11 
12 };
13 //归并排序
14 class merge_sort{
15 public:
16      static void sort_merge(int Array1[], int Array2[], int Left, int Rightend, int Right,int recursion);
17      static void Merge(int Array1[], int Array2[], int Left, int Rightend);//递归方法
18      static void Merge_pass(int Array1[], int Array2[], int ordered_len,int Length);
19      static void Merge1(int Array1[], int Array2[], int Length);//非递归方法
20 };
21 #endif

 1 #include "Sort.h"
 2 /*下面是对两个有序的数组进行归并的函数，middle
 3 是在一个长数组中的分隔点，将一个数组分成两个数组进行归并。*/
 4 void merge_sort::sort_merge(int Array1[], int Array2[], int Left, int Rightend, int Right,int recursion)
 5 {    
 6     int Leftend = Right - 1;
 7     int i = Left;
 8     int Length = Rightend - Left + 1;
 9     while (Left<=Leftend&&Right<=Rightend)//考虑在两边数组没有任何一个数组全都归并到大数组路面去的情况。
10         Array2[i++] = Array1[Left] < Array1[Right] ? Array1[Left++] : Array1[Right++];    
11     while (Right <= Rightend)
12         Array2[i++] = Array1[Right++];
13     while (Left <= Leftend)
14         Array2[i++] = Array1[Left++];
15     if (recursion)//判断是否递归调用。
16     {
17         for (int j = 0; j < Length; j++, Rightend--)
18             Array1[Rightend] = Array2[Rightend];
19     }
20 }
21 void merge_sort::Merge(int Array1[], int Array2[], int Left, int Rightend)
22 {
23     if (Rightend  > Left)
24     {
25         int middle = (Left + Rightend) / 2;
26         Merge(Array1, Array2, Left, middle);
27         Merge(Array1, Array2, middle + 1, Rightend);
28         merge_sort::sort_merge(Array1, Array2, Left, Rightend, middle + 1,1);
29     }
30 }
31 void merge_sort::Merge_pass(int Array1[], int Array2[], int ordered_len,int Length)
32 {
33     int i = 0;
34     for (; i <= Length - 2 * ordered_len; i += 2 * ordered_len)
35         merge_sort::sort_merge(Array1, Array2, i, i + ordered_len, i + 2 * ordered_len - 1,0);
36     if (i < Length - ordered_len)
37         merge_sort::sort_merge(Array1, Array2, i, i + ordered_len, Length - 1,0);
38     else
39         for (; i < Length; i++)
40             Array2[i] = Array1[i];
41 }
42 void merge_sort::Merge1(int Array1[], int Array2[], int Length)
43 {
44     int ordered_len = 1;//初始有序长度皆为1。
45     while (ordered_len < Length)
46     {//注意：上下两次调用参数Array1和Array2位置互换，就是为了在不断排序后最终将结果存在Array1中。
47         merge_sort::Merge_pass(Array1, Array2, ordered_len, Length);
48         ordered_len *= 2;
49         merge_sort::Merge_pass(Array2, Array1, ordered_len, Length);
50         ordered_len *= 2;
51     }
52 }

 1 /*************************
 2       Write by Leo Lv
 3       2019.3.31
 4       Merge sort
 5 *************************/
 6 #include <iostream>
 7 #include "Sort.h"
 8 using namespace std;
 9 int main()
10 {
11     int Array1[10] = { 4, 700, 80, 2000, 6, 3, 7, 10, 5,0 };    
12     int *Array2;
13     Array2 = (int*)malloc(11*sizeof(int));    
14     if (Array2 != NULL)//判断空间是否创建成功
15     {
16         merge_sort::Merge(Array1, Array2, 0, 9);
17         
18         cout << "归并算法结果如下" << endl;
19         for (int i = 0; i < (sizeof(Array1) / sizeof(int)); i++)
20         {
21             cout << Array1[i] << endl;
22         }
23         merge_sort::Merge1(Array1, Array2, (sizeof(Array1) / sizeof(int)));
24         cout << "非归并算法结果如下" << endl;
25         for (int i = 0; i < (sizeof(Array1) / sizeof(int)); i++)
26         {
27             cout << Array1[i] << endl;
28         }
29         free(Array2);//记得释放动态空间。
30         system("pause");
31         return 0;
32     }
33     else
34         return -1;    
35 
36 }