快速排序

有多种做法可以写出快速排序,但思路都是一样的,通过选定一个轴值,将数组分为两部分,比轴值小的排在轴值左侧,比轴值大的排在轴值右侧,然后分别对轴值两侧的部分再进行前述操作,直到整个数组有序。

法一:选定数组首位为轴值,分别顺序从右左两侧相向扫描,从右侧扫描时,左指向为轴值,右指向比轴值小则交换左右指向值;从左侧扫描时,右指向为轴值,左指向比轴值大或等于轴值时交换左右指向值,当左右指向相等的时候结束本轮排序,并分别将轴值左右两部分进行下一轮排序,直到整个数组有序。

法二:选定数组首位为轴值,对数组除首位外的剩余数组部分分别进行右左扫描,当右指向值比轴值小、左指向值比轴值大或等于轴值时,交换左右指向值,重复进行此过程直到左右指向相同,然后对轴值和右指向值进行比较,若轴值大于右指向值则交换双方,否则右指向左移一位,原因是当退出循环时,左右指向相同,但指向的值与轴值的大小关系尚未确定,若指向值比轴值大,则可以将指向值作为轴值(此时指向值左侧都比指向值小),否则必须要将指向值与轴值交换。接着将指向左右两侧的数组部分再次进行上述过程,直到整个数组有序。

#include<iostream>
using namespace std;

//法一
template<typename T>
void quickSort(T a[], int start, int end)
{
	if (start >= end)
		return;
	int left = start;
	int right = end;
	while (left < right)
	{
		while (a[right] >= a[left] && left < right)
		{
			right--;
		}
		if (left < right)
		{
			swap(a[left], a[right]);
			left++;
		}
		while (a[right] >= a[left] && left < right)
		{
			left++;
		}
		if (left < right)
		{
			swap(a[left], a[right]);
			right--;
		}
	}
	quickSort(a, start, left - 1);
	quickSort(a, left + 1, end);
}

//法二
template<typename T>
void quick_sort(T a[], int start, int end)
{
	if (start >= end)
		return;
	int left = start + 1;
	int right = end;
	T mid = a[start];
	while (left < right)
	{
		while (a[right] >= mid && left < right)
			right--;
		while (a[left] < mid && left < right)
			left++;
		swap(a[left], a[right]);
	}
	if (a[start] > a[right])
		swap(a[start], a[right]);
	else
		right--;
	quickSort(a, start, right - 1);
	quickSort(a, right + 1, end);
}

int main()
{
	while(true)
	{
		int n;
		cin>>n;
		int* a=new int[n];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		quickSort(a,0,n-1);
		for(int i=0;i<n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

一条留言

发表评论