在C中使用快速排序實現的段錯誤

Question

我正在爲C中的快速排序算法調試我的代碼。它在編譯時運行時出現「分段錯誤」，但編譯失敗。

任何人都可以幫助我調試它，並給我我的代碼的工作版本？我知道互聯網上有現有的和工作的。但我真正想要的是找到我自己的代碼的錯誤。

void myQuickSort(int list[],int head, int tail) 
{ 
    int m = head; 
    int n = tail; 

    int key = list[m]; 
    ++head; 
    while(head < tail) 
    { 
     while(list[head] < key) 
     { 
      ++head; 
     } 
     while(list[tail] >= key) 
     { 
      --tail; 
     } 
     //swamp two elements, to divide the array to two groups 
     int temp = list[head]; 
     list[head] = list[tail]; 
     list[tail] = temp; 

    } 

    //get the pivot element in dividing position 
    int temp = list[m]; 
    list[m] = list[head]; 
    list[head] = temp; 

    myQuickSort(list, m, head-1); 
    myQuickSort(list, head+1, n); 
} 

Answer 1

您的函數將永遠不會退出。

它將繼續調用自己，直到調用堆棧已滿並導致堆棧溢出異常。

編譯器應該產生這樣的警告：

warning C4717: 'myQuickSort' : recursive on all control paths, function will cause runtime stack overflow 

你需要退出條件，沿着線的東西：

void myQuickSort(int list[],int head, int tail) 
{ 
    //exit condition, or else the function will always call itself 
    if (head >= tail) 
     return; 

    /** 
    ... 
    */ 

    myQuickSort(list, m, head-1); 
    myQuickSort(list, head+1, n); 
} 

此外，還要確保你調用函數，如：

int num[5] = {1,4,2,3,5}; 
myQuickSort(num,0,4); 

最終參數必須小於數組的長度，因爲C++數組s是基於0的。

你還需要在你的while循環，一個額外的檢查：

while(head < tail && list[head] < key) // see if head reached the end 
{ 
    ++head; 
} 
while(head < tail && list[tail] >= key) 
{ 
    --tail; 
} 

，否則你可能會傳遞數組的結尾。

Answer 2

只要快速查看它，我會看到許多可能會出現段錯誤的地方。例如，在這裏：

while(list[head] < key) 
    { 
     ++head; 
    } 

想象一下，一個列表，其中key是，一個偶然的機會，在列表中的最大元素。然後這個循環將運行直到head超過數組的末尾，此時可以在任何時候發生段錯誤。同樣，以下循環可能會導致tail從陣列的開始處移開。

Answer 3

除了由Luchian診斷保證堆棧溢出，你需要檢查你沒有在內部循環跑出陣列：

while(head <= tail && list[head] < key) 
while(head <= tail && list[tail] >= key)