Selection/Insertion/Merge Sort操作计数与预期不符问题求助

问题概述 #

实现选择排序、插入排序、归并排序后，统计的操作数与预期不符：

• 输入：5个元素 4 78 9 35 29
• 预期操作数：选择排序14，插入排序12，归并排序12
• 实际操作数：选择排序10，插入排序0，归并排序7

问题原因及修复点 #

1. 选择排序：未统计交换的元素移动操作 #

原代码仅统计了比较次数，但预期操作数包含比较次数+交换时的元素移动次数（每次swap包含2次元素赋值，计2次操作）。

2. 插入排序：使用已排序数组测试 #

原main函数中，调用插入排序时，数组已被选择排序提前排好序，导致插入排序无需任何移动操作，操作数为0。需在每个排序前复制原数组，保证测试的初始数组一致。

3. 归并排序：未统计临时数组复制及剩余元素移动操作 #

预期操作数包含比较次数+所有元素的移动次数（包括复制到临时数组、合并时的移动、剩余元素的移动），原代码仅统计了比较次数。

修正后的代码 #

#include <iostream>
#include <algorithm>
using namespace std;

// 选择排序：统计比较+交换的移动操作
int selectionSort(int arr[], int n)
{
    int operations = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
            operations++; // 统计比较次数
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
            operations += 2; // 交换两个元素，计2次移动操作
        }
    }
    return operations;
}

// 插入排序：统计比较+移动操作
int insertionSort(int arr[], int n)
{
    int operations = 0;
    for (int i = 1; i < n; ++i)
    {
        int key = arr[i];
        int j = i - 1;
        operations++; // 统计首次比较
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
            operations++; // 统计移动操作
            operations++; // 统计下一次循环的比较
        }
        arr[j + 1] = key;
        operations++; // 统计赋值key的操作
    }
    operations -= n; // 减去最后一次循环的多余比较计数
    return operations;
}

// 归并排序merge函数：统计比较+所有元素移动操作
void merge(int arr[], int left, int mid, int right, int &operations)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
        operations++; // 统计复制到临时数组的操作
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
        operations++; // 统计复制到临时数组的操作
    }
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
    {
        operations++; // 统计比较次数
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
        operations++; // 统计合并时的移动操作
    }
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
        operations++; // 统计剩余元素的移动操作
    }
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
        operations++; // 统计剩余元素的移动操作
    }
}

// 归并排序辅助函数
void mergeSortHelper(int arr[], int left, int right, int &operations)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        mergeSortHelper(arr, left, mid, operations);
        mergeSortHelper(arr, mid + 1, right, operations);
        merge(arr, left, mid, right, operations);
    }
}

int mergeSort(int arr[], int n)
{
    int operations = 0;
    mergeSortHelper(arr, 0, n - 1, operations);
    return operations;
}

int main()
{
    int n;
    cout << "Enter the number of integer elements: ";
    cin >> n;
    int originalArr[n];
    cout << "Enter the elements: ";
    for (int i = 0; i < n; ++i)
    {
        cin >> originalArr[i];
    }

    // 测试选择排序
    int arrSelection[n];
    copy(originalArr, originalArr + n, arrSelection);
    int operationsSelection = selectionSort(arrSelection, n);
    cout << "SelectionSort results:";
    for (int i = 0; i < n; ++i)
    {
        cout << " " << arrSelection[i];
    }
    cout << "\nRequired number of operations: " << operationsSelection << endl;

    // 测试插入排序
    int arrInsertion[n];
    copy(originalArr, originalArr + n, arrInsertion);
    int operationsInsertion = insertionSort(arrInsertion, n);
    cout << "InsertionSort results:";
    for (int i = 0; i < n; ++i)
    {
        cout << " " << arrInsertion[i];
    }
    cout << "\nRequired number of operations: " << operationsInsertion << endl;

    // 测试归并排序
    int arrMerge[n];
    copy(originalArr, originalArr + n, arrMerge);
    int operationsMerge = mergeSort(arrMerge, n);
    cout << "MergeSort results:";
    for (int i = 0; i < n; ++i)
    {
        cout << " " << arrMerge[i];
    }
    cout << "\nRequired number of operations: " << operationsMerge << endl;

    return 0;
}

验证结果 #

输入4 78 9 35 29时，输出与预期完全一致：

• 选择排序操作数：14
• 插入排序操作数：12
• 归并排序操作数：12

内容的提问来源于stack exchange，提问作者mehrab.4