c - qsort - 幕后发生了什么？

Question

使用这个简单的示例，当前有 6 个数字排序为 5,4,3,2,1,0，将排序为:0,1,2,3,4,5

#include <stdio.h>
#include <stdlib.h>

int values[] = {5,4,3,2,1,0};
int sizeOfArray = sizeof(values)/sizeof(int);

int cmpfunc (const void * a, const void * b) 
{
    printf("Comparing %d and %d \n",*(int*)a, *(int*)b);
   return ( *(int*)a - *(int*)b );
}

int main () {
   int n;
   printf("Size of Array : %d\n", sizeOfArray);
   printf("Before sorting the list is: \n");
   for( n = 0 ; n < sizeOfArray; n++ ) {
      printf("%d ", values[n]);
   }

   printf("\n");

   qsort(values, sizeOfArray, sizeof(int), cmpfunc);

   printf("\nAfter sorting the list is: \n");
   for( n = 0 ; n < sizeOfArray; n++ ) {   
      printf("%d ", values[n]);
   }

   return(0);
}

cmpfunc 函数中添加了一个 printf 命令，用于显示调用每个函数时所比较的数字。

Size of Array : 6
Before sorting the list is: 
5 4 3 2 1 0 
Comparing 4 and 3 
Comparing 5 and 3 
Comparing 5 and 4 
Comparing 1 and 0 
Comparing 2 and 0 
Comparing 2 and 1 
Comparing 3 and 0 
Comparing 3 and 1 
Comparing 3 and 2 

After sorting the list is: 
0 1 2 3 4 5 

请注意，应用程序仅调用 cmpfunc 9 次。 我本以为这个函数会被多次调用。 另请注意，5 或 4 永远不会与 2 或 1 进行比较。

有谁能解释一下幕后发生了什么，导致这个例程如此高效吗？

Answer 1

研究了“QuckSort”之后，它变得更有意义了。 我修改了示例以添加额外的打印语句。

#include <stdio.h>
#include <stdlib.h>

int values[] = { 5,4,3,2,1,0};
int sizeOfArray = sizeof(values)/sizeof(int);

int cmpfunc (const void * a, const void * b) 
{
    int n = 0;
   printf("Comparing %d and %d  current array looks like this :" ,*(int*)a, *(int*)b);
   for( n = 0 ; n < sizeOfArray; n++ ) 
   {
      printf("%d ", values[n]);
   }
   printf("\n");
   return ( *(int*)a - *(int*)b );
}

int main () {
   int n;
   printf("Size of Array : %d\n", sizeOfArray);
   printf("Before sorting the list is: \n");
   for( n = 0 ; n < sizeOfArray; n++ ) 
   {
      printf("%d ", values[n]);
   }

   printf("\n");

   qsort(values, sizeOfArray, sizeof(int), cmpfunc);

   printf("\nAfter sorting the list is: \n");
   for( n = 0 ; n < sizeOfArray; n++ ) {   
      printf("%d ", values[n]);
   }

   return(0);
}

在阅读了维基百科页面并每次打印出数组的状态之后，它就明白了正在发生的事情并且它与图表流程相匹配。

Size of Array : 6
Before sorting the list is: 
5 4 3 2 1 0 
Comparing 4 and 3  current array looks like this :5 4 3 2 1 0 
Comparing 5 and 3  current array looks like this :5 3 4 2 1 0 
Comparing 5 and 4  current array looks like this :5 3 4 2 1 0 
Comparing 1 and 0  current array looks like this :3 4 5 2 1 0 
Comparing 2 and 0  current array looks like this :3 4 5 2 0 1 
Comparing 2 and 1  current array looks like this :3 4 5 2 0 1 
Comparing 3 and 0  current array looks like this :3 4 5 0 1 2 
Comparing 3 and 1  current array looks like this :3 4 5 0 1 2 
Comparing 3 and 2  current array looks like this :3 4 5 0 1 2 

After sorting the list is: 
0 1 2 3 4 5