algorithm - 为什么 Radix sort 比 C 中的 Quick sort 有更多的指令？

Question

我在C中设置了2个排序算法函数，基数排序和快速排序
但是当我用 gdb 检查这些函数时，事实证明快速排序的指令数量少于基数排序。而且感觉更快...
据我所知，基数排序是最快的排序算法。
以下是我从 wiki 中提取的排序代码。
1.快速排序

void q_sort(int numbers[], int left, int right)
 {
   if(left == right) return;
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];

   while (left < right)
   {
     while ((numbers[right] >= pivot) && (left < right))
       right--;

     if (left != right)
     {
       numbers[left] = numbers[right];
       left++;
     }

     while ((numbers[left] <= pivot) && (left < right))
       left++;

     if (left != right)
     {
       numbers[right] = numbers[left];
       right--;
     }
   }

   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;

   if (left < pivot)
     q_sort(numbers, left, pivot-1);
   if (right > pivot)
     q_sort(numbers, pivot+1, right);
 }

2.基数排序

/**
 * @data  array
 * @size  the number of array
 * @p  cipher of the biggest number
 * @k  notation( in case of decimal, it is 10)

 */
void rxSort(int *data, int size, int p, int k) {
     int *counts,
     *temp;
     int index, pval, i, j, n;
     if ( (counts = (int*) malloc(k * sizeof(int))) == NULL )
          return;
     if ( (temp = (int*) malloc(size * sizeof(int))) == NULL )
          return;
     for (n=0; n<p; n++) {
          for (i=0; i<k; i++)
               counts[i] = 0; // initialize

          // n:0 => 1,  1 => 10, 2 => 100
          pval = (int)pow((double)k, (double)n);
          for (j=0; j<size; j++) {
               // if the number is  253
               // n:0 => 3,  1 => 5, 2 => 2
               index = (int)(data[j] / pval) % k;
               counts[index] = counts[index] + 1;
          }
          for (i=1; i<k; i++) {
               counts[i] = counts[i] + counts[i-1];
          }
          for (j=size-1; j>=0; j--) {
               index = (int)(data[j] / pval) % k;
               temp[counts[index] -1] = data[j];
               counts[index] = counts[index] - 1;
          }

          memcpy(data, temp, size * sizeof(int));
     }
}

有一些限制如下
1.数组的大小要设置为256。
2.数字范围为0~64。
3. 对不同的数组进行四次运算。

我测试的时候把数组的大小设置为50
然后，指令数
基数:15030
快速:7484
快速获胜...T_T.. 对 Radix 感到非常难过...快速排序真的更快吗？

Answer 1

快速排序通常是对数组进行排序时的最佳选择，尤其是当您没有关于数字范围的信息并且数组非常大时。这是因为 qsort 的预期时间复杂度与其输入的大小乘以该大小的对数 O(nlogn) 成正比，这是基于比较的算法所能达到的最佳效果。此外，它有一个小的隐藏常数因子，并且它排序就位。基数排序不是比较排序，需要知道输入的大小(n)和每个数字的平均位数(k)，因为它的时间复杂度与k*n成正比。

在你的情况下，你有一个相当小的数组来做测试，所以两种算法的行为之间的任何可观察到的差异在渐近上是无关紧要的。如前所述，快速排序之所以获胜，是因为它在 O(nlogn) 中隐藏了一个小的常数运算因子。如果你尝试在一个小数组上运行插入排序和合并排序，尽管在最坏的情况下 InsSort 有 O(n^2) 和 MergeSort O(nlogn)，插入排序很可能会更快，因为同样理由如上。但请放心，如果您在 10^8 个数字的数组上尝试它们，结果会发生很大变化。还要记住，没有<​​strong>最好的排序算法这样的东西，您每次只需要看看哪种算法更适合您的问题性质。 :)