归并排序是一种经典的排序算法,它基于分治策略将一个大问题分解为多个小问题,然后将小问题的解合并起来得到最终的解。该算法的核心思想是将待排序的数组不断地二分,直到每个子数组只有一个元素,然后再将这些子数组两两合并,直到最终得到有序的数组。
归并排序的步骤如下:
归并排序的倒置计数是指在排序过程中统计数组中的倒置对数,即数组中的逆序对数量。倒置对是指在数组中,如果i < j 且 A[i] > A[j],则称(A[i], A[j])为一个倒置对。倒置计数可以用于衡量数组的有序程度。
C++实现归并排序的代码如下:
#include <iostream>
#include <vector>
using namespace std;
// 合并两个有序数组
void merge(vector<int>& nums, int left, int mid, int right, int& count) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
count += mid - i + 1; // 统计倒置对数
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int p = 0; p < temp.size(); p++) {
nums[left + p] = temp[p];
}
}
// 归并排序
void mergeSort(vector<int>& nums, int left, int right, int& count) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, count);
mergeSort(nums, mid + 1, right, count);
merge(nums, left, mid, right, count);
}
// 归并排序入口函数
vector<int> mergeSort(vector<int>& nums) {
int count = 0;
mergeSort(nums, 0, nums.size() - 1, count);
return nums;
}
int main() {
vector<int> nums = {5, 2, 6, 1, 3, 4};
vector<int> sortedNums = mergeSort(nums);
cout << "排序结果:";
for (int num : sortedNums) {
cout << num << " ";
}
cout << endl;
cout << "倒置对数:" << count << endl;
return 0;
}
归并排序的时间复杂度为O(nlogn),其中n为待排序数组的长度。它是一种稳定的排序算法,适用于各种规模的数组排序。
归并排序的应用场景包括但不限于:
腾讯云提供的相关产品和服务包括:
更多关于腾讯云产品和服务的信息,请访问腾讯云官方网站:https://cloud.tencent.com/
领取专属 10元无门槛券
手把手带您无忧上云