C上的快速排序错误
嗨,我编了下面的程序来输入一个数组的数组并对其进行排序。C上的快速排序错误
但我仍然得到错误的答案,如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位小数! (现在用我正确的算法?)
下面是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);
}
您遇到的错误实际上可能不是错误,而是对浮点类型的误解。这是非常不准确的,特别是对于十进制浮点文字,因为它们实际上是以二进制形式存储的。下面的代码(使用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的错误。
总之,只需再次检查可疑的浮点值。
所以我的fDig工作不正常,它应该返回一个浮点数的小数位数变量有,但它显然不是!我该如何修复它? –
@Ben FM它不能使用双类型来完成。如果原始数据是可访问的,则字符串类型(char [],但std :: string是首选)是更好的选择。此外,可以使用stoflib中声明的atof根据需要将字符串转换为double。 –
什么是输入数据? –
有什么问题? (即什么是输入和输出) –
这是排序错误,或'fDig'和输出格式?尝试对实际输入的最大位数进行硬编码,然后查看会发生什么情况。 – Useless