快速排序

#include<iostream>
using namespace std;

void quicksort(int a[],int left, int right)
{
	int temp, i, j;
	if (left > right)                //不符合排序条件,结束递归。
		return;

	temp = a[left];                  //temp储存的是基准数,以初始数组的第一个数作为基准数
	i = left;
	j = right;
	while (i != j)                   //i,j 碰头时候完成一轮
	{
		while (a[j] >= temp && i < j)//顺序很重要,要从右往左找,要求右边的比基准数大,左边的比基准数小
			j--;
		while (a[i] <= temp && i < j)
			i++;

		//交换两个数在数组中的位置
		if (i < j)                    //当i和j没有相遇时,不断交换,要求右边的比基准数大,左边的比基准数小
		{
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	a[left] = a[i];
	a[i] = temp;

	quicksort(a,left, i - 1);		   //继续处理左边的,这里是一个递归的过程
	quicksort(a,i + 1, right);         //继续处理右边的,这里是一个递归的过程
	return;
}

int main()
{
	int a[50];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	quicksort(a, 0, n-1);     //对数组进行快速排序,left是最左边的数的数组下标,right是最右边的数的数组下标
	
	
	//输出排序后的结果
	for (int i = 0; i <n; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}
/*
* 运行结果:
n:10
原数组:6 1 2 7 9 3 4 5 10 8
排序后数组:1 2 3 4 5 6 7 8 9 10
*/

全部评论

相关推荐

小博真爱学习:真心建议别找太mini的
点赞 评论 收藏
分享
零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务