Java教程

算法之快速排序

本文主要是介绍算法之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序算法是分治法的一种

什么是分治法

(11条消息) 分治法的特征和步骤_我还能再写一年的博客-CSDN博客

快速排序的解法步骤

给定十个数字,2,5,1,7,10,6,9,4,3,8进行排序

第一次

一般来说,是以第一个数为基准,

25171069438

->

1
2

571069438

 以2为基准,分为两个,一个是比2小的,一个是比2大的,比2小的放在左边,比2大的放在右边

第二次

再将分下来的两个继续进行刚才的操作 

1

->不需要再进行分解了

571069438

 ->以5为基准,将比5小的放在左边,将比5大的放在右边

43
5
710698

第三次

左边部分

43

 以4为基准,比4小的放在左边,比4大的放在右边

3
4

右边部分:

710698

 以7为基准,比7小的在左边,比7大的在右边

6
7
1098

第四次

左边部分,不需要再进行上述步骤

右边部分:

1098

以10为基准,比10小的放左边,比10大的放右边

98
10

第5次

左边部分:

98

以9为基准,比9小的放在左边,比9大的放在右边

8
9

右边部分:

不需要执行了

第6次

8

不需要执行了

代码执行:

分解

	public static void Qu(int a[] , int s, int t){
		if(s<t) {
			int i=Hua(a,s,t);
			Qu(a,s,i-1);
			Qu(a,i+1,t);
		}
	}

排序

public static int Hua(int a[] , int s, int t) {
		/**
		 * s为0,也就是第一个值的数组下标
		 * t为a.length-1,为数组的个数-1
		 */
		int i=s,j=t;
		int tmp=a[s];//基准
		while(i!=j) {
			while(j>i&&a[j]>=tmp) 
			j--;
		        
				a[i]=a[j];
			
			while(i<j&&a[i]<=tmp) {
				i++;
			
				a[j]=a[i]; }
			
			
		}
		a[i]=tmp;
		return i;
	}

完整代码

public static void disp(int a[],int n) {		
		for(int i=0;i<=n;i++) {
			System.out.print(a[i]+"\t");
		}
		System.out.print("\n");
	}
	public static int Hua(int a[] , int s, int t) {
		/**
		 * s为0,也就是第一个值的数组下标
		 * t为a.length-1,为数组的个数-1
		 */
		int i=s,j=t;
		int tmp=a[s];//基准
		while(i!=j) {
			while(j>i&&a[j]>=tmp) 
			j--;
		        
				a[i]=a[j];
			
			while(i<j&&a[i]<=tmp) {
				i++;
			
				a[j]=a[i]; }
			
			
		}
		a[i]=tmp;
		return i;
	}
	public static void Qu(int a[] , int s, int t){
		if(s<t) {
			int i=Hua(a,s,t);
			Qu(a,s,i-1);
			Qu(a,i+1,t);
		}
	}
	public static void main(String[] args) {
		//快速排序
		/*Scanner s= new Scanner(System.in);
		int n;
		n=s.nextInt();
		int [] arr =new int [n];
		
		for(int i=0;i<=n-1;i++) {
			arr[i]=s.nextInt();
		}*/
		int n=10;
		int [] arr ={2,5,1,7,10,6,9,4,3,8};
		disp(arr,n-1);
		Qu(arr,0,n-1);
		disp(arr,n-1);
	}

这篇关于算法之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!