图解（来源于网络）
别的大佬的一个讲解归并排序的视频
代码详解
#include#include using namespace std; void Merge_sort(vector &array, vector &tempArray, int left, int right); void merge(vector &array, vector &tempArray, int left, int mid, int right); void Arr_print(vector arr); //归并的入口函数 void Merge_sort(vector &array, vector &tempArray, int left, int right) { int mid = (left + right) / 2; //获得中间元素的下标，将数组一分为二 if (left < right) { Merge_sort(array, tempArray, left, mid); //左半部分数组一分为二 Merge_sort(array, tempArray, mid+1, right); //右半部分数组一分为二 merge(array, tempArray, left, mid, right); //将上面一分为二的部分归并排序 Arr_print(array); } } void merge(vector &array, vector &tempArray, int left, int mid, int right) { //左边区域第一个没有排序的元素下标 int l_index = left; //右边区域第一个没有排序的元素下标 int r_index = mid + 1; //临时数组开始的元素下标 int temp_index = left; //复制时候的开始下标 int copy_index = left; //开始合并 while (l_index <= mid && r_index <= right) { // 比较两段元素中头元素的大小，取最小的元素放入临时数组中 if (array[l_index] < array[r_index]) tempArray[temp_index++] = array[l_index++]; else tempArray[temp_index++] = array[r_index++]; } //若左半边元素有剩余 while(l_index<=mid) tempArray[temp_index++] = array[l_index++]; //若右半边元素有剩余 while(r_index<=right) tempArray[temp_index++] = array[r_index++]; //将临时数组中的数据，此时已经排好顺序，拷贝到原数组中 while (copy_index <= right) { array[copy_index] = tempArray[copy_index]; copy_index++; } } //打印数组函数 void Arr_print(vector arr) { for (auto a : arr) cout << a; cout << endl; } int main() { vector arr = { 8,7,6,5,4,3,2,1}; cout << "原数组为:" << endl;; Arr_print(arr); cout << "开始归并" << endl; vector tempArr; tempArr.resize(arr.size()); int start_index = 0; int end_index = arr.size() - 1; Merge_sort(arr, tempArr, start_index, end_index); }
输出为
原数组为:
87654321
开始归并
78654321
78564321
56784321
56783421
56783412
56781234
12345678
