快速排序

/*
* 快速排序学习：

今天我学习了快速排序，顾名思义，快速排序的速度是很快的，平均复杂度是nlogn，我也不知道是怎么算出来的，反正 T(n) = 2T(n/2) + o(n) 这样怎么怎么推到就成了nLogn了，呵呵，有空去学习一下。希望会的人可以教我，我数学太烂了。废话少说，记录一下快速排序的思路：

1.分治的思想，把数组分成两份，两份分成4分，这样分到足够小，就能很好排序咯，然后把他们合起来，排序完成。

2.该分治思想和合并排序思想一样，但是处理上更搞一筹，他是把小的和大的分成两份，这样在最后合并的时候，就不会像合并排序那样还要检查，因为本来就是左边比右边小，所以可以做到原地排序（就是不用申请多余的空间）。

3.如何做好把小和大的分开时关键，我们做的就是以一个数位基准，然后找到这个数的位置。把比他小的放在他的左边，比他大的放在他的右边，这样不就分开了嘛。

4.具体怎么分时一个最关键的地方，本来想用图说明一下，但是自己不会画：作罢，试着语言整理一下，呵呵：

例如，开始把最后一个作为标准，用一个循环j = nBegin j < nEnd一一比较，这样就能判断到底谁比他大，谁比他小咯。

注意：为了能清楚知道区域，所以要用一个变量i来保存它的标志，i的左边是比他小的，i的右边是比他大的。有了这个标志我们就好处理了。比较就好处理咯。

遇到小的，要把他方在i的左边，所以我们把他和i+1的元素交换，因为i+1得元素是大于x的，交换之后i+1就小于x了，这样我们把i也加1，不就有保证了i的左边都比x小，右边都比x大了嘛。呵呵。

遇到大的，不用管他。I也不用变。

比较完了，这时情况就是i的左边都比x小，i的右边都比x大,x在最后面。怎么处理呢？还不简单，有重复一下i + 1与 x交换，这样处理之后,i + 1就是保存的x值，i + 1的右边都比x大，i+1的左边都比x小，哈哈，i+1就是分割点咯。搞定。。

找出分割点后还不分而治之。。分而治之的时候发现分割点是排好的，只需排序nBegin - 分割点-1， 分割点+1 - nEnd 就可以咯。

最后还是截张《算法导论》书中的图：

(quickSortImage.jpg)
*/


/*
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

快速排序是不稳定的，最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
*/
public static void quickSort(int[] array,int low,int height){
if(low>=height)return;
int i = partition(array,low,height);
quickSort(array,low,i-1);
quickSort(array,i+1,height);
}

public static int partition(int[] array,int low,int height){
int i = low;
int key = array[height];
int temp;
for(int j=low+1;j<height;j++){
if(array[j]<key){
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
}
}
array[height]=array[i];
array[i] = key;
return i;
}