快速排序
算法思想: 基于分治的思想, 是冒泡排序的改进型. 首先在数组中选择一个基准点 (该基准点的选取可能影响快速排序的效率, 后面讲解选取的方法), 然后分别从数组的两端扫描数组, 设两个指示标志 (lo 指向起始位置, hi 指向末尾), 首先从后半部分开始, 如果发现有元素比该基准点的值小, 就交换 lo 和 hi 位置的值, 然后从前半部分开始扫秒, 发现有元素大于基准点的值, 就交换 lo 和 hi 位置的值, 如此往复循环, 直到 lo>=hi, 然后把基准点的值放到 hi 这个位置. 一次排序就完成了. 以后采用递归的方式分别对前半部分和后半部分排序, 当前半部分和后半部分均有序时该数组就自然有序了.
排序过程:
算法实现:
- public static int partition(int []array,int lo,int hi){
- // 固定的切分方式
- int key=array[lo];
- while(lo<hi){
- while(array[hi]>=key&&hi>lo){// 从后半部分向前扫描
- hi--;
- }
- array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){从前半部分向后扫描
- lo++;
- }
- array[hi]=array[lo];
- }
- array[hi]=key;
- return hi;
- }
- public static void sort(int[] array,int lo ,int hi){
- if(lo>=hi){
- return ;
- }
- int index=partition(array,lo,hi);
- sort(array,lo,index-1);
- sort(array,index+1,hi);
- }
快速排序的时间复杂度为 O(NlogN).
快速排序的优化
对于基准位置的选取一般有三种方法: 固定切分, 随机切分和三取样切分. 固定切分的效率并不是太好, 随机切分是常用的一种切分, 效率比较高, 最坏情况下时间复杂度有可能为 O(N2). 对于三数取中选择基准点是最理想的一种.
三数取中切分:
- public static int partition(int []array,int lo,int hi){
- // 三数取中
- int mid=lo+(hi-lo)/2;
- if(array[mid]>array[hi]){
- swap(array[mid],array[hi]);
- }
- if(array[lo]>array[hi]){
- swap(array[lo],array[hi]);
- }
- if(array[mid]>array[lo]){
- swap(array[mid],array[lo]);
- }
- int key=array[lo];
- while(lo<hi){
- while(array[hi]>=key&&hi>lo){
- hi--;
- }
- array[lo]=array[hi];
- while(array[lo]<=key&&hi>lo){
- lo++;
- }
- array[hi]=array[lo];
- }
- array[hi]=key;
- return hi;
- }
- public static void swap(int a,int b){
- int temp=a;
- a=b;
- b=temp;
- }
- public static void sort(int[] array,int lo ,int hi){
- if(lo>=hi){
- return ;
- }
- int index=partition(array,lo,hi);
- sort(array,lo,index-1);
- sort(array,index+1,hi);
- }
快速排序在序列中元素很少时, 效率将比较低, 不然插入排序, 因此一般在序列中元素很少时使用插入排序, 这样可以提高整体效率.
- public static void quick(int []array ,int lo,int hi){
- if(hi-lo+1<10){
- insertSort(array);
- }else{
- quickSort(array,lo,hi);
- }
- }
来源: http://www.bubuko.com/infodetail-3050344.html