一、题目内容

二、题解

解法：

思路

要求一个空间复杂度O(n)，时间复杂度O(nlogn) 排序，其实就是非冒泡排序，可选堆排或者快排

代码

堆排

public static void heapSort(int[] a) {
        if (a == null || a.length == 1) {
            return;
        }
        //构建大顶堆
        int firstNotLeaf = a.length / 2 - 1;
        for (int i = firstNotLeaf; i >= 0; i--) {
            //从第一个非叶子节点开始，自下而上、自右向左 调整堆
            adjustMaxHeap(a, i, a.length);
        }
        //交换堆顶与末尾元素，并调整堆
        for (int j = a.length - 1; j >= 0; j--) {
            //交换
            int temp = a[0];
            a[0] = a[j];
            a[j] = temp;
            //交换过后调整堆
            adjustMaxHeap(a, 0, j);
        }
    }
    /**
     * 调整大顶堆，使当前数组生成的堆满足堆定义（大堆或者小堆）
     *
     * @param a
     * @param currPos
     * @param length
     */
    public static void adjustMaxHeap(int[] a, int currPos, int length) {
        int temp = a[currPos];
        //从当前位置的左子节点开始
        for (int k = currPos * 2 + 1; k < length; k = 2 * k + 1) {
            //左小于右，则将k移动到右子节点
            if (k + 1 < length && a[k] < a[k + 1]) {
                k++;
            }
            //判断当前节点与当前父节点值
            if (a[k] > temp) {
                a[currPos] = a[k];
                currPos = k;
            } else {
                break;
            }
        }
        //最后将temp会写到当前对应的正确位置
        a[currPos] = temp;
    }

快排

/**
     * 快速排序
     * 以左侧首位为target，进行左右比较、交换
     *
     * @param a
     * @param low
     * @param high
     */
    public static void quickSort(int[] a, int low, int high) {
        if (a == null || a.length == 1) {
            return;
        }

        int left, right;
        int target;
        if (low >= high) {
            return;
        }

        left = low;
        right = high;
        target = a[left];
        while (left < right) {
            //找到右侧第一个小于target
            while (left < right && a[right] > target) {
                right--;
            }
            if (left < right) {
                a[left] = a[right];
                left++;
            }

            //找到左侧第一个大于targe
            while (left < right && a[left] < target) {
                left++;
            }
            if (left < right) {
                a[right] = a[left];
                right--;
            }
        }
        //此时left左侧都比target小，右侧都比target大，targe为中心值
        a[left] = target;

        //递归
        quickSort(a, low, left - 1);
        quickSort(a, left + 1, high);
    }