快速排序

要求算法实现二背下来

时间复杂度：O(nlogn)

  1. 快排的性能
    快排在排序算法中性能最好，数据越大排序最优，但在最坏的极端情况下会退化成O(n²)。若前提已知待处理的数据会出现极端的情况下，可以选择比较稳定的归并排序。
    最坏的情况：每次所取的基准都是最小的

算法实现：

  1. public void test(){
  2.         int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };
  4.         //记得传入右边边界要减一
  5.         sort(n,0,n.length-1);
  7.         for (int m : n) {
  8.             System.out.println(m+"\t");
  9.         }
  11.     }
  13.     public void sort(int[] n,int left,int right){
  14.         //制定递归出口
  15.         if (left<right) {
  16.             int index = quicksort(n, left, right);
  17.             //确定好下标，为第二次递归做准备
  18.             sort(n, left, index - 1);
  19.             sort(n, index + 1, right);
  20.         }
  21.     }
  23.     public int quicksort(int[] n,int left,int right){
  24.         //将随机一个数与最左边的一个数交换
  25.         swap(n,new Random().nextInt(right-left+1)+left,left);
  26.         int temp = n[left];
  27.         int tempIndex = left;
  28.         while (right>left){
  29.             while (temp<=n[right] && right>left){
  30.                 right--;
  31.             }
  32.             while (temp>=n[left] && right>left){
  33.                 left++;
  34.             }
  35.             //该交换为将大于基数的数移至基数左边
  36.             //小于基数的数移至基数右边
  37.             swap(n,left,right);
  38.         }
  39.         //该交换为基准与确定好的位置交换
  40.         swap(n,tempIndex,left);
  42.         //回传的是确定好位置的基准元素下标
  43.         return left;
  44.     }
  46.     public void swap(int[] n,int i,int j){
  47.         int temp = n[i];
  48.         n[i] = n[j];
  49.         n[j] = temp;
  50.     }

写法二：

  1. public class QuickSort {
  2.     private int[] array;
  3.     public QuickSort(int[] array) {
  4.         this.array = array;
  5.     }
  6.     public void sort() {
  7.         quickSort(array, 0, array.length - 1);
  8.     }
  9.     public void print() {
  10.         for (int i = 0; i < array.length; i++) {
  11.             System.out.println(array[i]);
  12.         }
  13.     }
  15.     /**
  16.      * 递归排序
  17.      * @param src
  18.      * @param begin
  19.      * @param end
  20.      */
  21.     private void quickSort(int[] src, int begin, int end) {
  22.         if (begin < end) {
  23.             int key = src[begin];
  24.             int i = begin;
  25.             int j = end;
  26.             while (i < j) {
  27.                 while (i < j && src[j] > key) {
  28.                     j--;
  29.                 }
  30.                 if (i < j) {
  31.                     src[i] = src[j];
  32.                     i++;
  33.                 }
  34.                 while (i < j && src[i] < key) {
  35.                     i++;
  36.                 }
  37.                 if (i < j) {
  38.                     src[j] = src[i];
  39.                     j--;
  40.                 }
  41.             }
  42.             src[i] = key;
  43.             quickSort(src, begin, i - 1);
  44.             quickSort(src, i + 1, end);
  45.         }
  46.     }
  47. }