给我一份完整的C++代码，用分治法实现一组无序序列的两路合并排序和快速排序。要求掌握合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。

### C++ 分治法实现两路合并排序和快速排序 以下是基于分治策略的两种经典排序算法——两路合并排序（Merge Sort）和快速排序（Quick Sort）的C++代码示例。 #### 两路合并排序 (Merge Sort) 两路合并排序是一种典型的分治算法，其核心思想是将数组分成两个子数组分别递归排序，然后再将这两个有序子数组合并成一个整体有序数组[^1]。 ```cpp #include <iostream> #include <vector> void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; std::vector<int> L(n1), R(n2); for(int i = 0; i < n1; ++i){ L[i] = arr[left + i]; } for(int j = 0; j < n2; ++j){ R[j] = arr[mid + 1 + j]; } int i = 0, j = 0, k = left; while(i < n1 && j < n2){ if(L[i] <= R[j]){ arr[k++] = L[i++]; }else{ arr[k++] = R[j++]; } } while(i < n1){ arr[k++] = L[i++]; } while(j < n2){ arr[k++] = R[j++]; } } void mergeSort(std::vector<int>& arr, int left, int right){ if(left >= right){ return; } int mid = left + (right - left)/2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } ``` 上述代码实现了标准的两路合并排序逻辑。通过`mergeSort()`函数递归调用自身来分割数组，并最终由`merge()`函数完成合并操作[^1]。 #### 快速排序 (Quick Sort) 快速排序同样是经典的分治算法之一，它通过选取一个“基准”元素将数据划分为左右两部分，使得左边的数据都小于等于该基准而右边的大于等于该基准，之后再对这两部分递归应用相同的操作[^2]。 ```cpp int partition(std::vector<int>& arr, int low, int high){ int pivot = arr[high]; int i = low - 1; for(int j = low; j <= high - 1; ++j){ if(arr[j] < pivot){ i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return (i + 1); } void quickSort(std::vector<int>& arr, int low, int high){ if(low < high){ int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } ``` 此段代码展示了如何利用分治方法执行快速排序的过程。其中`partition()`负责重新排列数组并返回分区索引位置；随后，在`quickSort()`里依据这个索引来进一步划分待处理区间[^2]。