快速排序法改良版

因遞廻會有爆掉堆疊的危險，所以若有可能盡可能用廻圈，但是不是可以用廻圈取決於關鍵變數，在一個廻圈後是不是須要保留其值，若不須要則可以重設其值，進行下一個廻圈的運行

以下用快速排序法做進一步的說明，先說它的改良法是青衫教的，我一直銘記在心

因快速排序法運行一個回合後會由定位點分割成左右兩部份，若要重設關鍵變數再處理左邊部份，右邊就失去關鍵變數沒法處理，反過來做亦相同，因此就讓較短的那邊用遞廻，長的那邊用廻圈

先看正常版的快速排序法長這樣：

template <typename T>
void QuickSort(vector<T> &Arr, size_t Left, size_t Right)
{
　if (Left < Right)
　{
　　size_t i = Left, j = Right + 1;
　　while (true)
　　{
　　　while (i < j && Arr[++i] < Arr[Left]);
　　　while (Left < j && Arr[--j] >= Arr[Left]);
　　　if (i >= j)
　　　　break;
　　　Swap(Arr, i, j);
　　}
　　Swap(Arr, Left, j);
　　QuickSort(Arr, Left, j);
　　QuickSort(Arr, j+1, Right);
　}
}

以下為改良版:

template <typename T>
void QuickSort2(vector<T> &Arr, size_t Left, size_t Right)
{
　while (Left < Right)
　{
　　size_t j = Right + 1;

　　{
　　　// 把 i 放這，是因不是關鍵變數，不須保存
　　　size_t i = Left;
　　　while (true)
　　　{
　　　　while (i < j && Arr[++i] < Arr[Left]);
　　　　while (Left < j && Arr[--j] >= Arr[Left]);
　　　　if (i >= j)
　　　　　break;
　　　　Swap(Arr, i, j);
　　　}
　　}

　　Swap(Arr, Left, j);

　　if (j > (Left + Right) / 2)
　　{
　　　QuickSort2(Arr, j + 1, Right);
　　　Right = j;
　　}
　　else　　{
　　　QuickSort2(Arr, Left, j);
　　　Left = j + 1;
　　}　 
　}
}

這樣可以保證遞廻的堆疊使用量不超過 log2(n)，不會爆掉堆疊，因資料量會先爆掉。須要保存的關鍵變數有 j Left Right，而參數 Arr 也會被保存，算是純函數的副作用，所以再改成以下 class 版本：

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
class QuickSort
{
　vector<T> &m_Arr;

　void Swap(size_t i, size_t j)
　{
　　T tmp = m_Arr[i];
　　m_Arr[i] = m_Arr[j];
　　m_Arr[j] = tmp;
　}

　void SortRecursive(size_t Left, size_t Right)
　{
　　while (Left < Right)
　　{
　　　size_t j = Right + 1;
　　　{
　　　　size_t i = Left;
　　　　while (true)
　　　　{
　　　　　while (i < j && m_Arr[++i] < m_Arr[Left]);
　　　　　while (Left < j && m_Arr[--j] >= m_Arr[Left]);
　　　　　if (i >= j)
　　　　　　break;
　　　　　Swap(i, j);
　　　　}
　　　}

　　　Swap(Left, j);

　　　if (j >(Left + Right) / 2)
　　　{
　　　　SortRecursive(j + 1, Right);
　　　　Right = j;
　　　}
　　　else　　　{
　　　　SortRecursive(Left, j);
　　　　Left = j + 1;
　　　}
　　}
　}

　// Constructor
　QuickSort(vector<T> &Arr)
　　:m_Arr(Arr)
　{

　}

public:

　static void Sort(vector<T> &Arr, size_t Left, size_t Right)
　{
　　QuickSort QS(Arr);
　　QS.SortRecursive(Left, Right);
　}
};

template <typename T>
void Show(vector<T> &Arr)
{
　size_t Size = Arr.size();
　size_t i = 0;
　while (i < Size)
　　cout << Arr[i++] << " ";
　cout << endl;
}

int main()
{
　vector<int> v{ 74,15,97,24,67,30,92,94,14,55,74 };

　Show(v);
　QuickSort<int>::Sort(v, 0, v.size() - 1);
　Show(v);
　QuickSort<int>::Sort(v, 0, v.size() - 1);
　Show(v);

　return 0;
}
　

以下改成非遞廻，使用堆積保存關鍵變數的方式，先保存較長的那邊並先處理短的那邊，保存的最長深度一樣以 log2(n) 計算：

template <typename T>
class QuickSort
{
　struct Rec_t
　{
　　size_t Left;
　　size_t Right;
　};

　vector<Rec_t> m_gs;
　vector<T> &m_Arr;

　void Swap(size_t i, size_t j)
　{
　　T tmp = m_Arr[i];
　　m_Arr[i] = m_Arr[j];
　　m_Arr[j] = tmp;
　}

　void SortLoop(size_t Left, size_t Right)
　{
　　m_gs.push_back({ Left,Right });
　　while (m_gs.size() > 0)
　　{
　　　Rec_t Rec = m_gs.back();
　　　m_gs.pop_back();
　　　if (Rec.Left < Rec.Right)
　　　{
　　　　size_t i = Rec.Left;
　　　　size_t j = Rec.Right + 1;
　　　　while(true)
　　　　{
　　　　　while (i < j && m_Arr[++i] < m_Arr[Rec.Left]);
　　　　　while (Rec.Left < j && m_Arr[--j] >= m_Arr[Rec.Left]);
　　　　　if (i >= j)
　　　　　　break;
　　　　　Swap(i, j);
　　　　}
　　　　Swap(Rec.Left, j);

　　　　if (j > (Rec.Left + Rec.Right) / 2)
　　　　{
　　　　　m_gs.push_back({ Rec.Left,j });
　　　　　m_gs.push_back({ j + 1, Rec.Right });
　　　　}
　　　　else　　　　{
　　　　　m_gs.push_back({ j + 1,Rec.Right });
　　　　　m_gs.push_back({ Rec.Left, j });
　　　　}
　　　}
　　}
　}

　// Constructor
　QuickSort(vector<T> &Arr)
　　:m_Arr(Arr)
　{

　}

public:

　static void Sort(vector<T> &Arr, size_t Left, size_t Right)
　{
　　QuickSort QS(Arr);
　　QS.SortLoop(Left, Right);
　}
};