C++ 快速排序算法
// 快速排序算法#include <iostream>
using namespace std;
int a = {};
void qsort(int l, int r)
{
int i = l, j = r, m = a[(l + r) / 2], temp;
if (l >= r)
return;
do
{
while (a < m)
i++;
while (a > m)
j--;
if (i <= j)
{
temp = a;
a = a;
a = temp;
i++;
j--;
}
} while (i <= j);
if (l < j)
qsort(l, j);
if (i < r)
qsort(i, r);
}
int main()
{
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a;
qsort(1, n);
for (i = 1; i <= n; i++)
cout << a << " ";
return 0;
}
不太理解代码意思{:5_104:} 就是取其中一个元素,正着遍历到不比这个元素小的,反着遍历到不比这个元素大的,交换,直到两边遍历相遇,
每轮都用来确定取出的元素的最终位置,并保证其左侧均比这个元素小,右边均比这个元素大
随便写一个{3,7,2,6,1,5,4}记为A
i=1,j=7
取出6,正着比较i确定i=2时A比6大,j=7时A比6小,交换成{3,4,2,6,1,5,7}
继续发现i=4,A不小于6,j=6,A不大于6,交换成{3,4,2,5,1,6,7}
继续发现i=6,A不小于6,j=5,A不大于6,i>=j,两边遍历相遇,不用交换,i=6为6的最终位置,
第一轮结束后6左边的都比6小,右边的都比6大
然后对A,A快排,循环下去就可以
大概就是这么个样子
页:
[1]