归并排序(merge sort)

组别:提高级
难度:5

归并排序是基于分治算法的一种排序,我们把一个问题分解成子问题,每个子问题再分别解决,最后再把子问题的解合并成最终结果。

如下图数列{6,5,12,10,9,1},首先将数列分成两分{6,5,12}和{10,9,1},再把这俩个子数列继续分解成{6},{5,12},{10},{9,1} ,当就子数列就剩两个元素时比较大小,现把子数列逐级合并成一个有序数列。

Merge Sort (With Code)

代码实现:

 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
63
64
65
66
/**************************************************************** 
 * Description: 用C++实现归并算法,Merge sort in C++
 * Author: Alex Li
 * Date: 2022-02-10 19:55:32
 * LastEditTime: 2023-11-11 21:58:28
****************************************************************/

#include <iostream>
using namespace std;

int arr[100]; //定义主数组
int left_array[100],right_array[100];// 创建两个子数组Left_array和right_array

// 合并两个子数组Left_arr和Right_arr到主数组里,
void merge(int arr[], int left, int middle, int right) {
  

//把arr数组分以middle为边界,别给到左子数组left_sub和右子数组left_right
  for (int i = left; i <=middle; i++)left_array[i] = arr[i];
  for (int j = middle+1; j <=right; j++)right_array[j] = arr[j];
  //维护子数组和主数组的当前索引
  int left_index=left, right_index=middle+1, merged_index=left;
  
  // 在Left和Right数组中挑选最大的元素放入到主数组中,
  while (left_index <= middle || right_index <= right) {
     if(right_index>right||left_index<=middle&&left_array[left_index]<right_array[right_index]){
      arr[merged_index++]=left_array[left_index++];
     }
     else arr[merged_index++]=right_array[right_index++];
  
  }
 return ;
}


//把主数组元素分解成两个子元素,排序并合并子数组
void mergeSort(int arr[], int begin, int end) {
  if (begin < end) {
    //middle是把主数组分成两个子数组的点
    int middle = begin + (end - begin) / 2;
    mergeSort(arr, begin, middle);
    mergeSort(arr, middle + 1, end);
    // 合并排好序的子数组,Merge the sorted subarrays
    merge(arr, begin, middle , end);
  }
}

// 打印排好序数组,Print the sorted array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

//主程序
int main() {
  int size;
  cout<<"please input number for array size: ";
  cin>>size;
  cout<<"please input "<<size<<" elements of array:";
  for (int i = 0; i <size; i++)cin>>arr[i];
  mergeSort(arr, 0, size - 1);
  cout << "Sorted array: \n";
  printArray(arr, size);
  return 0;
}
Scroll to Top