受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的话,就可以排任意类型了哦
分享到:
相关推荐
软件工程、快速排序法。绝顶的好东西。快速排序.Java快速排序.Java快速排序.Java
java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
java 快速排序 折半查找的界面实现 (递归与分治法)
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
java 编写的快速排序程序递归形式我做的课堂作业,,希望能帮助大家。。。
快速排序 java实现
详细解释了快速排序的java实现.里面有代码,还有注释说明
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
java实现的快速排序算法
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
清楚明确的代码书写,让你轻易学懂快速排序法
快速排序是一个知名度极高的排序算法,其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。这里采用简单的小例子实现快速排序。
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
java中实现快速排序算法。随机产生几个数然后对其进行排序
(数据结构课程设计)使用java语言实现对于快速排序的演示,其中提供了暂停功能,控制图画运行速度功能,能较好的演示快速排序。
采用java语言实现的排序排序,通俗易懂。
快速排序算法java代码,内附运行结果,望对大家有帮助,谢谢!
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
之前做的四种排序动画,快排比较快,所以为快排专门做一个动画