用c++对上一段代码进行改进实现 ,比较上述排序算法中关键字的比较次数和移动次数(其 中关键字交换计为 3 次移动)。
时间: 2023-12-20 07:04:51 浏览: 24
好的,以下是用 C++ 对排序算法进行改进实现的代码,同时记录关键字比较次数和移动次数:
```c++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
int i, j, temp;
int cmpCount = 0; // 记录关键字的比较次数
int moveCount = 0; // 记录关键字的移动次数
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
cmpCount++; // 每进行一次比较,计数器加1
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
moveCount += 3; // 每进行一次交换,计数器加3
}
}
}
cout << "Bubble Sort:" << endl;
cout << "Comparison Count: " << cmpCount << endl;
cout << "Move Count: " << moveCount << endl;
}
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
int cmpCount = 0; // 记录关键字的比较次数
int moveCount = 0; // 记录关键字的移动次数
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
cmpCount++; // 每进行一次比较,计数器加1
if (arr[j] < arr[min_idx])
min_idx = j;
}
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
moveCount += 3; // 每进行一次交换,计数器加3
}
cout << "Selection Sort:" << endl;
cout << "Comparison Count: " << cmpCount << endl;
cout << "Move Count: " << moveCount << endl;
}
void insertionSort(int arr[], int n) {
int i, j, key;
int cmpCount = 0; // 记录关键字的比较次数
int moveCount = 0; // 记录关键字的移动次数
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
cmpCount++; // 每进行一次比较,计数器加1
arr[j + 1] = arr[j];
j--;
moveCount++; // 每进行一次移动,计数器加1
}
arr[j + 1] = key;
moveCount++; // 每进行一次移动,计数器加1
}
cout << "Insertion Sort:" << endl;
cout << "Comparison Count: " << cmpCount << endl;
cout << "Move Count: " << moveCount << endl;
}
int main() {
int arr[] = { 64, 25, 12, 22, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
selectionSort(arr, n);
insertionSort(arr, n);
return 0;
}
```
此处我们使用了 `cout` 语句来输出计数器的值,可以更方便地查看排序算法的性能。