快速排序不能处理小数字？

Question

我正在使用快速排序对来自 FFT 函数的数据进行排序，因此我可以找到使用四分位数范围来查找异常值。目前，我不确定为什么经过快速排序的数据没有真正排序。这是我使用的函数（修改为使用双精度）：

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。

它有所有不同类型的快速排序的算法。为了更清楚起见，请使用动画：

Answer 2

c 的索引通常从 0 到 n-1，这就是您对快速排序函数进行编码的方式。调用应该是：

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

我不确定大小代表什么或为什么要乘以 2，通常大小是要排序的元素数，在这种情况下调用是：

    quickSort(X, 0, size - 1);

快速排序不能处理小数字？

Quicksort cannot handle small numbers?

c

sorting

quicksort