归并排序 c++ 代码简单
时间: 2024-09-09 12:00:20 浏览: 16
归并排序是一种经典的分治算法,它的基本思想是将数组分为两半,分别对每一半进行排序,然后合并两个已排序的部分。以下是C++语言实现归并排序的一个简单版本:
```cpp
#include <iostream>
#include <vector>
// 合并函数,用于合并两个已排序的区间
void merge(std::vector<int>& arr, int left, int mid, int right) {
std::vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余未复制的数据添加到temp
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的内容回填到原数组
for (i = left, k = 0; i <= right; ++i, ++k) {
arr[i] = temp[k];
}
}
// 归并排序主函数
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> numbers = {9, 7, 5, 11, 12, 2, 14, 3};
int n = numbers.size();
std::cout << "Original array: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << "\n";
mergeSort(numbers, 0, n - 1);
std::cout << "Sorted array: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
return 0;
}
```