基本思想

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

Java实现1

  1. //不稳定
  2. public class 快速排序 {
  3.     public static void main(String[] args) {
  4.         int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
  5.         System.out.println("排序之前：");
  6.         for (int i = 0; i < a.length; i++) {
  7.             System.out.print(a[i]+" ");
  8.         }
  9.         //快速排序
  10.         quick(a);
  11.         System.out.println();
  12.         System.out.println("排序之后：");
  13.         for (int i = 0; i < a.length; i++) {
  14.             System.out.print(a[i]+" ");
  15.         }
  16.     }
  17.     private static void quick(int[] a) {
  18.         if(a.length>0){
  19.             quickSort(a,0,a.length-1);
  20.         }
  21.     }
  22.     private static void quickSort(int[] a, int low, int high) {
  23.         if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
  24.             int middle = getMiddle(a,low,high);
  25.             // 前半部分排序
  26.             quickSort(a, 0, middle-1);
  27.             // 后半部分排序
  28.             quickSort(a, middle+1, high);
  29.         }
  30.     }
  31.     private static int getMiddle(int[] a, int low, int high) {
  32.         int temp = a[low];//基准元素
  33.         while(low<high){
  34.             //找到比基准元素小的元素位置
  35.             while(low<high && a[high]>=temp){
  36.                 high--;
  37.             }
  38.             a[low] = a[high]; 
  39.             while(low<high && a[low]<=temp){
  40.                 low++;
  41.             }
  42.             a[high] = a[low];
  43.         }
  44.         a[low] = temp;
  45.         return low;
  46.     }
  47. }

Java实现2

  1. /**  
  2.  * 快速排序<br/>  
  3.  * <ul>  
  4.  * <li>从数列中挑出一个元素，称为“基准”</li>  
  5.  * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，  
  6.  * 该基准是它的最后位置。这个称为分割（partition）操作。</li>  
  7.  * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>  
  8.  * </ul>  
  9.  *   
  10.  * @param numbers  
  11.  * @param start  
  12.  * @param end  
  13.  */  
  14. public static void quickSort(int[] numbers, int start, int end) {   
  15.     if (start < end) {   
  16.         int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
  17.         int temp; // 记录临时中间值   
  18.         int i = start, j = end;   
  19.         do {   
  20.             while ((numbers[i] < base) && (i < end))   
  21.                 i++;   
  22.             while ((numbers[j] > base) && (j > start))   
  23.                 j--;   
  24.             if (i <= j) {   
  25.                 temp = numbers[i];   
  26.                 numbers[i] = numbers[j];   
  27.                 numbers[j] = temp;   
  28.                 i++;   
  29.                 j--;   
  30.             }   
  31.         } while (i <= j);   
  32.         if (start < j)   
  33.             quickSort(numbers, start, j);   
  34.         if (end > i)   
  35.             quickSort(numbers, i, end);   
  36.     }   
  37. }

Java实现3

  1. public class QuickSort<T extends Comparable<T>> {
  2.     private static final Random RAND = new Random();
  3.     public static enum PIVOT_TYPE {
  4.         FIRST, MIDDLE, RANDOM
  5.     }
  6.     public static PIVOT_TYPE type = PIVOT_TYPE.RANDOM;
  7.     private QuickSort() { }
  8.     public static <T extends Comparable<T>> T[] sort(PIVOT_TYPE pivotType, T[] unsorted) {
  9.         int pivot = 0;
  10.         if (pivotType == PIVOT_TYPE.MIDDLE) {
  11.             pivot = unsorted.length/2;
  12.         } else if (pivotType == PIVOT_TYPE.RANDOM) {
  13.             pivot = getRandom(unsorted.length);  
  14.         }
  15.         sort(pivot, 0, unsorted.length - 1, unsorted);
  16.         return unsorted;
  17.     }
  18.     private static <T extends Comparable<T>> void sort(int index, int start, int finish, T[] unsorted) {
  19.         int pivotIndex = start + index;
  20.         T pivot = unsorted[pivotIndex];
  21.         int s = start;
  22.         int f = finish;
  23.         while (s <= f) {
  24.             while (unsorted[s].compareTo(pivot) < 0)
  25.                 s++;
  26.             while (unsorted[f].compareTo(pivot) > 0)
  27.                 f--;
  28.             if (s <= f) {
  29.                 swap(s, f, unsorted);
  30.                 s++;
  31.                 f--;
  32.             }
  33.         }
  34.         if (start < f) {
  35.             pivotIndex = getRandom((f - start) + 1);
  36.             sort(pivotIndex, start, f, unsorted);
  37.         }
  38.         if (s < finish) {
  39.             pivotIndex = getRandom((finish - s) + 1);
  40.             sort(pivotIndex, s, finish, unsorted);
  41.         }
  42.     }
  43.     private static final int getRandom(int length) {
  44.         if (type == PIVOT_TYPE.RANDOM && length > 0)
  45.             return RAND.nextInt(length);
  46.         if (type == PIVOT_TYPE.FIRST && length > 0)
  47.             return 0;
  48.         return length / 2;
  49.     }
  50.     private static <T extends Comparable<T>> void swap(int index1, int index2, T[] unsorted) {
  51.         T index2Element = unsorted[index1];
  52.         unsorted[index1] = unsorted[index2];
  53.         unsorted[index2] = index2Element;
  54.     }
  55. }

总结

快速排序是不稳定的排序。

  • 快速排序的时间复杂度为O(nlogn)。
  • 当n较大时使用快排比较好，当序列基本有序时用快排反而不好。