如何编写程序计算二分插入排序中的比较次数？

要统计二分插入排序的总比较次数，核心是在二分查找的每一次元素比较操作时累加计数器。以下是修改后的完整代码，通过全局变量维护计数器，精准统计所有比较操作：

#include<iostream>
using namespace std;

// 全局计数器，统计排序过程中的总比较次数
int compare_count = 0;

int binarysearch (int a[], int sel, int high, int low){
    int mid=(high+low)/2;
    if(high<=low){
        compare_count++; // 统计sel与a[high]的比较
        if(sel>a[high]){
            return high+1;
        }
        else{
            return high;
        }
    }
    else{
        compare_count++; // 统计sel与a[mid]的相等性比较
        if(sel==a[mid]){
            return mid+1;
        }
        compare_count++; // 统计sel与a[mid]的大小比较（仅当不等时执行）
        else if(sel>a[mid]){
            return binarysearch( a,  sel,  high,  mid+1);
        }
        else{
            return binarysearch( a,  sel,  mid-1,  low);
        }
    }
}

void insertionsort(int a[], int n){
    compare_count = 0; // 排序前重置计数器，避免多次调用时累计错误
    for(int i=1; i<n; i++){
        int j=i-1;
        int sel=a[i];
        int loc=binarysearch(a,sel,j,0);
        // 插入过程仅做元素移动，无比较操作，无需统计
        while(j>=loc){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=sel;
    }
}

int main(){
    int a[]= {1,6,2,5,3,4};
    int n=sizeof(a)/sizeof(a[0]);
    insertionsort(a,n);
    
    cout<<"Sorted array is :";
    for (int i = 0; i < n; i++)
        cout<<a[i]<<"\t";
    cout<<"\nTotal comparison times: "<<compare_count<<endl;
    
    return 0;
}

关键修改说明 #

• 添加全局变量compare_count，用于累计所有比较操作的次数，且在排序前重置，保证单次排序统计准确。
• 在二分查找的每个比较节点累加计数器：
  • 当查找范围缩小到单个元素时，sel>a[high]是一次比较，对应一次计数。
  • 当查找范围大于单个元素时，先判断sel==a[mid]（一次比较）；若不成立，再判断sel>a[mid]（第二次比较），分别计数。
• 插入阶段仅做元素后移操作，无元素比较，因此无需统计。

内容的提问来源于stack exchange，提问作者HEW