以第一個元素爲樞紐實現快速排序分區算法

我想實現以第一個元素爲樞軸的快速排序分區算法，我研究了最後一個元素作爲樞軸的Quicksort。有人可以告訴我在下面的僞代碼中我錯了嗎？以第一個元素爲樞紐實現快速排序分區算法

/* Taking first element of array as pivot and movig all elements 
smaller than pivot left to pivot and greater tto its right */ 
// L is leftmost index, R is rightmost index 

Partition(A[],L,R) 
{ 
    pivot = A[L] 
    i = L-1 
    for (j =L to R) 
    { 
     // If current element is smaller than or equal to pivot 

     if (A[j] <= pivot) 
     { 
      i++; // increment index of smaller element 
      swap A[i] and A[j] 
     } 
    } 
    swap A[i + 1] and A[L]) 
    return (i + 1) 
}

來源

2017-05-31 Aegon The Unworthy

quicksort是用C++編寫的。 Qsort是C中的快速排序。 –

你確定*你錯了嗎？什麼讓你有那個想法？你有沒有嘗試向你的[橡皮鴨]解釋僞代碼（https://en.wikipedia.org/wiki/Rubber_duck_debugging）？ –

如果你知道pivot元素的最後一個元素的正確代碼，那麼你可以做的一件事就是交換第一個元素和最後一個元素，並用最後一個元素運行代碼。在這方面需要很少的努力。 –

經過一些反覆試驗和大量的思考，我發現我的錯誤。這是正確的算法。

Partition(A[],L,R) 
{ 
    pivot = A[L] 
    i = L 
    for (j =L+1 to R) 
    { 
     if (A[j] <= pivot) 
     { 
      i++; // increment index of smaller element 
      swap A[i] and A[j] 
     } 
    } 
    swap A[i] and A[L]) 
    return (i) 
}

來源

2017-05-31 14:11:36

使用此算法，數組'[3，-1,1,5,4]'將變爲'[1，-1,3,5,4]'。您需要繼續左側和右側的算法。 – Neil

這就是在Quicksort @Neil中發生的情況，但OP指定（並在問題中記錄）他正在爲分區部分單獨編寫僞代碼。 –

以第一個元素爲樞紐實現快速排序分區算法

回答

相關問題