快速排序比较与交换计数 升序降序场景结果异常排查

你的代码存在3个明确的逻辑错误，直接导致了所有观测到的异常现象： #

核心bug说明 #

1. 比较计数位置完全错误，统计值严重失真 #

你将comp++写在了两个分区while循环的外部，这意味着无论while循环内部执行了多少次元素比较，每次进入循环只会给比较计数加1，完全无法统计真实比较次数。
这个bug直接对应你看到的升序场景比较次数异常：

• 固定选择区间第一个元素作为pivot时，升序数组的左指针i会从区间起点一直移动到区间终点，过程中执行(区间长度-1)次比较，但你只给comp加1
• 右指针j会从区间终点一直移动到区间起点，过程中执行(区间长度-1)次比较，你又只给comp加1
• 每层递归固定贡献2次比较计数，长度为n的数组总共递归n-1层，总比较次数就是2*(n-1)，和你测试得到的n=100得198、n=200得398的结果完全吻合，和最坏情况O(n²)的理论值偏差极大。

2. 基准值归位的交换未纳入统计 #

分区逻辑结束后，你手动写了三行代码交换pivot位置和j位置的元素，没有调用你实现的带计数功能的swap1函数，这部分交换完全没有被计入swap统计。
这就是有序场景下交换次数始终为0的直接原因：

• 升序场景下，分区过程中i最终会走到区间终点、j最终会走到区间起点，永远不满足i<j的交换条件，循环内的swap1从来不会被触发；最后pivot归位是和自身位置交换，你没走swap1，所以计数为0
• 降序场景下，分区过程中i和j最终会在区间终点相遇，同样不触发循环内的swap1；最后pivot归位是和区间终点元素交换，你没走swap1，所以计数也为0

3. 计数错误放大了逻辑巧合，导致升/降序结果完全一致 #

在上述两个计数bug的影响下，升序和降序场景的递归路径虽然不同，但每层递归都固定贡献2次比较、0次统计到的交换，最终就出现了两个场景计数完全相同的反常现象。
另外你的quicksort函数参数写为int number[25]属于不规范写法，虽然C语言中数组参数会退化为指针不会直接引发运行错误，但当处理长度超过25的数组时存在可读性和兼容性隐患，应当修正为int number[]。 #

修正后的代码参考 #

修正计数逻辑、参数写法、交换统计后的快排函数如下：

// 修正错误的数组参数声明
void quicksort(int number[],int first,int last){
   int i, j, pivot;

   if(first<last){
      pivot=first;
      i=first;
      j=last;

      while(i<j){
         // 比较计数移入循环内，每次元素比较都计数
         while(i<last && number[i]<=number[pivot]){
            comp++;
            i++;
         }
         comp++; // 补记触发i停止的最后一次比较
         while(number[j]>number[pivot]){
            comp++;
            j--;
         }
         comp++; // 补记触发j停止的最后一次比较
         if(i<j){
            swap1(&number[i], &number[j]);
         }
      }
      // 基准值归位的交换调用swap1，纳入交换计数
      swap1(&number[pivot], &number[j]);
      quicksort(number,first,j-1);
      quicksort(number,j+1,last);
   }
}

修正后预期结果 #

• 固定选择首元素为pivot的前提下，升序、降序数组都是快排的最坏输入，比较次数为O(n²)量级：n=100时比较次数约为4950次，n=1000时比较次数约为499500次，符合理论预期
• 降序场景的交换次数会明显高于升序场景，不会再出现两者计数完全一致的问题
• 有序场景下的交换次数会被正确统计，不再恒定为0

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