我正在使用快速排序來對FFT函數中的數據進行排序,因此我可以使用四分位數範圍來查找離羣值。目前,我不確定爲什麼通過quicksort的數據沒有真正分類。下面是我使用的功能(修改爲使用雙打):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;
}
}
爲什麼不選它應該工作?
您需要直接在問題中發佈代碼,而不是通過鏈接。 – skrrgwasme
我不知道你發佈的數據甚至意味着什麼,但是如果你的排序算法輸出的是不同於輸入的數據,那麼它就會被破壞。顯然,如果我們看不到**你的**代碼,我們不能告訴你什麼是壞的。在某些網站上找到的示例代碼不計算在內。 –
有一個名爲'qsort'的庫函數,以防你錯過了它。 – user3386109