zltzlt 发表于 2020-2-6 19:40:48

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:}

William4869 发表于 2020-2-7 10:57:20

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

随便写一个{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]
查看完整版本: C++ 快速排序算法