首页 > 代码库 > 快速排序算法--两个小人扔萝卜

快速排序算法--两个小人扔萝卜

    public static void quickSort(int[] A, int low, int high) {
        if(low < high) {
            int pivotpos = partition2(A, low, high); //完成pivot的定位
            quickSort(A, low, pivotpos - 1);
            quickSort(A, pivotpos + 1, high);            
        }
    }
    public static int partition1(int[] A, int low, int high) {
        //两个下标索引分别从首尾向中间扫描,挖掉一个标杆萝卜pivot,留个坑,首尾来回仍萝卜,是否要扔:比较与pivot的值大小关系
        //两个小人low与high站在两头
        //low处有坑,则high从他那里找萝卜扔,找到比pivot小的扔过来
        //high处就有了坑,从low处那里找萝卜扔,找到比pivot大的扔过来
        //扔完之后首尾之差为1个坑,那么原来挖出的标杆萝卜pivot入座,定位!
        int pivot = A[low];//将当前表的第一个元素作为枢纽值,同时留下一个坑,位于low
        while(low < high) {//循环跳出条件,low与high不断接近,直到(low = high)
            while(low < high && A[high] >= pivot) {
                //如果high处萝卜比标杆萝卜pivot大,就不处理,high往里走,缩小范围
                high--;
            }
            A[low] = A[high];//high处萝卜比标杆萝卜pivot小,扔给low处的坑,自己留下一个坑,,位于high
            while(low < high && A[low] <= pivot) {
                //如果low处萝卜比标杆萝卜pivot小,就不处理,low往里走,缩小范围
                low++;
            }
            A[high] = A[low];//low处萝卜比标杆萝卜pivot大,扔给high处的坑,自己留下一个坑,位于low
        }
        A[low] = pivot;//把pivot放在最后一个坑上,没有坑了
        return low;//循环跳出了,low = high = pivot应该在的坑
    }

技术分享

快速排序算法--两个小人扔萝卜