【排序】快速排序算法

描述

对一组无序的整数用快速排序法进行排序输入第一行为数列的总个数，第二行为待排序的数列输出排序后的数列

样例输入

8
10 4 6 3 8 2 5 7

样例输出

2 3 4 5 6 7 8 10

AC代码:

#include<cstdio>
#include <iostream>
using namespace std;
void QuickSort(int a[], int left, int right)
{
  int i, j, temp, tp;
  temp = a[left];                 //暂存基准数
  i = left;                       //最左位置
  j = right;                      //最右位置

  if (left > right)                //递归结束条件
    return;

  while (i != j)                  //当i和j不重合时
  {
    while (a[j] >= temp && i < j) //从右往左寻找小于基准数的值
      j--;
    while (a[i] <= temp && i < j) //从左往右寻找大于基准数的值
      i++;
    //找到了且i<j则交换数值
    if (i < j)
    {
      tp = a[i];
      a[i] = a[j];
      a[j] = tp;
    }
  }
  //将基准数和i、j的相遇数值进行交换
  a[left] = a[i];
  a[i] = temp;

  //左边进行快速排序
  QuickSort(a, left, i - 1);
  //右边进行快速排序
  QuickSort(a, i + 1, right);
}

int main()
{
  int n = 0;
  cin >> n;
  int a[1000], i;
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  QuickSort(a, 0, n-1);
  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
  printf("\n");
}