您好,我编写了以下程序来输入数字数组并对其进行排序。
但是对于诸如 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 位小数的 float ,我正在尝试对数组进行排序! (我使用的算法正确吗?)
最佳答案
这是来自 Kernighan & Ritchie 的“The C Programming Language”,第 87 页的 qsort。
他们的代码最初是int v[]
我将其更改为 double v[]
因为您的数据是实数。
我不会将 long long
用于索引变量,long int
将是一个 64 位数字,允许的最大索引值为 9,223,372,036,854,775,807。如果你有一个 double 数组那么远,一个 double 占用 8 个字节,你将需要超过 6700 万太字节的 ram。
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 );
}
关于c - C 上的快速排序错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40938330/