2.7 快速排序
毫无疑问,快速排序(quick sort
)是最流行的排序算法,因为有充足的理由,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN) 级。(这只是对内部排序或者说随机存储器内的排序而言,对于在磁盘文件中的数据进行的排序,其他的排序算法可能更好。)
快速排序算法本质上通过把一个数组划分(patition
)为两个子数组,然后递归地调用自身,将子数组划分为更细的子数组,为每一个子数组进行快速排序来实现的。
在前面讲解的归并排序(merge sort)中,实际上也是对数组进行进行拆分,然后进行排序,快速排序和归并排序都是分治法的典型应用。 不过不同的是,二者的划分标准不同:
在归并排序中,是将数组不断的划分成两个大小相同的子数组,实际上就是取数组下标的中间值进行拆分,例如{3,1,9,0,4,7,2,6,5,8}划分后的结果为{3,1,9,0,4 }和{7,2,6,5,8}
而在快速排序中,数组的划分是基于某一个基准值(pivot
)的,拆分时,将所有大于基准值的元素放在一组,将所有小于基准值的元素放在另一组。 比如基准值为5,那么{3,1,9,0,4,7,2,6,5,8}划分后的结果为{3, 1, 2, 0, 4}和{7, 9, 6, 5, 8}
需要注意的是,归并排序由于是根据数组下标中间值划分的,因此切分后的两个子数组的长度最多相差1,但是对于快速排序,由于是根据基准值来进行划分,如果基准值选择的不好,例如基准值等于1,那么{3,1,9,0,4,7,2,6,5,8}划分后的结果为{1}和{3,9,0,4,7,2,6,5,8 },因此在快速排序中,我们需要对划分操作有特别的关注。
划分
划分是快速排序的根本机制,依赖于基准值。划分数据就是把数据分成两组,所有大于基准值的数据在一组,所有小于基准值的在一组。比如基准值为5,那么{3,1,9,0,4,7,2,6,5,8}划分后的结果为{3, 1, 2, 0, 4 }和{7, 9, 6, 5, 8}。
理论上,可以使用任何值作为基准值,这个值可以包含在要排序的数组中,也可以是其他任意数字,基准值选择的有一定的技巧,如果选择的基准值比数组中任意一个元素都要大或者小的话,那么就相当于没有进行划分,最简单的基准值的选择方法,就是从数组中随机选择一个元素,当做基准值。
划分算法由两个指针来完成,这两个指针分别指向数组的开始和结尾,左指针left pointer
向右移动而右指针right pointer
向左移动。
停止和交换
当left pointer 遇到比基准值小的值时它继续右移,因为这个数据项的位置已经在数组的小于基准值得一边了。当遇到基准值大的数时,它就停下来。
类似的,当right pointer 遇到比特定值大的数时就继续左移,当遇到比基准值小的数时就停下来。当都停下来的时候left pointer 和right pointer 都指向了在数组错误一方位置上的数据项,所以交换这两个数据项。
交换之后,继续移动两个指针,然后再在合适的实际停止、交换数据,不断重复此过程。
当right pointer和left pointer相遇时,划分完成。
划分过程图解
在第一次划分时,left pointer需要在一个比自己大的位置上停下来,9是第一个数字,所以此时left pointer指向9,right pointer需要在第一个比自己小的位置上停下来,所以right pointer指向2,此时交换两个指针位置指向的数字,即9和2的位置。
第二次划分时,left pointer继续右移,遇到7,比自己大,停下来;此时right pointer右移,也到了7的位置,两个指针相遇,划分完成。 此时在相遇数组下标左边的元素,都比基准值5小,而相遇下标右边的元素都大于等于基准值5,划分因此完成。
划分代码实现:
public class Patition { /** * 返回划分后,左指针和右指针相遇的下标 */ public static int partition(int[] arr,int start,int end){ int pivot=getPivot(arr,start,end); int left_pointer=start-1; int right_pointer=end+1; while (true){ while (arr[++left_pointer]<pivot);//left_pointer当遇到比基准值大的元素,停下来 while (arr[--right_pointer]>pivot);//right_pointer当遇到比基准值小的元素,停下来 if(left_pointer>=right_pointer){break;} swap(arr,left_pointer,right_pointer); } return right_pointer; } /** * 获得基准值 */ private static int getPivot(int[] arr, int start, int end) { return 5; } //交换数组中两个元素的位置 private static void swap(int[] arr, int i, int j) { int temp= arr[i]; arr[i] =arr[j]; arr[j]=temp; } public static void main(String[] args) { int[] arr={3,1,9,0,4,7,2,6,5,8}; System.out.println("划分前数组:"+ Arrays.toString(arr)); int partitionIndex = partition(arr, 0,arr.length-1); System.out.println("划分后左半部分:"+ Arrays.toString(Arrays.copyOfRange(arr,0,partitionIndex+1))); System.out.println("划分后右半部分:"+ Arrays.toString(Arrays.copyOfRange(arr,partitionIndex+1,arr.length))); } }
运行程序,输出
划分前数组:[3, 1, 9, 0, 4, 7, 2, 6, 5, 8] 划分后左半部分:[3, 1, 2, 0, 4] 划分后右半部分:[7, 9, 6, 5, 8] |
基准值对划分结果的影响
在上例中,getPivot方法返回一个固定值5,作为基准值,基准值的选择对划分的结果有着指直接的影响,会导致划分后的子数组不平均,例如,现在我们将基准值改为数组中的第一个元素:
/** * 获得基准值 */ private static int getPivot(int[] arr, int start, int end) { return arr[start]; }
此时运行程序,输出
划分前数组:[3, 1, 9, 0, 4, 7, 2, 6, 5, 8] 划分后左半部分:[2, 1, 0] 划分后右半部分:[9, 4, 7, 3, 6, 5, 8] |
快速排序算法
基本的快速排序很简单,就是对一个数组进行不断的进行划分操作,当划分操作完成时,排序也就完成了,听起来不可思议,但是事实就是这样。
每一次划分(partition)操作,在快速排序中称之为一趟,我们可以通过将上面划分后的两个子数组,再分别进行一趟快速排序。
每个子数组在继续进行划分的时候,需要重新选择基准值,也就是每一趟都需要重新选择一个基准值,为了方便,我们通常选择划分后的子数组的第一个元素作为基准值,因此左半部分的基准值是3,右半部分的基准值是7(感兴趣的读者,可以尝试继续用画图的方式进行逐步推导)。
当划分后的子数组只剩一个元素时,划分结束。
基本快速排序的代码实现
public class QuickSort { public static void sort(int[] arr){ recSort(arr,0,arr.length-1); } public static void recSort(int[] arr,int start, int end){ if(start>=end){ return; } int partitionIndex = partition(arr, start, end); recSort(arr,start,partitionIndex); recSort(arr,partitionIndex+1,end); } /** * 返回划分后,左指针和右指针相遇的下标 */ public static int partition(int[] arr,int start,int end){ int pivot=getPivot(arr,start,end); int left_pointer=start-1; int right_pointer=end+1; while (true){ while (arr[++left_pointer]<pivot);//left_pointer当遇到比基准值大的元素,停下来 while (arr[--right_pointer]>pivot);//right_pointer当遇到比基准值小的元素,停下来 if(left_pointer>=right_pointer){break;} swap(arr,left_pointer,right_pointer); } return right_pointer; } /** * 获得基准值 */ private static int getPivot(int[] arr, int start, int end) { return arr[start]; } //交换数组中两个元素的位置 private static void swap(int[] arr, int i, int j) { int temp= arr[i]; arr[i] =arr[j]; arr[j]=temp; } public static void main(String[] args) { int[] arr={3,1,9,0,4,7,2,6,5,8}; System.out.println("排序前数组:"+ Arrays.toString(arr)); sort(arr); System.out.println("排序前数后:"+ Arrays.toString(arr)); } }
运行程序,输出
排序前数组:[3, 1, 9, 0, 4, 7, 2, 6, 5, 8] 排序前数后:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
三数据项取中(media-of-three)
在上例中,我们对基准值的选择,总是选择划分后数组的第一个元素arr[start]
,这种方式可能遇到的问题是,划分后的数组不够均匀,这个我们在前面讲解划分(partition)的概念的时候已经提到过。
划分不均匀,会导致排序的效率降低,因为对于较大数组必须进行更多次的划分
理想状态下,应该选择数据项中的中值 作为枢纽,也就是说,应该有一半的数据项大于枢纽,一半的数据项小于枢纽,这会使数组被划分成两个大小相等子数组。可是如果没有选择好枢纽,那么快排的结果,就是划分为一大一小两个子数组进行排序,这样会降低算法的效率,因为较大的子数组要被划分更多次。
N个数据项数组的最坏情况是一个子数组只有一个数据项,而另一个子数组有N-1个数据项。如果在每一趟划分中都出现这种1个数据项和N-1个数据项的分割,那么每一个数据项都需要一个单独的划分步骤。在逆序排列的数据项中实际上发生的就是这种情况,在所有的子数组中,枢纽都是最小的数据项,此时算法的效率降低到了。
人们已经设计出很多更好的基准值选择方法,方法都是为了避免枢纽选择最大或者最小的值。理想情况下,基准值应该是一个中间值,但是选择出一个中间值,可能效率并不太高,因此采取了一个折中的方法,找到数组中第一个、最后一个以及中间位置的数据,选择中间位置的数据作为基准值,这种方法称之为"三数据项取中"(media-of-three
)。
三数据取中很好实现,只需要将getPivot
方法改为如下即可:
private static int getPivot(int[] arr, int start, int end) { int median=arr[start]; if(end-start>=2){//保证有3个数据项 int left=arr[start]; int right=arr[end]; int middle=arr[(start+end)/2]; if(left<middle&&middle<right){ median= middle; }else if(left<right&&right<middle){ median= right; }else{ median= left; } } return median; }