欢迎光临
我们一直在努力

java中如何实现快速排序

java中如何实现快速排序插图

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

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

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

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

int Partition(int data[],int length,int start,int end)
{
	if(data == nullptr || length =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 

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

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

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 
                                                    
                                                

相关推荐: java 变量会被继承吗

java 变量会被继承吗 java中变量会被继承,前提是父类的成员变量类型是public或protected。当父类的成员变量为private时不能够被继承,但是可以通过父类提供的相应方法进行访问。 1、子类可以直接使用父类非私有成员 所以,一般在父类中声明过…

赞(0)
未经允许不得转载:爱分享 » java中如何实现快速排序

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

爱分享,生活常用知识教程百科分享、学习、交流平台

爱分享精选好货商城