快速排序算法基础

快速排序算法原理

简单说，快速排序算法就是在给定数组中，找到各个元素所应该在的位置，即满足在这个元素之前的元素都应小于它，在它之后的都应大于它，如：
在这里插入图片描述
其中，找到该元素所在的正确位置和将元素移动到正确位置的功能都由partition方法实现

给partition方法传入三个参数arr(待排序数组),l(待排序数组左端),r(待排序数组右端)，返回元素正确位置的索引

在这里插入图片描述

整个过程的伪代码：
在这里插入图片描述

三路快速排序算法的实现

原理：将待排序数组分为三段，>v,<v和==v，用i来遍历整个数组，具体区间、循环不变量如下图

实现三路快速排序：

package QuickSort;

import java.util.Random;

public class QuickSort2 {
	private QuickSort2() {
	}
	
	public static<E extends Comparable<E>> void sort3ways(E[] arr) {
		Random rnd=new Random();
		sort3ways(arr,0,arr.length-1,rnd);
	}
	
    private static<E extends Comparable<E>> void sort3ways(E[] arr,int l,int r,Random rnd) {
    	if(l>=r) return;
		int p=l+rnd.nextInt(r-l);
		swap(arr,l,p);
    	//[l+1,lt]<v;[lt+1,i-1]==v;[gt,r]>v
    	int i=l+1,lt=l,gt=r+1;
    	while(i<gt) {
    		if(arr[i].compareTo(arr[l])<0) {
    			lt++;
    			swap(arr,lt,i);
    			i++;
    		}
    		else if(arr[i].compareTo(arr[l])>0) {
    			gt--;
    			swap(arr,gt,i);
    		}
    		else
    			i++;
    	}
    	swap(arr,l,lt);
    	
    	sort3ways(arr,l,lt-1,rnd);
    	sort3ways(arr,gt,r,rnd);
    	
    	
	}
    
    private static <E extends Comparable<E>>  void swap(E[] arr,int i,int j) {
    	E tmp=arr[i];
    	arr[i]=arr[j];
    	arr[j]=tmp;
    }
    
    public static void main(String[] args) {
		Integer[] arr= {4,6,1,9,3,7,2,8,5};
		QuickSort2.sort3ways(arr);
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+"  ");
	}

}