Quicksort无法处理小数字？

Question

我正在使用快速排序来对FFT函数中的数据进行排序，因此我可以使用四分位数范围来查找离群值。目前，我不确定为什么通过quicksort的数据没有真正分类。下面是我使用的功能（修改为使用双打）：

void quickSort(double arr[], int left, int right) { 
    int i = left, j = right; 
    int tmp; 
    double pivot = arr[(left + right)/2]; 

    /* partition */ 
    while (i <= j) { 
     while (arr[i] < pivot) 
       i++; 
     while (arr[j] > pivot) 
       j--; 
     if (i <= j) { 
       tmp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = tmp; 
       i++; 
       j--; 
     } 
    }; 

    /* recursion */ 
    if (left < j) 
     quickSort(arr, left, j); 
    if (i < right) 
     quickSort(arr, i, right); 
    } 

我不知道如何把输出在这里，因为它是相当长的。这里是如何将所有的未排序的数据几乎是这样的：

0.01033861 0.00861337 0.00861337 -0.00326733 -0.00326733 0.00098514 0.00098514 -0.01022199 -0.01022199 -0.00303045 -0.00303045 -0.00435644 -0.00435644 -0.00217089 -0.00217089 -0.00171707 -0.00171707 -0.00073572 -0.00073572 -0.00283767 -0.00283767 0.00008432 0.00008432 -0.00288364 -0.00288364 -0.00162750 -0.00162750 -0.00222617 -0.00222617 -0.00017057 -0.00017057 0.00101272 0.00101272 0.00332283 0.00332283 -0.00115711 -0.00115711 

它似乎并不像排序是正确的，因为大部分产量由非常小的数据（0.00000000）的，其余的有斑点，看起来像这样：

0.00000000 0.00000000 -0.00002053 0.00000000 -0.00002051 -0.00002051 -0.00002050 0.00000000 -0.00002048 0.00000000 -0.00002045 -0.00002039 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00002025 0.00000000 -0.00002020 0.00000000 -0.00002019 0.00000000 0.00000000 -0.00002005 0.00000000 

这里我为了获得这项输出：

int size = sizes[i]; 
int numElements = (int)pow(2.0, ceil(log((double)size)/log(2.0))); //next power of 2 
double *X = (double *) malloc((2*numElements+1) * sizeof(double)); 
double *p = ptr[i]; //ptr[i] is a void *ptr; 

//X is filled with data 
for (j = 0; j < size; j++){ //put numbers in 
    if ((double)*(p+j) < 1000 && (double)*(p+j) > -1000) { 
     X[2*j+1] = (double)*(p+j); 
    } else{ 
     X[2*j+1] = 0.0; 
    } 
    X[2*j+2] = 0.0; 
} 
for (j = size; j < numElements; j++){ //fill the rest with zeros 
    X[2*j+1] = 0.0; 
    X[2*j+1] = 0.0; 
} 

printf("\nStarting FFT()..."); fflush(stdout); 
four1(X, numElements, 1, pData); 
for (j = 0; j < numElements; j++){ 
     //first block of data is printed 
     fprintf(pData->pFile, "%.8f %.8f ", X[2*j+1], X[2*j+1]); 
    } 

//create a copy of the array for storage 
double *array = (double *) malloc((maxIndex-minIndex+1) * sizeof(double)); 
for (j = 0; j < maxIndex-minIndex+1; j++){ 
    array[j] = X[2*(j+minIndex)+1]; 
} 

quickSort(X, 1, 2*(long)size+2); //don't need to sort everything 

//print out the output of the quicksort 
for (j = 1; j < 2*(long)size+2; j++){ 
    //second block of data is printed 
    fprintf(pData->pFile2, "%.8f ", X[j]); 
} 

//use interquartile range 
double q1, q3, iqr; 
q1 = X[(long)size/2+1]; //size is even 
q3 = X[3*(long)size/2+1]; 
iqr = q3-q1; 
printf("q1: %.5f, q3: %.5f, iqr: %.5f", q1, q3, iqr); 

//check if any of the elements in array[] are outliers 
for (j = 0; j < maxIndex-minIndex+1; j++) { 
     if (array[j] > 3*(q3+iqr)/2){ 
      printf(" A match!"); fflush(stdout); 
      break; 
     } 
    } 

为什么不选它应该工作？

Answer 1

其实我找不到在你的程序的具体问题，但如果你想有一个程序元素的阵列上执行快速排序，这是它：

#include<stdio.h> 

void quicksort(int [10],int,int); 

int main(){ 
    int x[20],size,i; 

    printf("Enter size of the array: "); 
    scanf("%d",&size); 

    printf("Enter %d elements: ",size); 
    for(i=0;i<size;i++) 
    scanf("%d",&x[i]); 

    quicksort(x,0,size-1); 

    printf("Sorted elements: "); 
    for(i=0;i<size;i++) 
    printf(" %d",x[i]); 

    return 0; 
} 

void quicksort(int x[10],int first,int last){ 
    int pivot,j,temp,i; 

    if(first<last){ 
     pivot=first; 
     i=first; 
     j=last; 

     while(i<j){ 
      while(x[i]<=x[pivot]&&i<last) 
       i++; 
      while(x[j]>x[pivot]) 
       j--; 
      if(i<j){ 
       temp=x[i]; 
        x[i]=x[j]; 
        x[j]=temp; 
      } 
     } 

     temp=x[pivot]; 
     x[pivot]=x[j]; 
     x[j]=temp; 
     quicksort(x,first,j-1); 
     quicksort(x,j+1,last); 

    } 
} 

您可以检查它的wiki page。

它具有所有不同类型快速排序的算法。为了给更多的清晰度，SE动画：

Answer 2

对于C该指数通常去从0到n-1，那就是你必须快速排序功能编码方式。呼叫应该是：

quickSort(X, 0, 2*(long)size + 1); /* changed the +2 to +1 */ 

我不知道代表什么规模或为什么你乘以2，通常大小进行排序的元素数量在这种情况下调用：

quickSort(X, 0, size - 1);