快速排序（Quicksort） 是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快速排序算法描述: 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 从数列中挑出一个元素，称为 “基准”（pivot）； 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 快速排序示意图： 快速排序动态示意图： 动图里，每趟都把待排序的数组的末尾元素作为基数来排序。后面的代码实现我们是以中间的数来作为基数。 代码实现：
import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int [] arr = {-9,78,0,23,-567,70,-20,30,9}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int [] arr,int left,int right){ int l = left; int r = right; //pivot 取中轴值 int pivot = arr[(right + left)/2]; int temp = 0; while(l < r){ //在pivot的左边一直找，找到大于等于pivot值，才退出 while(arr[l] < pivot){ l += 1; } //在pivot的右边一直找，找到小于等于pivot值，才退出 while(arr[r] > pivot){ r -= 1; } //如果l>=r，说明已经按照上面的排好了 if (l >= r){ break; } //交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后，发现arr[l] == pivot，那么r--，前移 if(arr[l] == pivot){ r -= 1; } //如果交换完后，发现arr[r] == pivot，那么l++，后移 if(arr[r] == pivot){ l += 1; } } //如果l==r，那么必须l++，r--，否则会出现栈溢出。 if(l == r){ l += 1; r -= 1; } //向左递归 if(left < r){ quickSort(arr,left,r); } //向右递归 if(right > l){ quickSort(arr,l,right); } } }