快速排序

快速排序算法思想

快速排序和归并排序是互补的，归并排序将整个数组分成小数组，然后将排好序的小数组归并以将整个数组排序；而快速排序是在将大数组分成小数组的时候排序，当小数组小到不可再分的时候，排序也就完成了。
1.首先选择一个中间元素（一般选左端或者右端）。
2.分别获取除中间元素外的左右两端的索引。
3.由左右两端逐渐向中间迭代，每迭代一步比较一下索引中的元素和中间元素，当左边出现比中间元素大的元素的时候，暂停左边的迭代，当右边迭代出比中间元素小的元素的时候，右边迭代也暂停，交换左右两边的元素。
4.重复步骤3，直到左右两边的索引相遇，然后将中间元素移动到中间，这时中间元素左边的元素都比它小，右边的元素都比它大。
5.将上面的中间元素左右两边当成两个数组，分别进行上述过程。
6.重复以上步骤直到数组不可再分。

快速排序算法实现

 public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr, low, high);
        for (int i : arr) {
            System.out.print(i + "  ");
        }
    }

    /**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    private static void quickSort(int[] arr, int low, int high) {
        if (low >= high) return;
        // 分成两个
        int p1 = getPartion(arr, low, high);
        int p = getPartionOne(arr, low, high);
        System.out.println(p1 == p);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }

    /**
     * 切分
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int getPartionOne(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;
        int j = right + 1;
        while (true) {
            while (arr[++i] < tmp) {

            }
            while (arr[--j] > tmp) {

            }
            if (i >= j) {
                break;
            }
            exchage(arr, i, j);
        }
        exchage(arr, left, j);
        return left;
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private static void exchage(int[] arr, int i, int j) {
        int aux = arr[i];
        arr[i] = arr[j];
        arr[j] = aux;
    }

    /**
     * 总感觉这个切分更好理解
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int getPartion(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] > tmp)
                right--;
            arr[left] = arr[right];

            while (left < right && arr[left] <= tmp)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

算法复杂度

1.平均时间复杂度： O(NLogN)
2.最好情况时间复杂度： O(NLogN)
3.最差情况时间复杂度： O(NLogN)
4.所需要额外空间： O(1)

算法稳定性

1. 快速排序是不稳定的

想看完整版请点击：快速排序