排序算法:交换排序_快速排序

排序算法学习内容来源于《啊哈算法》，如果我的行为侵犯了作者的权益，麻烦告知一下，我立刻给删除

关键词：交换，跳跃，分治

交换：同冒泡排序一样，都是基于交换的一种排序方式。

跳跃：相比冒泡排序相邻的数之间的交换，快速排序的交换是跳跃式的，交换的距离比冒泡排序要大

分治：采用分治的思想。将整体分而治之。

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N2)，它的平均时间复杂度为 O (NlogN)。其实快速排序是基于一种叫做“二分”的思想。

    private void quickSort(int[] pInts, int pLeft, int pRight) {

        int i, j, temp;

        if (pLeft >= pRight) {
            return;
        }

        i = pLeft;
        j = pRight;

        // 记录基准数
        temp = pInts[pLeft];

        // 如果i!=j，表示两个探针还没有相遇，还没有找到基准数将要归位的位置索引
        while (i != j) {

            // 向左探查，直到找到小于基准值的数后才停止
            while (pInts[j] >= temp && i < j) {
                j--;
            }

            // 向右探查，直到找到大于基准值的数后才停止
            while (pInts[i] <= temp && i < j) {
                i++;
            }

            // 交换两个位置的数值
            if (i < j) {
                swap(pInts, i, j);
            }
        }

        // 如果执行到这里，就表示两个探针已经相遇，且找到基准书将要归位的位置索引
        // 将当前位置的数值和基准值交换
        pInts[pLeft]=pInts[i];
        pInts[i]=temp;

        quickSort(pInts, pLeft, i - 1);
        quickSort(pInts, i + 1, pRight);
    }

    private void swap(int[] pArr, int a, int b) {
        pArr[a] = pArr[a] + pArr[b];
        pArr[b] = pArr[a] - pArr[b];
        pArr[a] = pArr[a] - pArr[b];
    }