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

Closed. This question needs to be more focused。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？更新问题，使其仅通过editing this post专注于一个问题。
                        
                        2年前关闭。
                                                                                            
                
        
使用此简单示例，当前有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相比较。

有谁能够解释导致此例程如此高效的幕后情况？

最佳答案

在研究了“ 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);
}

在阅读Wikipedia页面并每次都知道发生了什么并与图流匹配时，打印出数组的状态。

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