if (low >= high) // 结束标志

return;

int first = low; // 低位下标

int last = high; // 高位下标

int key = v[first]; // 设第一个为基准

while (first < last)

{

// 将比第一个小的移到前面

while (first < last && v[last] >= key)

last--;

if (first < last)

v[first++] = v[last];

// 将比第一个大的移到后面

while (first < last && v[first] <= key)

first++;

if (first < last)

v[last--] = v[first];

}

// 基准置位

v[first] = key;

// 前半递归

QuickSort(v, low, first - 1);

// 后半递归

QuickSort(v, first + 1, high);

if (start >= end)

return;

T mid = arr[end];

int left = start, right = end - 1;

while (left < right) {

while (arr[left] < mid && left < right)

left++;

while (arr[right] >= mid && left < right)

right--;

std::swap(arr[left], arr[right]);

}

if (arr[left] >= arr[end])

std::swap(arr[left], arr[end]);

else

left++;

quick_sort_recursive(arr, start, left - 1);

quick_sort_recursive(arr, left + 1, end);

int start, end;

Range(int s = 0, int e = 0) {

start = s, end = e;

}

if (len <= 0)

return; // 避免len等於負值時宣告堆疊陣列當機

// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素

Range r[len];

int p = 0;

r[p++] = Range(0, len - 1);

while (p) {

Range range = r[--p];

if (range.start >= range.end)

continue;

T mid = arr[range.end];

int left = range.start, right = range.end - 1;

while (left < right) {

while (arr[left] < mid && left < right) left++;

while (arr[right] >= mid && left < right) right--;

std::swap(arr[left], arr[right]);

}

if (arr[left] >= arr[range.end])

std::swap(arr[left], arr[range.end]);

else

left++;

r[p++] = Range(range.start, left - 1);

r[p++] = Range(left + 1, range.end);

}

}