Java快排算法(java工程师需要掌握哪些知识)

全栈程序员-站长 • 2022年4月11日下午1:00 • 未分类 • 阅读 38

大家好，又见面了，我是你们的朋友全栈君。

思路

对于给定的数组，从中选一个元素为比较对象，一般选最左或最右的元素，选左边为升序排，选右边反之。

数组array[]：
在这里插入图片描述
最左边：target = 5
数组下标：i = 0, j = 9

步骤：

①从右边遍历数组，把array[ j ]比5小的放在5的左边, j–；
交换位置后i = 0,j = 7：

在这里插入图片描述

②从左边遍历数组，把array[ i ]比5大的放在5的右边, i++；
交换位置后i = 5,j = 7：

在这里插入图片描述

③回到①②步骤循环执行：
在这里插入图片描述

循环执行后，比5小的都放在了5的左边，比5大的都放在了5的右边；

④此时5左边和右边部分还是乱序的，这就需要做递归操作，把0 2 3 1 4和 7 8 6 9 部分继续执行述排序步骤。
递归执行后：

在这里插入图片描述

代码示例：

public class _06FastSortExample { 
   
    /** * 左右两个哨兵 * * @param left * @param right 每次都是这个先 */
    public void quicksort(int[] a, int left, int right) { 
   
        int i, j, t, temp;//哨兵i,哨兵j，交换ij用到t,基准数temp
        if (left > right) { 
   //跳出
            return;
        }
        //传过来的参数进行赋值
        temp = a[left];//temp中存储的就是基准数
        i = left;//左边哨兵
        j = right;//右边哨兵
        while (i != j) { 
   
            //顺序很重要，先从右边开始找
            while (a[j] >= temp && i < j) { 
   
                j--;//记录哨兵j位置
            }
            //再从左边找：小于基准数的数
            while (a[i] <= temp && i < j) { 
   
                i++;//记录哨兵i位置
            }
            //交换两个数在数组中的位置
            if (i < j) { 
   
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        //最终将基准数归位 ： 就是基准数跟ij相遇位置的数进行交换
        a[left] = a[i];//a[i]给left的位置也就是0，就是基准数
        a[i] = temp;//基准数该a[i]

        quicksort(a, left, i - 1);//继续处理左边的，这里是一个递归的过程
        quicksort(a, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
    }

    public static void main(String[] args) { 
   
        int a[] = { 
   5,2,3,1,6,4,7,8,0,9};//数组//定义变量，这两个变量需要在子函数中使用
        _06FastSortExample f = new _06FastSortExample();
        f.quicksort(a, 0, a.length - 1);
        for (int aa : a) { 
   
            System.out.println(aa);
        }
    }
}