如何用非遞歸、不用棧的方法，實現原位（in-place）的快速排序？

01-23

在《演算法分析與設計》一書當中，對快速排序有這樣的描述（170頁）：

注意：為了使快速排序成為真正的原位排序，必須用非遞歸方式實現它（且不用棧）。這樣實現的關鍵細節是需要一種原位方式，確定「當前」子序列左、右邊界的界限。……

def inplace_qsort(input_list): begin = 0 end = len(input_list) end_l = len(input_list) while end &< end_l or end - begin &> 1: print input_list, "begin=", begin, "end=", end if end - begin &> 1: min_i = begin for i in range(begin + 1, end): if input_list[i] &< input_list[min_i]: min_i = i input_list[min_i], input_list[end - 1] = input_list[end - 1], input_list[min_i] print "Move minimal: ", input_list sep = input_list[begin] begin_p = begin end_p = end - 2 while begin_p &<= end_p: while input_list[begin_p] &< sep: begin_p += 1 while input_list[end_p] &> sep: end_p -= 1 print "Swap",begin_p, end_p if begin_p &> end_p: break if input_list[end_p] == input_list[begin_p]: begin_p += 1 end_p -= 1 else: input_list[begin_p], input_list[end_p] = input_list[end_p], input_list[begin_p] print input_list if input_list[end_p + 1] != sep: for i in range(end_p + 2, end - 1): if input_list[i] == sep: input_list[i], input_list[end_p + 1] = input_list[end_p + 1], input_list[i] print "Keep sep=",sep,input_list break if input_list[end - 1] == sep: # Do not need to sort left part print "Skip left" begin = begin_p else: end = end_p + 1 else: # Done, find the right border sep = input_list[end] print "sep=", sep for i in range(end + 1, end_l): if input_list[i] &< sep: break else: break move_item = input_list[i] print "i=",i,"move_item=",move_item for j in range(i - 1, -1, -1): if input_list[j] &<= move_item: input_list[j+1] = move_item break else: input_list[j+1] = input_list[j] else: input_list[0] = move_item begin = end + 2 end = i + 1 print "Final result:", input_list

自行按照需要去掉print或者換成print()

原理是在劃分前預先將最小的數交換到最右。劃分後，保證區間右側的第一個數恰好等於劃分標準，如果之前交換的數與劃分標準一樣大，則說明左側區間全部都是這個數值，不需要再對左側進行遞歸，直接進入右側；否則對左側進行遞歸。在需要回溯的時候，從當前區間右端點下一個數是原先的劃分標準，向右找，一定存在唯一一個比劃分標準小的數，這個數就是上一層右端點的標記，把它用插入排序插回到前面。由於增加的過程都不超過O(n)，因此總的時間複雜度仍然是O(nlogn)。

調試了整整一個小時……

快速排序寫到今天還是覺得是一種玄學，比如下面這段代碼

while begin_p &<= end_p: while input_list[begin_p] &< sep: begin_p += 1 while input_list[end_p] &> sep: end_p -= 1 print "Swap",begin_p, end_p if begin_p &> end_p: break if input_list[end_p] == input_list[begin_p]: begin_p += 1 end_p -= 1 else: input_list[begin_p], input_list[end_p] = input_list[end_p],

每次我想要稍微改動一點點的時候就會出詭異的錯誤，比如把某個&>換成&>=之類的。

原本的快排是自頂向下構築的，遞歸原則是

[X&其實inplace是個很簡單的要求，至少大多數我看過的數據結構教材里都是inplace的偽代碼。

既不用棧也不遞歸的快排自然是自底向上構築的。由於X是區間內連續序列，自底向上就要想辦法取這個範圍，即把原有的序列分段。無優化的快排自底向上的話，最底層肯定是兩個相鄰元素的比較，但照理需要記錄分段信息，這樣空間就不是常數了；如果要常數，就要求分段信息可以根據某參數推算。

總的來說，關鍵點還挺多。蜜月旅行中，稍後有空了寫個代碼貼上，算是先mark了。

基本思路就是利用數組中的數值本身來記錄子問題，而不是用棧，可以用額外O(N)的掃描來確定子問題邊界

不過這樣做也只是理論上探索一下O(1)空間的可能性吧，畢竟快排記錄幾個位置需要的空間不多，我弄個大小64的棧，每個棧元素是64bit的start和end，總夠了吧，也沒耗多少空間

感謝 @靈劍的答案給了我靈感，以下是我的寫法。

大體思路是修改Partition方法將原本樞數的調整放到方法結束後去做。

這樣因為數組右側第一個大於當前樞數的位置就應該是未劃分的子數組的邊界。

然後繼續進行Partition調整。

這種寫法照比遞歸的寫法多出一個向右尋找邊界的過程，該過程的平均時間複雜度為 $Theta (nlgn)$ 。

private static void QSort(int[] array) { int leftLow, leftHeight, rightLow, rightHeight; int tempLow, tempHeight, key, temp; leftLow = 0; leftHeight = leftLow; rightLow = array.Length - 1; rightHeight = array.Length - 1; tempLow = -1; tempHeight = -1; key = -1;


            while (rightHeight &> leftLow)

            {
                while (leftHeight + 1 &< rightLow)
                {

                    key = leftHeight;
                    tempLow = leftHeight + 1;
                    tempHeight = rightLow;

                    while (tempLow &< tempHeight)
                    {
                        while (tempLow &< rightHeight  array[tempLow] &< array[key])
                        {
                            tempLow++;
                        }
                        while (leftHeight &< tempHeight  array[key] &<= array[tempHeight])
                        {
                            tempHeight--;
                        }
                        if (leftLow &< tempHeight  tempLow &< rightHeight  tempLow &< tempHeight)
                        {
                            temp = array[tempLow];
                            array[tempLow] = array[tempHeight];
                            array[tempHeight] = temp;
                        }
                    }
                    if (rightHeight == tempHeight  leftHeight ==leftLow )
                    {
                        temp = array[rightLow];
                        array[rightLow] = array[leftHeight];
                        array[leftHeight] = temp;
                        rightHeight--;
                        rightLow--;
                        continue;
                    }
                    rightLow = tempHeight;
                    if (key == tempHeight)
                    {
                        break;
                    }
                    else if (key &< tempHeight  tempLow &> tempHeight)

                    {

                        leftHeight++;

                    }
                }
                if (leftHeight != leftLow)

                {

                    if (leftHeight &< rightLow)
                    {
                        if (array[leftHeight] &< array[rightLow])
                        {
                            temp = leftHeight;
                        }
                        else
                        {
                            temp = rightLow;
                            rightLow++;
                            leftHeight++;
                        }
                    }
                    else
                    {
                        temp = rightLow;
                        rightLow++;
                    }

                    key = array[temp];
                    for (int i = temp; i &> leftLow; i--)

                    {

                        array[i] = array[i - 1];

                    }

                    array[leftLow] = key;

                    leftLow++;
                    while (rightLow &<= rightHeight  array[rightLow] &< array[leftHeight])
                    {
                        rightLow++;
                    }
                    if (rightLow &> rightHeight)

                    {

                        rightLow--;

                    }
                }
                else

                {

                    rightLow = rightHeight;

                    leftLow++;

                    leftHeight++;

                }

} if (array[rightHeight] &< array[rightHeight - 1]) { temp = array[rightHeight]; array[rightHeight] = array[rightHeight - 1]; array[rightHeight - 1] = temp; } }

這顯然應該是不對的：「為了使快速排序成為真正的原位排序，必須用非遞歸方式實現它（且不用棧）」，但也有可能是翻譯的問題。in place說的只是直接去改那個數組，並沒有什麼其它額外的要求。

有個問題，麻煩了，這本書，題主還能找到賣的嗎？我想買一本，我之前找過沒找到。

#include & #define MAX 128


void QuickSort(int array[], unsigned length) {
    unsigned low = 0, stack[MAX], ptr = 0;

while (1){ for (; low+1 &< length; length++) { if (ptr == MAX) length = stack[ptr = 0]; int pivot = array[low]; stack[ptr++] = length; for (unsigned high = low-1; ; ) { while (array[++high] &< pivot); while (pivot &< array[--length]); if (high &>= length) break; int temp = array[high]; array[high] = array[length]; array[length] = temp; } } if (ptr == 0) break; low = length; length = stack[--ptr]; } }