可能是史下最优雅的 java 快速排序

可能是史上最优雅的 java 快速排序
受erlang启发，写的一个快速排序，兼具排重功能，哈哈。

elang快速排序代码如下：

qsort([]) -> [];qsort([Pivot|T]) -> qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X <- T, X > Pivot]) 

深夜灵感突现，写了又调，2个小时后出炉
其思想是，sort接受的参数是一个乱序的List，但sort返回的一个子集必须是已排好序的。
用到了递归，递归用好了真是无比强大，在函数式编程语言中尤其如此，比如说erlang,lisp
sort方法仅用了不到20行（当然还有更变态的方法把if语句写的更短，但为了可读性不这么写）！

package com.test.clazz;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Qsort3 {public static List<Integer> sort(List<Integer> l) {if (l.size() == 0) return l;Integer pivot = l.get(0);List<Integer> lLower = new ArrayList<Integer>();List<Integer> lHigher = new ArrayList<Integer>();for (Integer e : l) {if (e < pivot) {lLower.add(e);}if (e > pivot) {lHigher.add(e);}}List<Integer> sorted = new ArrayList<Integer>();sorted.addAll(sort(lLower));sorted.add(pivot);sorted.addAll(sort(lHigher));return sorted;}public static void main(String[] args) {List<Integer> a = Arrays.asList(3,5,7,4,23,4,56,23,6,1,81);System.out.println(sort(a));}}

    上面这段代码可能有点费解，下面这段是整个调试过程输出到控制台看结果的，“-”表示函数调用到第几层，可以看到最后整个递归过程结束之后，各个List的子集都已经一一排好：）

package com.test.clazz;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 受erlang快速排序的启发，写的java快速排序，应用了尾递归 * @author high0048 * */public class Qsort2 {public static List<Integer> sort(List<Integer> l, int i) {String tab = "-";for (int j = 0; j < i; j++) {tab += "-";}int size = l.size();if (size == 0)return l;//  pivot 枢轴；中心点；Integer pivot = l.get(0);System.out.println(tab + "pivot: " + pivot);List<Integer> lLower = new ArrayList<Integer>();List<Integer> lHigher = new ArrayList<Integer>();for (Integer e : l) {if (e < pivot) {lLower.add(e);}if (e > pivot) {lHigher.add(e);}}System.out.println(tab + "Lower: " + lLower);System.out.println(tab + "Higher: " + lHigher);List<Integer> sorted = new ArrayList<Integer>();sorted.addAll(sort(lLower, i++));sorted.add(pivot);sorted.addAll(sort(lHigher, i++));System.out.println(tab + "Lower+pivot+Higher: " + sorted);return sorted;}public static void main(String[] args) {List<Integer> a = Arrays.asList(3,5,7,4,23,4,56,23,6,1,81);System.out.println(sort(a, 0));}}

    感觉这段排序比JDK自己的快速排序写得好，哈哈
    最后补充一句，List里的类型如果改成Compareable的话，就可以排任意类型了哦

查看更多 下一篇