排序--06---快速排序

快速排序

定义:

• 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；
2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
   
   

切分原理：

快速排序是也是一种分治思想的排序算法

把一个数组切分成两个子数组的基本思想：

1. 找一个基准值，用两个指针分别指向数组的头部和尾部；
2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4. 交换当前左边指针位置和右边指针位置的元素；
5. 重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
   
   
   
   
   

代码实现 1

快速排序API设计:

代码

publicclassQuick{/* 比较v元素是否小于w元素 */privatestaticbooleanless(Comparable v,Comparable w){returnv.compareTo(w)<0;}/* 数组元素i和j交换位置 */privatestaticvoidexch(Comparable[]a,inti,intj){Comparable t=a[i];a[i]=a[j];a[j]=t;}//对数组内的元素进行排序publicstaticvoidsort(Comparable[]a){intlo=0;inthi=a.length-1;sort(a,lo,hi);}//对数组a中从索引lo到索引hi之间的元素进行排序privatestaticvoidsort(Comparable[]a,intlo,inthi){//安全性校验if(hi<=lo){return;}//需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；intpartition=partition(a,lo,hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引//让左子组有序sort(a,lo,partition-1);//让右子组有序sort(a,partition+1,hi);}//对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引publicstaticintpartition(Comparable[]a,intlo,inthi){//确定分界值Comparable key=a[lo];//定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置intleft=lo;intright=hi+1;//切分while(true){//先从右往左扫描，移动right指针，找到一个比分界值小或者相等的元素，停止while(less(key,a[--right])){if(right==lo){break;}}//再从左往右扫描，移动left指针，找到一个比分界值大或者相等的元素，停止while(less(a[++left],key)){if(left==hi){break;}}//判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可if(left>=right){// 一定要是left>=right,因为有可能出现left大于right的情况break;}else{exch(a,left,right);}}//交换分界值exch(a,lo,right);//此时只能是和right交换值,因为有可能left此时已经大于right了.returnright;}}

测试:

publicstaticvoidmain(String[]args){Integer[]data={6,1,6,2,7,9,3,4,5,6,8};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));Quick.sort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}

代码实现 2

/** * 快速排序 * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小， * 则分别对这两部分继续进行排序，直到整个序列有序。 * @author shkstart * 2018-12-17 */publicclassQuickSort{privatestaticvoidswap(int[]data,inti,intj){inttemp=data[i];data[i]=data[j];data[j]=temp;}publicstaticvoidquickSort(int[]data){subSort(data,0,data.length-1);}privatestaticvoidsubSort(int[]data,intstart,intend){if(start<end){intbase=data[start];intlow=start;inthigh=end+1;while(true){while(low<end&&data[++low]-base<=0);while(high>start&&data[--high]-base>=0);if(low<high){swap(data,low,high);}else{break;}}swap(data,start,high);subSort(data,start,high-1);//递归调用subSort(data,high+1,end);}}publicstaticvoidmain(String[]args){int[]data={9,-16,30,23,-30,-49,25,21,30};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));quickSort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}

对线排序:

importmain.java.Algorithms.DataWrap;publicclassQuickSort02{privatestaticvoidswap(DataWrap[]data,inti,intj){DataWraptemp=data[i];data[i]=data[j];data[j]=temp;}privatestaticvoidsubSort(DataWrap[]data,intstart,intend){if(start<end){DataWrapbase=data[start];inti=start;intj=end+1;while(true){while(i<end&&data[++i].compareTo(base)<=0);while(j>start&&data[--j].compareTo(base)>=0);if(i<j){swap(data,i,j);}else{break;}}swap(data,start,j);subSort(data,start,j-1);subSort(data,j+1,end);}}publicstaticvoidquickSort(DataWrap[]data){subSort(data,0,data.length-1);}publicstaticvoidmain(String[]args){DataWrap[]data={newDataWrap(9,""),newDataWrap(-16,""),newDataWrap(21,"*"),newDataWrap(23,""),newDataWrap(-30,""),newDataWrap(-49,""),newDataWrap(21,""),newDataWrap(30,"*"),newDataWrap(30,"")};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));quickSort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}

快速排序 是不稳定的

• 快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。

快速排序时间复杂度分析：

快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n).

但整个快速排序的时间复杂度和切分的次数相关。

最优情况：

每一次切分选择的基准数字刚好将当前序列等分。

• 如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);

最坏情况:

• 每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);
  
  最坏情况下，快速排序的时间复杂度为O(n^2);

平均情况:

• 每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为O(nlogn),

快速排序的平均时间复杂度为O(nlogn),

小结:

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn) 不稳定