排序算法（C++）
本帖最后由 aaron0919 于 2022-8-26 19:24 编辑排序算法(下)
排序算法上
5. 快速排序 (Quicksort)
快速排序由 C.A.R.Hoare 在 1962 年提出。
基本思想：
通过一轮排序将待排记录分为两部分，其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分继续进行排序。（递归）
已达到整个序列有序
排序方法：
设要排序的数组为 a …… a ，首先任意选一个数（通常选用中间数）作为关键数据，然后将所有比它小的数放它前面，将所有比它大的数放它后面。
这叫一趟快速排序。
值得注意的是快排并不稳定，也就是输入的相同值会产生顺序变化。
一趟排序：
①设置两个变量 i,j ，排序开始时： i = 1, j = n;
②以任意元素作为关键数据（一般以中间的数），赋值给 key ，也可以是 key = a[(i + j) / 2];
③从 j 开始向前搜索，即 j-- ，找到第一个比 key 少的值 a[ j ]；
④从 i 开始向前搜索，即 i++ ，找到第一个比 key 大的值 a[ i ]；
⑤交换 a[ i ] 与 a[ j ] 的值，同时 i++, j--;
⑥重复 ③④⑤ 直到 i > j;
排序过程：
例如有 8 个数要排序：
6 10 11 8 4 1 9 7
一趟快排：
6 10 11 8 4 1 9 7 key = 8
^ ^
i j
6 10 11 8 4 1 9 7 key = 8
^ ^
i j
6 7 11 8 4 1 9 10 key = 8
^ ^
i j
6 7 11 8 4 1 9 10 key = 8
^ ^
i j
6 7 1 8 4 11 9 10 key = 8
^ ^
i j
6 7 1 8 4 11 9 10 key = 8
^^
i j
6 7 1 4 8 11 9 10 key = 8
^^
i j
6 7 1 4 8 11 9 10 key = 8
^^
j i
程序如下：
#include <iostream>
using namespace std;
const int MAX = 10001;
int a, n;
void qsort(int le, int ri)
{
int i = le, j = ri, mid = a[(i + j) / 2];
while (i <= j)
{
while (a < mid)
i++;
while (a > mid)
j--;
if (i <= j)
{
swap(a, a);
}
if (le < j)
qsort(le, j);
if (i < ri)
qsort(i, ri);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a;
}
qsort(1, n);
for (int i = 1; i <= n; i++)
{
cout << a << " ";
}
return 0;
}
快排是对冒泡排序的一种改进，快排的时间复杂度（运算量）为 O(n * log2(n)) ，速度快（排 1,000,000 才 19,931,568.569324173 次），但并不稳定。
就平均时间而言，快排是目前被认为的最好的一种内部排序方法。
但快排要一个栈空间来实现递归，若每一趟排序都将记录序列均匀分为长度相等的两个子序列，则栈最大深度为 log(n + 1) 。
{:10_256:}
页:
[1]