快速排序算法

快速排序算法

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法过程：
step1：指定枢纽
step2：通过一趟排序将以枢纽为中心，把待排记录分割为独立的两部分，使得左边记录的关键字小于枢纽值，右边记录的关键字大于枢纽值。
step3：对左右两部分记录序列重复上述过程，依此类推，直到子序列中只剩下一个记录或不含记录为止。

package com.quicksort.yy;
/**
 * 快速排序
 *@author yuyang_csu
 *@data 2013-4-7
 */
public class QuickSort {
	//声明待排序的数组
	private int [] arr;
	//重载构造函数
	public QuickSort(int [] arr){
		this.arr = arr;
	}
	//交换数组元素的方法
	public void swap(int i ,int j){
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	//创建设置枢纽的方法
	public int findKey(int left,int right){
		int begin = left;
		int mid = (left+right)/2;
		int end = right;
		
		if(arr[begin]>arr[mid]){
			swap(begin,mid);
		}
		if(arr[begin]>arr[end]){
			swap(begin,end);
		}
		if(arr[mid]>arr[end]){
			swap(mid,end);
		}
		return arr[mid];
	}
	
	//分解数组的方法
	public int quickSort(int left,int right){
		int tmp = findKey(left,right);
		while(left<right){
			while(arr[left]<tmp){left++;}
			while(arr[right]>tmp){right--;}
			swap(left,right);
		}
		return left;
	}
	//递归的完成分解排序的方法
	public void quick(int left,int right){
		int mid;
		if(left<right){
		    mid = quickSort(left,right);
			quick(left,mid-1);
			quick(mid+1,right);
		}
	}
	//显示数组的方法
	public void display(){
		for(int i = 0;i<arr.length;i++){
			System.out.print(arr[i]+"  ");
		}
	}
	public static void main(String[] args) {
		int[] arr = {27,38,13,49,76,97,65,69};
		QuickSort qs = new QuickSort(arr);
		qs.quick(0, arr.length-1);
		qs.display();
	}
}

快速排序时间复杂度分析：平均时间复杂度O(NlogN)，所有内部排序方法中最高好的，大多数情况下总是最好的。

快速排序稳定性分析：快速排序是一个不稳定的算法。