C/C++二路归并排序

二路归并排序"/>

C/C++二路归并排序

堆排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

动态演示

代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//进行合并
void merge(vector<int>& arr, int start, int end, vector<int>& result) {int left_length = (end - start + 1) / 2 + 1;int left_index = start;int right_index = start + left_length;int result_index = start;while (left_index < start + left_length && right_index < end + 1) {if (arr[left_index] <= arr[right_index]) {result[result_index++] = arr[left_index++];}else {result[result_index++] = arr[right_index++];}}while (left_index < start + left_length) {result[result_index++] = arr[left_index++];}while (right_index < end + 1) {result[result_index++] = arr[right_index++];}
}
void merge_sort(vector<int>& arr, int start, int end, vector<int>& result) {if (end - start == 1) {if (arr[start] > arr[end]) {swap(arr[start], arr[end]);}return;}else if (end - start == 0) {return;}else {merge_sort(arr, start, (end - start + 1) / 2 + start, result);merge_sort(arr, (end - start + 1) / 2 + start + 1, end, result);merge(arr, start, end, result);for (int i = start; i <= end; i++) {arr[i] = result[i];}}
}
void print_arr(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n; i++) {cout << arr[i] << "  ";}cout << endl;
}
int main() {vector<int> arr = { 9,5,6,8,7,4,2,3,1 };vector<int> result(arr.size(), 0);cout << "排序前：" << endl;print_arr(arr);merge_sort(arr,0,arr.size()-1,result);cout << "排序后：" << endl;print_arr(arr);system("pause");return 0;
}

结果输出