這個算法沒有 swap 過程差凹,直接把個別元素復制到了另一個位置少漆,但是到最后依舊可以排序尸疆,而且沒有丟失任何一個元素椿猎。我花了一上午模擬過程才明白了這個算法:
void QuickSort(vector<int>& v, int low, int high) {
if (low >= high) // 結(jié)束標志
return;
int first = low; // 低位下標
int last = high; // 高位下標
int key = v[first]; // 設(shè)第一個為基準
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; //但是到這里的時候,數(shù)組里的元素只是換了位置寿弱,而沒有丟失掉任何一個
// 前半遞歸
QuickSort(v, low, first - 1);
// 后半遞歸
QuickSort(v, first + 1, high);
}