Quick Sort

快速排序实现思路

1. 在要排序的数组中，选择一个基准元素（通常是第一个或者是最后一个元素）;
2. 通过扫描把序列分为两个部分，一部分比基准元素小，另一部分比基准元素大，此时基准元素在排好序的位置;
3. 重复上述步骤，直到完全排好序。

代码实现

public static void quickSort(int[] arr) {
    int tmp;
    int length = arr.length;
    for (int i=0; i<length-1; i++) {
        for (int j=0; j<length - i -1; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

public void quickSort(int[] arr) {
  boolean swapped = true;
  int j = 0;
  int tmp;
  while (swapped) {
        swapped = false;
        j++;
        for (int i = 0; i < arr.length - j; i++) {                                       
              if (arr[i] > arr[i + 1]) {                          
                    tmp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = tmp;
                    swapped = true;
              }
        }                
  }
}

动画演示

复杂度分析

最好的情况下（完全正序）复杂度是 O(1)；最糟糕的情况下（完全倒序），复杂度是 O(n^2)

参阅文档

https://www.programcreek.com/2012/11/quicksort-array-in-java/