计算数组中冒泡排序交换的次数而不进行冒泡排序

Question

你好，我正在尝试计算大小为 N 的数组中的冒泡排序交换次数，但我想在不进行冒泡排序的情况下进行计算，我听说过合并排序，并且有人已经告诉我它是某种合并排序修改...我不想使用这个基本算法 >

void bubbleSort(int * array, int size){
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(array[j+1] < array[j]){
                int tmp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tmp;
            }   
        }   
    }   
}  

你们有人有什么想法吗？

Answer 1

您可以按照三个简单的步骤操作。制作输入数组的副本，然后在每次交换时增加一个计数器并返回该计数。就像是：

int bubbleSort(int * array, int size){
    std::vector<int> temp_array(array, array + size);
    int count{0};
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(temp_array[j+1] < temp_array[j]){
                int tmp = temp_array[j + 1];
                temp_array[j + 1] = temp_array[j];
                temp_array[j] = tmp;
                count++;
            }
        }
    }
    return count;
}