6.快速排序(量大时特快,不稳定,对基础类型 随机快排最常用)
快排的几种写法:
(基本快排,随机快排,优化随机快排,双轴快排)
时空分析:
平均时间复杂度:n*logn ;空间复杂度logN (因为要记录断点【放在数组的位置】,用数组记录相等的范围)
如果不用随机快排,最坏时间复杂度为N*2,随机快排最坏为nlogN
简单快排:
选第一个数字作为基准,分两个区
核心代码:
public static void qucikSort1(int[] A, int L, int R){ if(L < R){ int pivot = A[L];//最左边的元素作为中轴元素 int i = L;//初始化时小于等于pivot的部分,元素个数为0 int j = L+1; //大于pivot的部分,元素个数也为0 while(j <= R){ if(A[j] <= pivot){ swap(A, ++i, j++); }else{ j++;//大于pivot的元素增加一个 } } //A[i]及A[i]以前的都小于等于pivot //循环结束后A[i+1]及它以后的都大于pivot //所以交换A[L]和A[i],这样我们就将中轴元素放到了适当的位置 swap(A, L, i); qucikSort1(A, L, i-1); qucikSort1(A, i+1, R); } }
优化随机快排:
1.范围内随机选一个数字做基准,小于它的放左边,大于它的放右边,等于它的放小于区右边;
2.利用小于区推动着等于区向大于区靠拢;同时大于区也会扩大.
2.当等于区与大于区相遇时,遍历完整个数组,将原数组分成了三个区域:小于区,等于区,大于区
3.对小于区和大于区再使用快排
其中partition的过程很重要,将数组分为三个区域.对应荷兰国旗问题.
public static void qucikSort(int [] a){ qucikSort(a,0,a.length-1); } public static void qucikSort(int [] a,int left,int right){ if(left<right){ swap(a, left + (int) (Math.random() * (right - left)), right); int[] p = partition(a, left, right); qucikSort(a, left, p[0] - 1); qucikSort(a, p[1] + 1, right); } } public static int[] partition(int [] a,int l,int r){ int less=l-1;//为l-1,因为小于区初始需要为0个 int more=r;//为r,因为最后要换 while(l<more){ if(a[l]<a[r]){ swap(a,l++,++less);//交换小于基准数时,小于区,等于区指针同时后移 }else if(a[l]>a[r]){ swap(a,l,--more);//交换大于基准数时,大于区扩大,指针左移 }else { l++;//相等时,等于区指针后移 } } swap(a,more,r);//最后将基准数与等于区最后一个元素替换 return new int[]{less+1,more};//返回等于区的起始坐标和结束坐标 } static void swap(int[] a,int i,int j){//快排的交换不能用位运算,因为小于区扩大时,可能涉及到自己与自己交换,位运算会将数交换成0 int temp=a[i]; a[i]=a[j]; a[j]=temp; }
快排的拓展(partition)
问题一:(分两个区)
给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
public static void partition(int[] a,int num) { int R = a.length - 1; int less = 0; int more = 1; while (more <= R) { if (a[more] <= num) { swap(a, ++less, more++); } else { more++; } } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
问题二(荷兰国旗问题):(分三个区)
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
public static void partition(int[] a,int num) { int more = a.length; int less = -1; int mid = 0; while (mid < more) { if (a[mid] < num) { swap(a, ++less, mid++); } else if(a[mid]>num){ swap(a,--more,mid); }else{ mid++; } } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }