孟习笔谈
5快速排序-最优
发布时间:
思想
-
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
-
假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先选取第一个记作为pivot或支点），定义两个指针i和j分别指向第二个和最后一个位置 ，则首先从j所指位置起向前搜索找到第一个关键字小于pivot的记录，然后从i所指位置起向后搜索，找到第一个关键字大于pivot的记录，将它们互相交换，重复这两步直至i>=j为止，最后将pivot值与j处的值交换，完成一趟快速排序。
-
将pivot左右两边部分重复调用以上方法达到整个排序完成。
-
快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
-
由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。
js
#include <iostream>
using namespace std;
int a[] = {3, 1, 7, 4, 9, 6, 2, 5, 8};
int len = sizeof(a) / sizeof(a[0]);
void showA() {
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
cout << endl;
}
void qsort(int l, int r) {
int i = l + 1;
int j = r;
int pivot = l;
do {
while (a[i] < a[pivot])
i++; // 在左半部分寻找比中间数大的数
while (a[j] > a[pivot])
j--; // 在右半部分寻找比中间数小的数
if (i < j) { // 若找到一组与排序目标不一致的数对则交换它们
swap(a[i], a[j]);
showA();
i++;
j--; // 继续找
}
} while (i < j); // 注意这里不能有等号
if (j != pivot) {
swap(a[pivot], a[j]);
showA();
}
if (j - 1 > l) {
qsort(l, j - 1); // 若未到两个数的边界，则递归搜索左右区间
}
if (i < r) {
qsort(i, r);
}
}
int main() {
qsort(0, len);
showA();
}