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

　　java

　　1 void quickSort(int[] arr, int left, int right){

　　2 int p = partition(arr, left, right);

　　3 quickSort(arr, left, p-1);

　　4 quickSort(arr, p+1, right);

　　5 }

　　6 //1:

　　7 int partition(int[] arr, int left, int right){

　　8 int p = left/2 + right/2;

　　9 while(left < right){

　　10 while(left < p && arr[left] <= arr[p]){

　　11 left++;

　　12 }

　　13 while(right > p && arr[right] >= arr[p]){

　　14 right--;

　　15 }

　　16 swap(arr[left], arr[right]);

　　17 }

　　18 return p;

　　19 }

　　20