思路
分治法
主要分成下面三个步骤:
- 选定基准值(默认是数组首元素), 这里称为pivot
- 找到基准值待放置的位置(排序之后的位置), 将大于基准值的元素放在基准值后面, 小于的放在前面
- 递归上述过程.
代码(递归)
下面这种方法是算法导论给出的, 先写子数组处理函数, 再给出递归过程. pivot取最右边元素:
int Partition(vector<int> &arr, int l, int r) {
/*i: the number of left side of x */
int x = arr[r], i = l - 1;
for (int j = l; j < r; ++j)
if (arr[j] <= x) swap(arr[++i], arr[j]);
swap(arr[++i], arr[r]);
return i; // 返回pivot插入的位置
}
// 递归实现快速排序算法
void QuickSort1(vector<int> &arr, int l, int r) {
if (l >= r) return;
int m = Partition(arr, l, r);
QuickSort1(arr, l, m - 1);
QuickSort1(arr, m + 1, r);
}
我改成了pivot取中间元素的情况:
int Partition(vector<int> &arr, int l, int r) { // pivot=arr[mid]
/*i: the number of left side of x */
int mid = l + (r - l) / 2; // 选pivot
swap(arr[mid], arr[r]); // 这样就不需要判断mid位置了
int pivot = arr[r], i = l;
for (int j = l; j < r; ++j)
if (arr[j] <= pivot) swap(arr[i++], arr[j]);
swap(arr[r], arr[i]);
return i; // 返回pivot插入的位置
}
// 函数主体不变
以及经典的取首元素方法:
int Partition(vector<int> &arr, int l, int r) {
/*i: the number of left side of x */
int x = arr[l], i = l;
for (int j = l + 1; j <= r; ++j)
if (arr[j] <= x) swap(arr[++i], arr[j]);
swap(arr[i], arr[l]);
return i; // 返回pivot插入的位置
}
上面的代码可能不太好记, 这里我给出一种模板, 就是说针对数组中选取任意一个位置作为pivot, 都可以用下面的代码来完成partition.
int Partition(vector<int> &arr, int l, int r) {
swap(arr[x], arr[r]); // 这里x 可以取l到r任意一个元素
int i = l;
for (int j{l}; j < r; ++j)
if (arr[j] <= arr[r]) swap(arr[i++], arr[j]);
swap(arr[r], arr[i]);
return i; // 返回pivot插入的位置
}
例如:
int PartitionX(vector<int> &arr, int l, int r) {
swap(arr[(r + l) / 2], arr[r]); //
int i = l;
for (int j{l}; j < r; ++j)
if (arr[j] <= arr[r]) swap(arr[i++], arr[j]);
swap(arr[r], arr[i]);
return i; // 返回pivot插入的位置
}
代码(迭代法)
用数组模拟栈, 放入左右边界(实际的递归变量), 参考1,2.
/* arr --> Array to be sorted,
l --> Starting index,
r --> Ending index */
void QuickSort2(vector<int> &arr, int l, int r) {
int stack[r - l + 1];
// 栈顶指针(索引)
int top = -1;
stack[++top] = l;
stack[++top] = r;
// 栈空, 说明每一个子区间都被处理完了
while (top >= 0) {
r = stack[top--];
l = stack[top--];
int p = Partition(arr, l, r);
// pivot 左边元素入栈
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}
// pivot 右边元素入栈
if (p + 1 < r) {
stack[++top] = p + 1;
stack[++top] = r;
}
}
}
相当经典, 下面我用STL给出了一种比较简洁的写法:
void QuickSort(vector<int> &arr) {
int l{}, r = arr.size() - 1;
stack<pair<int, int>> st;
st.push(make_pair(l, r));
while (!st.empty()) {
tie(l, r) = st.top();
st.pop();
int p = Partition(arr, l, r);
if (p - 1 > l) st.push(make_pair(l, p - 1));
if (p + 1 < r) st.push(make_pair(p + 1, r));
}
}