C上的快速排序错误

Question

嗨，我编了下面的程序来输入一个数组的数组并对其进行排序。

但我仍然得到错误的答案，如1.3333331数字！

什么问题？

#include <stdio.h> 

void quicksort(double array[], long long left, long long right); 

long long partition(double array[], long long left, long long right); 

int fDig(double x); 

int main(void) { 
    long long quantity = 0LL, counter = 0LL; 
    int dig = 0; 
    scanf("%lli", &quantity); 

    double beard[quantity]; 

    for(counter = 0LL; counter < quantity; counter++) { 
     scanf("%lf", &beard[counter]); 
    } 

    quicksort(beard, 0LL, quantity - 1LL); 

    for(counter = 0LL; counter < quantity; counter++) { 
     dig = fDig(beard[counter]); 
     printf("%.*lf", dig, beard[counter]); 
     if(counter == quantity - 1LL) { 
      break; 
     } 

     printf(" "); 
    } 

    return 0; 
} 

int fDig(double x) { 
    int result = 0; 
    while(x != floor(x)) { 
     x *= 10; 
     result++; 
    } 

    return result; 
} 

/* Quick sort recursive function */ 

void quicksort(double array[], long long left, long long right){ 
    if (left < right) { 
     long long middle = partition(array, left, right); 
     quicksort(array, left, middle - 1LL); 
     quicksort(array, middle + 1LL, right); 
    } 
} 

/* Partition : 
    Modifies the array : 
    SMALLER , PIVOT , GREATER 
    Returns the index for pivot because pivot is placed in the final position 
*/ 

long long partition(double array[], long long left, long long right) { 
    long long middle; 

    double x = array[left]; 
    long long l = left; 
    long long r = right; 

    while(l < r) { 
     while((array[l] <= x) && (l < right)) { 
      l++; 
     } 

     while((array[r] > x) && (r >= left)) { 
      r--; 
     } 

     if(l < r) {  
      double temp = array[l]; 
      array[l] = array[r]; 
      array[r] = temp; 
     } 
    } 

    middle = r; 

    double temp = array[left]; 
    array[left] = array[middle] ; 
    array[middle] = temp; 

    return middle ; 
} 

我想对数组进行排序，因为数组元素是浮点数最多8位小数！ （现在用我正确的算法？）

Answer 1

下面是Kernighan的&里奇从“C程序设计语言”的快速排序，第87页

他们的代码原本是int v[] 我改成了double v[]因为您的数据是实数。 我不会使用long long作为索引变量，long int将是一个64位数字，允许最大索引值为9,223,372,036,854,775,807。如果你有一堆双打，那么双倍占用8个字节，你将需要超过6700万兆字节的内存。

void swap (double v[], long int i, long int j) 
{ 
    double temp; 

    temp = v[i]; 
    v[i] = v[j]; 
    v[j] = temp; 
} 


void qsort (double v[], long int left, long int right) 
{ 
    long int i; 
    long int last; 

    if (left >= right) 
     return; /* do nothing if array contains fewer than 2 elements */ 

    swap(v, left, (left+right)/2); /* move partition element */ 
    last = left; 
    for (i = left + 1; i <= right; i++) 
    { 
     if (v[i] < v[left]) 
     swap(v, ++last, i); 
    } 
    swap(v, left, last); 
    qsort(v, left, last - 1); 
    qsort(v, last + 1, right); 
} 

Answer 2

您遇到的错误实际上可能不是错误，而是对浮点类型的误解。这是非常不准确的，特别是对于十进制浮点文字，因为它们实际上是以二进制形式存储的。下面的代码（使用fDig）可以是用于这种不精确性一个提示：

#include <stdio.h> 
#include <math.h> 

int fDig(double x) { 
    int result = 0; 
    while (x != floor(x)) { 
     x *= 10; 
     result++; 
    } 

    return result; 
} 

int main() { 
    double x = 0.3333331; 

    int dig = fDig(x); 
    printf("%.7f\n", x); 
    printf("%.*f\n", dig, x); 
    printf("%.20f\n", x); 

    return 0; 
} 

上述代码在我的gcc（MinGW的GCC 4.8.1）与-std = C99的输出如下所示：

0.3333331 
0.33333309999999999 
0.33333309999999999329 

我无法重现文字1.3333331的错误。

总之，只需再次检查可疑的浮点值。