排序-快速排序
基本思想： 将数据划分为两部分，左边的所有元素都小于右边的所有元素；然后，对左右两边进行快速排序。
划分方法： 选定一个参考点（中间元素），所有元素与之相比较，小的放左边，大的放右边。
具体步骤： 选择第一个元素作为中间元素。
(1)先保存该元素的值到其它位置，腾出其空间。
(2)从后往前搜索一个比中间数小的元素，并将其放置到前面的这个空位上。
(3)从前往后搜索一个比中间数大的元素，并将其放置到后面的这个位置上。
重复(2)，(3)，直到两边搜索的空位重合，此时将中间元素放在该空位中。
平均时间：O(nlogn)
最好情况：O(nlogn)
最坏情况：O(n2)
辅助空间：O(logn)
稳定性：不稳定
适用场景：n比较大时
代码实现：
1 public static void quickSort(int[] list){ 2 quickSort(list, 0, list.length-1); 3 } 4 5 private static void quickSort(int []list,int left,int right){ 6 int cutPoint = 0; 7 if(left < right){ 8 cutPoint = partion(list,left,right); 9 quickSort(list, left, cutPoint-1); 10 quickSort(list, cutPoint+1, right); 11 } 12 } 13 14 private static int partion(int []list, int left, int right) { 15 int cutPointValue = list[0]; 16 while(left < right){ 17 while(left < right && cutPointValue < list[right])right--; 18 if(left < right) 19 list[left] = list[right]; 20 21 while(left < right && cutPointValue > list[left])left++; 22 if(left < right) 23 list[right] = list[left]; 24 } 25 list[left] = cutPointValue; 26 return left; 27 }
原文：http://www.cnblogs.com/yang--yang/p/4855478.html