我在 C 中實作了快速排序，它運行得非常好。然后我開始玩樞軸元素，現在我陷入了一個奇怪的境地。我所實作的有時運行良好，但在其他所有時間都沒有運行（顯示沒有輸出），我無法確定為什么會發生這種情況。這是我的代碼。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void displayArray(int arr[], size_t size)
{
for(int i = 0; i < size; i)
printf("%d\t",arr[i]);
printf("\n");
}
unsigned int getNMinNMax(int arr[], unsigned int lb, unsigned int ub)
{
unsigned int a = rand()%(ub-lb 1) lb, b =rand()%(ub-lb 1) lb,c = rand()%(ub-lb 1) lb;
// printf("%d %d %d \n", a,b,c);
// getchar();
// inefficient comparisons incoming, brace yourselves
if(arr[a] >= arr[b] && arr[a] < arr[c]) return a;
else if(arr[b] >= arr[a] && arr[b] < arr[c]) return b;
else return c;
}
unsigned int partition(int arr[], unsigned int lb, unsigned int ub)
{
// pivot selection mania(select necessarily from array elements)****{needs more testing}
// 1)middle element
// swap(&arr[lb (ub - lb)/2], &arr[lb]);
// 2)neither smallest nor largest
// swap(&arr[getNMinNMax(arr,lb,ub)], &arr[lb]); (problem here)
// 3)random
// swap(&arr[rand()%(ub-lb 1) lb], &arr[lb]); (problem here)
// 4)1st element(no optimisation)
int pivot = arr[lb];
unsigned int down = lb 1, up = ub;
while(down <= up)
{
while(arr[down] <= pivot)
down ;
while(arr[up] > pivot)
up--;
if(down < up)
swap(&arr[down], &arr[up]);
}
arr[lb] = arr[up];
arr[up] = pivot;
return up;
}
void quickSort(int arr[], unsigned int lb, unsigned int ub)
{
while(lb < ub)
{
unsigned int pivot = partition(arr, lb, ub);
if (pivot - lb < ub - pivot)
{
quickSort(arr, lb, pivot - 1);
lb = pivot 1;
}
else
{
quickSort(arr, pivot 1, ub);
ub = pivot - 1;
}
}
}
int main()
{
int arr[] = {1,2,3,5,0,-1,-2,-3};
srand(time(NULL));
quickSort(arr, 0, sizeof(arr)/sizeof(int)-1);
displayArray(arr,sizeof(arr)/sizeof(int));
return 0;
}
我已經評論了哪些行導致輸出消失。我很確定我的實作在其他情況下也有效，因為我沒有遇到輸出消失，但請隨時指出任何其他錯誤。我使用的編譯器是 Onlinegdb C 編譯器（即 gcc afaik）。
PS：我已經添加了完整的代碼，因為當我弄亂了我的磁區函式時，我發現我的顯示函式無法正常作業很奇怪。我也嘗試過除錯，但沒有運氣。
uj5u.com熱心網友回復：
問題是由以下原因引起的：
while(lb < ub)
通過樞軸調整，ub可以達到-1，但型別ub是無符號整數，所以ub看起來像一個很大的正數，while回圈將繼續。
將此行更改為：
while( (int)lb < (int)ub )
允許程式完成并顯示已排序的陣列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/463566.html
上一篇：獲取具有多個股票類別的公司串列
下一篇：按物件的變數對物件的向量進行排序