花了很久的时间才搞定，根据算法导论里面的伪代码写的
最初在网上找的例子都有问题，不知为啥，都把我给搞晕了
然后按伪代码来写，也出错，真是很郁闷
然后全部删掉重新写了很多次，突然间就写好了
主要难点在于partition函数，里面的i和j的关系，它们的值在什么时候进行交换
可能是很久没有考虑过数据结构的东东了
因此今天花了很多时间来做这个
package cn.qs.util;public class SortUtil { /** * 快速排序法 * 典型事例 快速排序：（以整数类型为例） * 快速排序的思想是，对于输入，按照以下二个步骤进行排序 * 对于数组a[p:r] * 1）分解（其实包括合并过程）：以a[p]为基准将数组分成三段a[p:q-1]、a[q]、a[q+1:r]使得a[p:q-1]中的任意元素都小于等于a[q]，a[q+1:r]中的任意元素都大于等于a[q]. * 2）递归求解：通过递归调用快速排序，分别完成a[p:q-1]和a[q+1:r]的排序。 * @param Array 数组，需要排序的集合 * @param p 数组的开始下标 * @param r 数组的结束下标 */ public void quickSort(int[] Array, int p, int r){ if(p < r){ int q = partition(Array, p, r); //递归调用 quickSort(Array, p, q - 1); quickSort(Array, q + 1, r); } } public int partition(int[] Array, int p, int r){ int x = Array[r];//带比较的值，直接取最后一个 int i = p - 1; for(int j= p; j <= r - 1; j++){ if(Array[j] <= x){ i++; //把较小的值放到数组左边 this.swap(i, j, Array); } } //是把进行比较的值(最初放在了数组最后)与该值正确的位置进行互换 this.swap(i+1, r, Array); return i + 1; } /** * 数组内的交换 * @param a * @param b * @param arraySort */ private void swap(int a, int b, int[] arraySort) { int tmp = arraySort[a]; arraySort[a] = arraySort[b]; arraySort[b] = tmp; } /** * @param args */ public static void main(String[] args) { int[] arrays = {43,36,15,11,9,12,35}; // int[] arrays = { 12,9,15,11,36}; SortUtil su=new SortUtil(); su.quickSort(arrays, 0, arrays.length-1); for(int i=0;i<arrays.length;i++){ System.out.print(arrays[i]+","); } }}
