当前位置:   article > 正文

java 算法之快速排序_快速排序算法java

快速排序算法java

1、快速排序是一种比较高效的排序算法,采用“分而治之”的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。

2、快速排序图

3、Java 代码实现快速排序

public static void main(String[] args) {
    int[] arry = {9,8,7,6,5,4,3,2,1};
    quickSort(arry,0, arry.length-1);
    System.out.println(Arrays.toString(arry));
}
public static void quickSort(int[] arry,int left,int right){
    //运行判断,如果左边索引大于右边是不合法的,直接return结束次方法
    if(left>right){
        return;
    }
    //定义变量保存基准数
    int base = arry[left];
    //定义变量i,指向最左边
    int i = left;
    //定义j ,指向最右边
    int j = right;
    //当i和j不相遇的时候,再循环中进行检索
    while(i!=j){
        //先由j从右往左检索比基准数小的,如果检索到比基准数小的就停下。
        //如果检索到比基准数大的或者相等的就停下
        while(arry[j]>=base && i<j){
            j--; //j从右往左检索

        }
        while(arry[i]<=base && i<j){
            i++; //i从左往右检索
        }
        //代码走到这里i停下,j也停下,然后交换i和j位置的元素
        int tem = arry[i];
        arry[i] = arry[j];
        arry[j] = tem;


    }
    //如果上面while条件不成立就会跳出这个循环,往下执行
    //如果这个条件不成立就说明 i和j相遇了
    //如果i和j相遇了,就交换基准数这个元素和相遇位置的元素
    //把相遇元素的值赋给基准数这个位置的元素
    arry[left] = arry[i];
    //把基准数赋给相遇位置的元素
    arry[i] = base;
    //基准数在这里递归就为了左边的数比它小,右边的数比它大
    //排序基准数的左边
    quickSort(arry,left,i-1);
    //排右边
    quickSort(arry,j+1,right);

}

4、这个是面试常考的算法之一,后续将继续更新剩下的几种。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/476536
推荐阅读
相关标签
  

闽ICP备14008679号