tags: DSA C++ Sort
思路
分治法
主要分成下面三个步骤:
- 选定基准值(默认是数组首元素), 这里称为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) {
/*i: the number of left side of x */
int mid = l + (r - l) / 2; // 选pivot
int pivot = arr[mid], i = l - 1;
for (int j = l; j <= r; ++j) {
if (j == mid) continue;
if (arr[j] <= pivot) swap(arr[++i], arr[j]);
}
swap(arr[++i], arr[mid]);
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插入的位置
}
代码(迭代法)
用数组模拟栈, 放入左右边界(实际的递归变量), 参考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));
}
}
ref
- Iterative Quick Sort - GeeksforGeeks; ↩︎
- 迭代的快速排序(Iterative Quick Sort)_K.Sun的博客-迭代版快速排序; ↩︎