sorting/快速排列

//快速排序
/* 
   时间复杂度为 O(n log n)~O(n2)， 平均时间复杂度为 O(n log n)
  基本思想：通过一趟排序将待排数据分隔为独立的两部分，其中一部分比指定数据小，
  一部分比之大,然后分别对这两部分继续进行排序，以达到整个序列有序。
  具体步骤：
  1、确定分界点：一般为（左边界、中间值、右边界、随机）， 为 x.
  2、调整区间：第一个区间里的数都小于等于 x ，第二个区间数都大于等于 x 
  3、递归处理左右两端。
*/ 
#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
	if(l >= r)
	return;
	
	int x = q[l], i = l - 1, j = r + 1;
	while(i < j)
	{
		do i ++; while (q[i] < x);
		do j ++; while (q[j] > x);
		if (i < j)
		swap(q[i], q[j]);//交换两个数
		/*
		{
		 	int t = q[i];
			 q[i] = q[j];
			 q[j] = t;
		}
		*/
	}
	
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
	scanf("%d", &q[i]);
	
	quick_sort(q, 0, n - 1);
	
	for(int i = 0; i < n; i ++)
	printf("%d ", &q[i]);
	
	return 0;
}
/*
  适用场景： 
  快速排序是目前基于比较的内部排序中被认为是最好的方法，
  当待排序的关键字是随机分布时，快速排序的平均时间最短
*/