当前位置：首页 > article >正文

【算法】快排

article 2025/2/23 2:08:55

题目

快排

思路

如果输入为0或1直接返回；否则取一个基准值，可以取中间位置，如果输入是有序的可以避免时间过长，然后移动指针，先让i指针右移，如果小于基准值就继续右移，j指针左移同理。如果指针都停住，再看i<j，就交换。

代码

#include<iostream>
using namespace std;
void quick_sort(int q[], int l, int r)
{
	if (l >= r)
		return;
	int x = q[(l+r)/2], 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]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}
int main()
{
	int n;
	cin >> n;
	int q[n];
	for (int i = 0;i < n;i++)
	{
		cin>>q[i];
	}
	quick_sort(q, 0, n - 1);
	for (int i = 0;i < n;i++)
	{
		cout << q[i] << " ";
	}
	return 0;
}