C++ 快速排序算法

zltzlt

// 快速排序算法

#include <iostream>
using namespace std;
int a[1000] = {};

void qsort(int l, int r)
{
    int i = l, j = r, m = a[(l + r) / 2], temp;
    if (l >= r)
        return;
    do
    {
        while (a[i] < m)
            i++;
        while (a[j] > m)
            j--;
        if (i <= j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = 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[i];
    qsort(1, n);
    for (i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}

不太理解代码意思

William4869

就是取其中一个元素，正着遍历到不比这个元素小的，反着遍历到不比这个元素大的，交换，直到两边遍历相遇，
每轮都用来确定取出的元素的最终位置，并保证其左侧均比这个元素小，右边均比这个元素大

随便写一个{3,7,2,6,1,5,4}记为A[1...7]
i=1,j=7
取出6，正着比较i确定i=2时A[i]比6大，j=7时A[j]比6小，交换成{3,4,2,6,1,5,7}
继续发现i=4，A[i]不小于6，j=6,A[j]不大于6，交换成{3,4,2,5,1,6,7}
继续发现i=6，A[i]不小于6，j=5,A[j]不大于6，i>=j，两边遍历相遇，不用交换，i=6为6的最终位置，
第一轮结束后6左边的都比6小，右边的都比6大

然后对A[1...5],A[7...7]快排,循环下去就可以

大概就是这么个样子