关于Java排序算法-快速排序（Quick Sort）

快速排序是对气泡排序的一种改进。
基本思想：通过一趟排序将待排序列分割成独立的两部分，其中一部分元素的排序码均比另一部分的排序码小，分别对这两部分继续进行排序，直至整个序列有序。
具体过程：设待排序列为 A[s..t]，选取任意一个元素作为支点(基准元素，一般就选A[s])，然后从区间两端向中间依次比较元素，一旦发现前半部分有元素大于基准元素，后半部分有元素小于基准元素，则交换这两个元素，所有元素比较一遍后，最后把基准元素交换到两部分的中间，使得所有比基准元素大的都排在此基准元素的后面；所有比基准元素小的都放在此基准元素的前面。即该基准元素把序列 A[s..t] 分成两部分，此过程称为一次划分。

public class SortTest {
  public static void main(String[] args) {
    int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };
    display("原始数据 : ", arr);

    // 快速排序
    quickSort(arr, 0, arr.length - 1);

    display("排序结果:", arr);
  }

  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 快速排序
  public static void quickSort(int[] arr, int s, int t) {
    // 递归算法，对区间a[s] ～a[t] 进行快速排序
    int i = s + 1, j = t;
    int temp = 0;
    int x = arr[s]; // 第一个为基准元素
    while (i <= j) {
      // 从左到右
      while (i <= j && arr[i] <= x) {
        i++;
      }
      
      // 从右到左
      while (i <= j && arr[j] >= x) {
        j--;
      }

      if (i < j) {
//				temp = arr[i];
//				arr[i] = arr[j];
//				arr[j] = temp;
        swap(arr, i, j);
        i++;
        j--;
      }
    }
    
    // 交换基准元素
    if (s != j) {
      arr[s] = arr[j];
      arr[j] = x;
    }
    
    // 处理左区间
    if (s < j - 1) {
      quickSort(arr, s, j - 1);
    }
    
    // 处理右区间
    if (j + 1 < t) {
      quickSort(arr, j + 1, t);
    }
  }

}

原始数据 :
49 38 65 97 76 13 27 49
排序结果:
13 27 38 49 49 65 76 97