接上篇,改进了快速排序会排重的特性,现在不会排重了,而且输出的日志组织的更为合理,更能明白程序运行的过程
原理再阐述一下:
把列表中的数字分为3类,以第一个数字为轴心,分为小于它的,等于它的,大于它的。然后对于小于它的和大于它的,分别递归调用上述整个过程,直到列表为空。
程序的执行就像一颗树,又像一个栈,只有到分到最后列表为空时,才知道最终结果,然后这些结果一下子返回,每个子集都是排好序的,最后整个集合也是排好序的。
package com.test.clazz;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Qsort4 {
public static List<Integer> sort(List<Integer> l, int i) {
// tab 的作用是分清楚调用层次,前面有几个tab就是第几层
String tab = "-";
for (int j = 0; j < i; j++) {
tab += "-";
}
System.out.println(tab + "List to sort: " + l);
int size = l.size();
if (size == 0) {
System.out.println(tab + "This recursion sort branch finished!" + tab);
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>();
List<Integer> lEquals = new ArrayList<Integer>();
for (Integer e : l) {
if (e < pivot) {
lLower.add(e);
}
if (e > pivot) {
lHigher.add(e);
}
if (e == pivot) {
lEquals.add(e);
}
}
//初始化 假设已排好的 list
List<Integer> sorted = new ArrayList<Integer>();
//初始化 下一调用层次
int level = ++i;
System.out.println(tab + "Begin to sort lower: " + lLower);
sorted.addAll(sort(lLower, level));
System.out.println(tab + "Add pivot: " + lEquals);
sorted.addAll(lEquals);
System.out.println(tab + "Begin to sort higher: " + lHigher);
sorted.addAll(sort(lHigher, level));
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));
}
}
分享到:
相关推荐
软件工程、快速排序法。绝顶的好东西。快速排序.Java快速排序.Java快速排序.Java
java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
java 快速排序 折半查找的界面实现 (递归与分治法)
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
详细解释了快速排序的java实现.里面有代码,还有注释说明
快速排序 java实现
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
java实现的快速排序算法
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
清楚明确的代码书写,让你轻易学懂快速排序法
快速排序是一个知名度极高的排序算法,其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。这里采用简单的小例子实现快速排序。
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
java中实现快速排序算法。随机产生几个数然后对其进行排序
(数据结构课程设计)使用java语言实现对于快速排序的演示,其中提供了暂停功能,控制图画运行速度功能,能较好的演示快速排序。
采用java语言实现的排序排序,通俗易懂。
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
之前做的四种排序动画,快排比较快,所以为快排专门做一个动画
这是我自己写的java,快速排序法。以前在网上找了很久,都没有合适的,就自己写了个,希望大家有需要的能用到。呵呵呵
用Java对整型一维数组实现快速排序,pivot值默认为数组第一个值。