求解随机快速排序的问题。

Question

求解public void random_partion(int start, int length)里面的代码块理解不了是什么意思。求各位大神指教。

 package cn.edu.xmut;

import java.util.Random;
import java.util.Scanner;

public class QuickSort {
    private int initArray[];

    public int[] getInitArray() {
        return initArray;
    }

    public void setInitArray(int[] initArray) {
        this.initArray = initArray;
    }

    public void random_partion(int start, int length) {//核心代码（随机位置二分排序）
        if (length <= 1)
            return;
        Random rand = new Random();
        int index = rand.nextInt(length) + start;
        int i = start - 1;
        int j = start;
         System.out.println("start--->"+start+" length--->"+length+" i--->"
        +i+" j--->"+j+" index--->"+index+" start+length-1--->"+(start+length-1));
        this.swap(index, start + length - 1);
        for (j = start; j < start + length; j++) {
            if (initArray[j] < initArray[start + length - 1]) {
                this.swap(++i, j);
            }
        }
        this.swap(++i, start + length - 1);
        random_partion(start, i - start + 1);
        random_partion(i + 1, length + start - i - 1);
    }

    public int[] quickSorted() {
        this.random_partion(0, initArray.length);
        return initArray;
    }

    public void swap(int a, int b) {
        int temp = initArray[a];
        initArray[a] = initArray[b];
        initArray[b] = temp;
    }

    public static void main(String[] args) {

        QuickSort sort = new QuickSort();
        int[] array;
        int length;
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入数组长度：");
        length = scanner.nextInt();
        array = new int[length];
        for (int i = 0; i < length; i++) {
            System.out.println("请输入第" + (i + 1) + "个数：");
            array[i] = scanner.nextInt();
        }

        sort.setInitArray(array);
        array = sort.quickSorted();
        for (int i = 0; i < array.length; i++) {
            System.out.println("array[" + i + "]= " + array[i]);
        }
    }
}

谢谢了。

Answer 1

快速排序的思路就是选取一个元素作为参考，将等待排序的数据分为2部分，比这个数字小的，和比这个数字大的。这个过程叫做分区（partition）
然后分别对这两个部分分别再分区，直到每个分区都只有一个元素，排序完成。
random_partion就是选取待排序列中随机的一个下标作为比较的参考。