排序篇(7)--快速排序

2019-11-06 07:44:03

字体：大中小

来源：转载

供稿：网友

希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，同属于选择排序类，而接下来要说明的快速排序则是冒泡排序的一种升级，都属于交换排序类。

一、快速排序

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

二、快速排序算法实现

package Sort;/** * Created by LKL on 2017/3/4. */public class TestQuickSort { public static void main(String[] args){ int[] adj = new int[]{5,1,9,8,3,7,4,6,2}; PRint(adj); QuickSort(adj); } public static void QuickSort(int[] adj){ QSort(adj,0,adj.length-1); } public static void QSort(int[] adj,int low,int high){ int pivot; if(low<high){ //将序列表一分为二，算出枢轴值 pivot = Partition(adj,low,high); //对低子表递归排序 QSort(adj,low,pivot-1); //对高子表递归排序 QSort(adj,pivot+1,high); //打印输出每次的内容 print(adj); } } /* * 选出其中的一个关键字，放在一个合适的位置， * 使得左边的值都比它小，右边的值比它大，将它成为枢轴（pivot） * * */ public static int Partition(int[] adj,int low,int high){ int pivotkey; pivotkey=adj[low]; //从表的两端交替向中间扫描 while(low<high){ while(low<high&&adj[high]>=pivotkey){ high--; } swap(adj,low,high);//将比枢轴记录小的交换到低端 while(low<high&&adj[low]<=pivotkey){ low++; } swap(adj,low,high);//将比枢轴记录大的交换到高端 } return low; } public static void swap(int[] adj,int low,int high){ int temp; temp=adj[low]; adj[low]=adj[high]; adj[high]=temp; } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "/t"); } System.out.println(); }}

运行结果如下：

5 1 9 8 3 7 4 6 2 1 2 3 4 5 7 8 6 9 1 2 3 4 5 7 8 6 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

三、快速排序优化

由于上述代码，我们是有一个假设性的操作，即假设pivot刚好处于low与high的中间，而事实并不会这么凑巧，当出现{9,1,3,5,2,4,7,6,8}，此时pivot为9，转化后，并没有发生什么实质性的优化，因此有人想到了“三数取中法”，即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数。此时，pivot至少不会是最大或者最小了。主要是修改了Patition方法，首先判定pivot不是最大，也不是最小。

/* * 选出其中的一个关键字，放在一个合适的位置， * 使得左边的值都比它小，右边的值比它大，将它成为枢轴（pivot） * * */ public static int Partition(int[] adj,int low,int high){ int pivotkey; int m=low +(high-low)/2; if(adj[low]>adj[high]){ swap(adj,low,high); } if(adj[m]>adj[high]){ swap(adj,high,m); } if(adj[m]>adj[low]){ swap(adj,m,low); } pivotkey=adj[low]; //从表的两端交替向中间扫描 while(low<high){ while(low<high&&adj[high]>=pivotkey){ high--; } swap(adj,low,high);//将比枢轴记录小的交换到低端 while(low<high&&adj[low]<=pivotkey){ low++; } swap(adj,low,high);//将比枢轴记录大的交换到高端 } return low; }

四、快速排序复杂度分析

(1)快速排序最优的时间复杂度

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然上面的不是)；此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：

T[n] = 2T[n/2] + n ------第一次递归

令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n —-第二次递归

= 2^2 T[ n/ (2^2) ] + 2n

令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} +2n ——-第三次递归

= 2^3 T[ n/ (2^3) ] + 3n ...................................................................................... 令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束) 当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。

得到： T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn； T[n] = 2^m T[1] + mn ；其中m = logn;

T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数

又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；

综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )。