首先解释什么是快速排序算法:
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由 C. A. R. Hoare(东尼•霍尔,Charles Antony Richard Hoare)在1960年提出,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序有什么用?
排序算法是为了让无序的数据组合变成有序的数据组合。有序的数据组合最大的优势是在于当你进行数据定位和采用时,会非常方便,因为这个数据是有序的,从而在代码设计的时候会让你避免很多不必要的麻烦,因为无序数据你在进行推断数据前后关系的时候会显示很繁琐
快速排序怎么用?
下面这段是整个调试过程输出到控制台看结果的,“-”表示函数调用到第几层,可以看到最后整个递归过程结束之后,各个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)); } }