QuickSort explanation and make code by myself

介绍

快速排序是基础算法里面非常简单暴力的排序算法，正如他的名字一样，排序效率高，在最差的情况下，时间复杂度为O(n2),虽然其他排序也有很多在O(n2)，但是遇到数据量庞大的时候选择快速排序是没错的。正好今天学到快速排序，让我想到了学习排序算法的第一课—冒泡排序，而快速排序就是冒泡排序的改进版。

上图中可以看出快速排序的平均情况比冒泡排序的平均情况要好。

图解

通过图解可以很好的了解到快速排序的原理。（这只是我个人理解，如果有问题请指出）

代码

public class QuickSort {
	
	public static void main(String[] args){
		int [] quickData = {7, 3, 9, 5, 4, 1, 2, 6, 8, 11, 55, 88, 54, 32, 45, 18, 111, 214, 784, 21, 456, 120, 666};
		
		quickData = quickSort(quickData, 0, quickData.length - 1);
		
		for(int i = 0; i < quickData.length; i++){
			System.out.println(quickData[i]);
		}
	}
	
	private static int[] quickSort(int[] transBefore, int low, int height){
		if(low > height){
			return null;
		}
		
		int pivotIndex = getMiddle(transBefore, low, height);
		
//		System.out.println("中间数" + transBefore[pivotIndex]);
		
		quickSort(transBefore, low, pivotIndex - 1);
		quickSort(transBefore, pivotIndex + 1, height);
		
		return transBefore;
	}
	
	private static int getMiddle(int[] transBefore, int low, int height){
		int pivot = transBefore[low];
		boolean direction = true;//从右到左
		int temp;
		while(low < height){
			if(direction){
				if(pivot > transBefore[height]){
					
					transBefore[low] = transBefore[height];
					direction = false;
					low++;
				}
				else{
					height--;
				}
			}else{
				if(pivot < transBefore[low]){
					
					transBefore[height] = transBefore[low];
					direction = true;
					height--;
				}else{
					low++;
				}
			}
		}
		transBefore[height] = pivot;
		return height; //low
	}
}

总结

快速排序采用分治法的思想来实现快速排序的，分治法顾名思义就是分而治之，将复杂的问题分为若干个简单的问题，从而逐个击破，达到理想的效果。好了，总的来说，快速排序的关键点是需要知道基准的作用、移动方向的转变条件以及递归的使用。