十大排序-快速排序

 分为三种：

1、双指针-单向扫描快速排序

2、双指针-双向扫描快速排序

3、三指针-双向扫描快速排序（相等元素优化）

定主元的两种方法：

1、取第一个

2、三点中值法（推荐）

package com.xch2.DiGui;

public class Main4 {

	//单向单指针扫描分区快排法
	static void f1(int[] arr,int l,int r) {
		if(l>=r)//递归出口
			return;
		
		int left=l+1,right=r,mid=0;
		while(left<=right) {//递归体
			if(arr[left]<=arr[l])
				left++;
			else {
				mid=arr[left];
				arr[left]=arr[right];
				arr[right]=mid;
				right--;
			}
		}
		mid=arr[right];
		arr[right]=arr[l];
		arr[l]=mid;
		
		f1(arr,l,right-1);//子递归
		f1(arr,right+1,r);
	}
	
	//双向双指针扫描分区快排法
	static void f2(int[] arr,int l,int r) {
		if(l>=r)//递归出口
			return;
		
		int left=l+1,right=r,mid=0;
		while(left<=right) {//递归体
			while(left<=right&&arr[left]<=arr[l])
				left++;
			while(left<=right&&arr[right]>arr[l])
				right--;
			if(left=r)//递归出口
			return;
		
		int equ=l,left=l+1,right=r,mid=0;
		while(left<=right) {//递归体
			while(left<=right&&arr[left]<=arr[l]) {
				if(arr[left]==arr[l]&&equ==l)
					equ=left;
				if(arr[left]arr[l])
				right--;
			if(left=r)//递归出口
			return;
		
		int left=l+1,right=r,mid=0;
		
		int midsub=l+((r-l)>>1);//三点取中值
		if(arr[l]>=arr[midsub]&&arr[midsub]>=arr[r]||
			arr[l]<=arr[midsub]&&arr[midsub]<=arr[r]) {
			mid=arr[midsub];
			arr[midsub]=arr[l];//换主元
			arr[l]=mid;
		}else if(arr[midsub]>=arr[r]&&arr[r]>=arr[l]||
				arr[midsub]<=arr[r]&&arr[r]<=arr[l]){
			mid=arr[r];
			arr[r]=arr[l];
			arr[l]=mid;
		}
		
		while(left<=right) {//递归体
			if(arr[left]<=arr[l])
				left++;
			else {
				mid=arr[left];
				arr[left]=arr[right];
				arr[right]=mid;
				right--;
			}
		}
		mid=arr[right];
		arr[right]=arr[l];
		arr[l]=mid;
		
		f4(arr,l,right-1);//子递归
		f4(arr,right+1,r);
	}
	
	
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int[] arr=new int[] {0,1,9,5,4,1};
	//	f1(arr,0,5);
	//	f2(arr,0,5);
	//	f3(arr,0,5);
		f4(arr,0,5);
		for (int i : arr) {
			System.out.print(i+" ");
		}
		System.out.println();
		
		
	}

}

十大排序算法的时间复杂度：

时间复杂度效率对比：