一.代码

  1. public class QuickSort {
  2.     public static void quickSort(int[] arr, int startIndex, int endIndex) {
  3.         if (startIndex >= endIndex) {
  4.             return;
  5.         }
  6.         int pivotIndex = partition(arr, startIndex, endIndex);
  7.         quickSort(arr, startIndex, pivotIndex - 1);
  8.         quickSort(arr, pivotIndex + 1, endIndex);
  9.     }
  11.     private static int partition(int[] arr, int startIndex, int endIndex) {
  12.         int pivot = arr[startIndex];
  13.         int left = startIndex;
  14.         int right = endIndex;
  16.         while (left != right) {
  17.             while (left < right && arr[right] >= pivot) {
  18.                 right--;
  19.             }
  20.             while (left < right && arr[left] <= pivot) {
  21.                 left++;
  22.             }
  23.             if (left < right) {
  24.                 int temp = arr[left];
  25.                 arr[left] = arr[right];
  26.                 arr[right] = temp;
  27.             }
  28.         }
  29.         arr[startIndex] = arr[left];
  30.         arr[left] = pivot;
  31.         return left;
  32.     }
  33. }

二.稳定性

不稳定。5 3 4 3 6 7 10 排序 3 3 4 5 6 7 10 ，3的顺序变了。

三.时间复杂度

最优O(nlogn) 最差O(n^2) 平均O(nlogn)