利用挖坑填数+分治实现的快排

代码如下：

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Formatter;import java.util.HashMap;import java.util.Map;public class TestJava {    public static void main(String[] args) {        String string = readFromConsole();        System.out.println("input:" + string);        char chs[] = string.toCharArray();        qSort(chs, 0, chs.length - 1);        System.out.println("after sorted:" + new String(chs));    }    private static void qSort(char[] chs, int start, int end) {        if (start >= end) {            return;        }        char fuck = chs[start]; // 先从数列中取出一个数作为基准数。        int left = start;        int right = end;        while (left < right) {            // 跳过比基数大于等于的            while (left < right && chs[right] >= fuck) {                right--;            }            // 比基数小的换到左边            if (left != right) {                chs[left] = chs[right]; // 用这次的值填上次的坑。                left++;            }            while (left < right && chs[left] < fuck) {                left++;            }            // 比基数大的换到右边            if (left != right) {                chs[right] = chs[left];                right--;            }        }        chs[left] = fuck; // 把基数放到中间        qSort(chs, start, left);        qSort(chs, left + 1, end);    }    /**     * 从终端输入一行字符串     *      * @return     */    private static String readFromConsole() {        String inStr = null;        BufferedReader reader = new BufferedReader(new InputStreamReader(                System.in));        try {            inStr = reader.readLine();        } catch (IOException e) {            // TODO Auto-generated catch block            e.printStackTrace();        }        return inStr;    }}

 

详细可以看这篇博文：