1 package com.gxf.sort; 2  3 /** 4  * 这里实现快速排序 5  * 快速排序是对冒泡排序的一种改进 6  * 选数组中的一个元素作为支点，通常选第一个元素 7  * 将大于支点的元素放到支点后面，将小于支点的元素放到支点前面 8  * 这样一趟下来，支点前面的就是小于支点元素，支点后面的大于支点元素 9  * 每一趟划分，返回支点的位置，这样形成了两个带排序的数组，在分别对两个数组进行递归调用10  * 直到每次划分只有一个元素11  * @author Administrator12  *13  */14 public class QuickSort {15     /**16      * 这里是对数组的一趟划分，返回支点在数组中的位置，默认第一个元素为支点17      * @param Rec18      * @param start19      * @param end20      * @return21      */22     public int quickSort(Rec rec[], int start,int end){23         int fulcrum = rec[start].key;//fulcrum有道查的支点24         int i = start;25         int j = end;//分别指向开头和结束26         while(i < j){//i==j时结束一次划分27             while(i < j && rec[j].key > fulcrum)//找出右边比支点小的元素28                 j--;29             rec[i].key = rec[j].key;//右边元素之间移到支点位置即可30             while(i < j && rec[i].key < fulcrum)//找出左边比支点大的元素31                 i++;32             rec[j].key = rec[i].key;//左边的大于支点元素之间交换过去33         }34         //这里要不要考虑相等元素的问题35         rec[i].key = fulcrum;36         return i;37     }38     39     /**40      * 对数组进行快速排序41      * 递归实现42      * @param rec43      */44     public void sort(Rec rec[], int start, int end){45         int index;46         if(start < end){47             index = quickSort(rec, start, end);48             sort(rec, start, index - 1);49             sort(rec, index + 1, end);//注意这里要+1要不然会无限递归，造成栈溢出50         }51     }52     /**53      * @param rec54      */55     public void sort(Rec rec[]){56         sort(rec, 0, rec.length - 1);57     }58     59 }

 1 package com.gxf.sort; 2  3 public class Rec { 4     public int key; 5      6     public Rec(int key){ 7         this.key = key; 8     } 9     public Rec(){10         11     }12     public void showArray(Rec rec[]){13         for(int i = 0; i < rec.length ; i++){14             15             System.out.print(rec[i].key + " ");16         }17     }18     public Rec[] getRecArray(int array[]){19         Rec result[] = new Rec[array.length];20         for(int i = 0; i < array.length; i++){21             result[i] =  new Rec(array[i]);22         }23         return result;24     }25 }

 1 package com.gxf.sort; 2  3 public class Test { 4  5     public static void main(String[] args) { 6         Rec rec = new Rec(); 7         QuickSort quickSort = new QuickSort(); 8          9         int array[] = new int[]{0, 32, 1, 34, 54, 5, 6};10         Rec array_rec[] = rec.getRecArray(array);11         System.out.println("使用快速排序之前的顺序：");12         rec.showArray(array_rec);13         14         quickSort.sort(array_rec);15         16         System.out.println("使用快速排序之后的顺序：");17         rec.showArray(array_rec);18     }19 20 }