快速排序:找到一个基数,然后把全部元素和基数进行比较,小于基数的放在左边,大于的放在右边,然后基数和左边最后一个数进行对调,基数所在位置就是最后正确的目标位置,同理后面的元素比较,一般我们以第一个元素设为基数
//a是待排序数组,p为左边界,r为右边界,递归调用 public static void QKSort(int[] a, int p, int r){ if(p<r){ //进行比较并交换基数和左边最后一个比基数小的数 int k = Compare(a,p,r); //返回调换后的基数位置 //基数位置已确定,对基数左右未确定的序列确定下一个新的基数的位置 QKSork(a,p,k-1); QKSork(a,k+1,r); } } //比较,得到基数位置 public static void Compare(int[] a, int p, int r){ //一般以第一个数为基数 int x = a[p]; //设置左右游标 int i = p; //左,后面++i排除了基数的影响 int j = r+1; //右,后面--j排除了越界的影响 while(true){ while(a[++i]<x && i<r);//从左边开始遍历,当左边出现比x大或越界的时候停下 while(a[--j]>x); //从最右边开始遍历,单右边出现比x小的时候停下 //当出现i>=j的时候,基数的正确位置已出现,已完成左小右大,跳出循环 if(i>=j){ break; } //未出现i>=j时,需要调换ij数据位置,保证左小右大,自己写一个交换函数,或者直接交换 Swap(a,i,j); } //跳出循环后,交换基数和左边最后一个比x小的数的位置,并返回基数现有位置 a[p] = a[j]; a[j] = x; return j; }
为了让时间复杂度出现最坏的几率变小,可以采用随机化的方式,只需要在上面基础上再添加一个函数即可。
//在序列范围内随机抽出一个数作为基数,和左边界的数进行对调 public static int random(int[] a, int p, int r){ //在p r范围内随机选中一个下标 int index = (int)(p+Math.random()*(r-p)); //对调基数和首元素位置,是为了方便调用上面的Compare()函数 Swap(a,p,index); return Compare(a,p,r); } //上面第一个函数 int k = Compare(a,p,r); //改为 int k = random(a,p,r);