java中如何实现快速排序

下面由java入门学习栏目为大家介绍java中如何实现快速排序,希望这种算法排序可以帮助到大家!实现快速排序的关键在于以某一个数为中点将数组中的数字分为两部分,比选择的数字小的移动到数组的左边,比选择的数字大的移动到数组的右边。

java中如何实现快速排序

下面由java入门学习栏目为大家介绍java中如何实现快速排序,希望这种算法排序可以帮助到大家!

快速排序的时间复杂度并不固定,如果在最坏情况下(在一个原本逆向排序的数列中选择第一个元素为基准元素)速度比较慢,达到 O(n^2)(和选择排序一个效率),但是如果在比较理想的情况下时间复杂度 O(nlogn)。

实现快速排序的关键在于先在数组中选择一个数字,接下来把数组中的数字分为两部分,比选择的数字小的数字移动到数组的左边,比选择的数字大的数字移动到数组的右边。这体现了分治法的思想。

下面我们来实现这个函数:

int Partition(int data[],int length,int start,int end)
{
	if(data == nullptr || length <= 0 || start < 0 || end >=length)
		throw new std::exception("Invalid Parameters");
	int index = RandomInRange(start,end);
	Swap(&data[index],&data[end]);
	int small = start - 1;
	for(index = start; index < end; index++)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				Swap(&data[index],&data[small]);
		}
	}
	++small;
	Swap(&data[small],&data[end]);
	return small;
}
int RandomInRange(int min, int max)
{
	int random = rand()%(max - min +1) +min;
	return random;
}
int Swap(int *num1, int *num2)
{
	int temp = *num1;
	*num1 = num2;
	*num2 = temp;
}
只听到从山间传来架构君的声音:
肃肃宵征,抱衾与裯。有谁来对上联或下联?

上面代码中函数RandomInRange用来生成一个在start和end之间的随机数,函数Swap用来交换两个数字。

下面我们用递归来实现快速排序的代码:

此代码由Java架构师必看网-架构君整理
void QuickSort(int data[], int length, int start, int end) { if(start == end) return; int index = Partition(data, length, start, end); if(index > start) QuickSort(data, length, start, index -1); if(index < end) QuickSort(data, length, index + 1, end); }

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/36151
0

发表评论