首页 > 代码库 > Java算法快速排序

Java算法快速排序

快速排序的原理:每次将序列以一个值为界限分成两组,在将两个序列分别以一个界限分成两组这样一直分下去。

int[] a = {11,222,44,63,84,11,24,53,123,25,98,76,34};

第一步:以34将数组a分成两组 11, 25, 24, 11              34,  63, 44, 53, 123, 222, 98, 76, 84

第二步:以11将11, 25, 24, 11分为两组  11, 11,    24, 25。以84将34,  63, 44, 53, 123, 222, 98, 76, 84分为两组34, 63, 44, 53, 76, 84         98, 123, 222。

这样一直循环下去直到不能再分。

import java.util.Arrays;


public class QuickSort {
	
	public static int partition(int[] arrays,int left,int right){
		
		int leftPart = left -1;
		int rightPart = right;
		
		//拿出数组最后一个词作为界限,数组的最后一个本身不参与比较
		int median = arrays[right];
		
		while(true){
			
			while(leftPart < rightPart && arrays[++leftPart] <= median);
			
			while(leftPart < rightPart && arrays[--rightPart] >= median);
			
			if(leftPart >= rightPart){
				break;
			}else{			
				change(arrays,leftPart,rightPart);
			}
			
		}
		
		//将界限的值也就是数组最后一个放到两组的中间
		change(arrays,leftPart,right);
		
		System.out.println(Arrays.toString(arrays));
		
		return leftPart;
	}
	
	public static void quickSort(int[] arrays,int left,int right){
		if(left >= right){
			return;
		}else{
			int partition = partition(arrays, left, right);
			
			//分别在递归排序两个组,中间的界限不参与。
			quickSort(arrays,left,partition-1);
			quickSort(arrays,partition+1,right);
		}
	}
	
	public static void change(int[] arrays,int left,int right){
		int temp = arrays[left];
		arrays[left] = arrays[right];
		arrays[right] = temp;
	}
	
	public static void main(String[] args) {
		int[] a = {11,222,44,63,84,11,24,53,123,25,98,76,34};
		quickSort(a, 0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	
}