快速排序实现

快速排序是使用递归来实现的一种排序。快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

下面是Java代码实现

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        //把数组中的第0个数字作为标准数
        int stard = arr[start];
        //记录需要排序的下标
        int low = start;
        int high = end;
        //循环找比标准数大的数和比标准数小的数
        while (low < high) {
            //右边的数字比标准数更大
            while (low < high && stard <= arr[high]) {
                high--;
            }
            //使用右边的数字替换左边的数字
            arr[low] = arr[high];
            //如果左边的数字比标准数小
            while (low < high && stard >= arr[low]) {
                low++;
            }
            arr[high] = arr[low];
        }
        //把标准数赋给低所在的位置的元素
        arr[low] = stard;
        //处理所有小的数字
        quickSort(arr, start, low);
        //处理所有大的数字
        quickSort(arr, low + 1, end);
    }

}

其中有一点需要主义，哨兵单位（也就是上面的标准数）将数组分为两边，两边的值必须小于等于或大于等于，这个等于一定不能少，不然上面的代码会造成死循环,如下图所示，哨兵单位和前后的位置元素都为一样的数字，这将会在外循环中造成死循环