如何用sort计算交换了多少次
时间: 2024-05-02 13:20:33 浏览: 69
您可以使用归并排序或冒泡排序来计算交换次数。如果使用归并排序,则可以在每次合并两个有序数组时计算交换次数。如果使用冒泡排序,则需要在每次交换时计算交换次数。具体实现可以参考以下代码:
归并排序:
```
int merge(vector<int>& nums, int left, int mid, int right) {
int i = left, j = mid + 1;
int cnt = 0;
vector<int> tmp(right - left + 1);
int k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
cnt += mid - i + 1; // 计算交换次数
}
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= right) tmp[k++] = nums[j++];
for (int p = 0; p < k; p++) {
nums[left + p] = tmp[p];
}
return cnt;
}
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
int cnt = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
cnt += merge(nums, left, mid, right);
return cnt;
}
int main() {
vector<int> nums = {5, 2, 6, 1};
int cnt = mergeSort(nums, 0, nums.size() - 1);
cout << cnt << endl; // 输出交换次数
return 0;
}
```
冒泡排序:
```
int bubbleSort(vector<int>& nums) {
int n = nums.size();
int cnt = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
cnt++; // 计算交换次数
}
}
}
return cnt;
}
int main() {
vector<int> nums = {5, 2, 6, 1};
int cnt = bubbleSort(nums);
cout << cnt << endl; // 输出交换次数
return 0;
}
```