快速排序java实现

 性能介绍： 快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序 相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序，不能把数据分成大小相当的两份，很明显，排序的过程就成了一个歪脖子树，树的深度为n，那时间复杂度就成了O(n^2)。尽管如此，需要排序的情况几乎都是乱序的，自然性能就保证了。据书上的测试图来看，在数据量小于20的时候，插入排序具有最好的性能。当大于20时，快速排序具有最好的性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度都为nlog2(n)。

 

程序实现思路：

1、确定一个基点，通过一次排序将比它大的放在其右边，小的放在左边；

2、调整key值，到相应位置；

3、然后对前后两部分，分别进行递归，直到都有序为止。

 

注意点：

1、进行排序时，需先从后往前，再从前往后。

2、每一小次的交换是，两个数之间的交换，最后再调整key值的位置。