快速排序算法

快速排序:找到一个基数,然后把全部元素和基数进行比较,小于基数的放在左边,大于的放在右边,然后基数和左边最后一个数进行对调,基数所在位置就是最后正确的目标位置,同理后面的元素比较,一般我们以第一个元素设为基数

//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);

上一篇:C++类模板 template <class T> 详细使用方法


下一篇:[Kotlin] Compare Functional Programming in Java and Kotlin