acwing785-quick-sort_do_while.cpp

/** acwing地址: https://www.acwing.com/problem/content/description/787/
 * 作者: 极客学长
 * 日期: 2021-08-13 11:07:23
*/
#include<iostream>
usingnamespacestd;

constint N = 1e6 + 10; // 1e6表示 10^6
int n;
int A[N];

voidquickSort(int A[], int l, int r)
{
if (l >= r) return;
int x = A[(l+r)/2]; // 分界点取中间点比较保险, 因为有时会遇到最坏的情形(极度散乱, 熵最大时)~
int i = l - 1, j = r + 1; /* 每次交换完之后, 向中间一定1位 */
// 双指针
while (i < j)
 {
do i++; while (A[i] < x);
do j--; while (A[j] > x);
if (i < j) swap(A[i], A[j]);
 }
// 递归处理左侧
quickSort(A, l, j);
// 递归处理右侧
quickSort(A, j+1, r);
}

intmain()
{
// scanf("%d", &n);
// for (int i = 0; i < n; i++)
// scanf("%d", &A[i]);
 n = 5;
int T[] = {10, 7, 6, 2, 4}; 
copy(T, T + n, A); // n = len(T) = 5

quickSort(A, 0, n - 1); // 用具体的 l 和 r 值调用 quickSort(A, l, r);

for (int i = 0; i < n; i++)
printf("%d ", A[i]);

return0;
}