快速排序

快数排序的平均时间复杂度是O(NlogN)，最坏时间复杂度是O(N2)，采用的也是一种分治思想，通常的快速排序的一个错误方法就是选择第一或者最后一个作为枢纽元，这种做法的错误的，如果原数组已经是有序数组，这样会产生最大的时间复杂度，这次介绍的快速排序算法，主要是对枢纽元的选择做了改进，叫做三数中值分割法，就是取原数组的首位，末位，还有中间的值，做一个相互比较，将最大的放在末尾，最小的放在首位，中间值作为枢纽元，下面从代码上分析：

private void quickSort(int[] oriArray, int left, int right) {
       //取得枢纽元
        int pivot = media3(oriArray, left, right);
        Log.e("AAA", "the left is  " + left);
        Log.e("AAA", "the right is  " + right);
        for (int k = left; k <= right; k++) {
            Log.e("AAA", "ori array " + k + " is " + oriArray[k]);
        }
       
       //由于数组的最大最小已经排序，枢纽元是在倒数第二位上，
       //所有从低端走的i是从left+1开始，从高端走的j是从right-2开始。
        int i = left + 1;
        int j = right - 2;
        if (j <= i){
            return;
        }
        for (; ; ) {
          //如果没有发现大于枢纽元的值，i就往上走，
            while (oriArray[i] < pivot) {
                i++;
            }
           //如果没有发现小于枢纽元的值，j就往下减
            while (oriArray[j] > pivot) {
                j--;
            }
           //如果停下来的时候发现i>j，那么直接跳出，否侧交换i和j的数值，然后i和
j继续走前面的流程。
            if (i < j) {
                swapReferences(oriArray, i, j);
            } else {
                break;
            }
        }
       //将 i的值与枢纽元交换
        swapReferences(oriArray, i, right - 1);
        for (int k = left; k <= right; k++) {
            Log.e("AAA", "after change ori array " + k + " is " + oriArray[k]);
        }
       //对分开的两部分递归调用
        quickSort(oriArray, left, i - 1);
        quickSort(oriArray, i + 1, right);
    }

    private int media3(int[] array, int left, int right) {
        int center = (left + right) / 2;
        if (array[center] < array[left]) {
            swapReferences(array, left, center);
        }

        if (array[right] < array[left]) {
            swapReferences(array, left, right);
        }

        if (array[right] < array[center]) {
            swapReferences(array, center, right);
        }
       //将枢纽元放在倒数第二位上
        swapReferences(array, center, right - 1);
        return array[right - 1];
    }

    private void swapReferences(int[] array, int oriIndex, int dstIndex) {
        int temp = array[oriIndex];
        array[oriIndex] = array[dstIndex];
        array[dstIndex] = temp;
    }