四个时间复杂度为nlogn的排序算法

三个n^2级的算法http://t.csdnimg.cn/oQSSL

 本周分享四个时间复杂度为nlogn的算法：

1. 希尔排序
2. 堆排序
3. 快速排序
4. 归并排序

1.希尔排序

1959 年 7 月，美国辛辛那提大学的数学系博士 Donald Shell 在 《ACM 通讯》上发表了希尔排序算法，成为首批将时间复杂度降到 O(n^2) 以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是 O(n^2) ，但经过优化的希尔排序可以达到 O(n^{1.3}) 甚至 O(n^{7/6})。

希尔排序虽然现在用到的地方很少，但之所以仍然讲解，是因为理解了希尔排序之后，能够快速地其他排序算法（学习本质上是对思维的锻炼，而不是具体的知识）；

希尔排序本质上是对插入排序的一种优化，将插入排序从相邻元素的交换改变成特定下标的元素交换。它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。从本质上来说希尔排序是特定间隔的多次插入排序。

基本思想

● 将待排序数组按照一定的间隔分为多个子数组，对每组分别进行插入排序。（间隔分组不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组，而我们的插入排序也是对这一个间隔数组进行的插入排序）

● 逐渐缩小间隔进行下一轮排序

● 最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的基本排序之后，此时数组基本有序了，所以此时的插入排序只需进行少量交换便可完成

举个例子，对数组 [84, 83, 88, 87, 61, 50, 70, 60, 80, 99] 进行希尔排序的过程如下：

● 第一遍（55 间隔排序）：按照间隔 55 分割子数组，共分成五组，分别是 [84,50],[83,70],[88,60],[87,80],[61,99]。对它们进行插入排序，排序后它们分别变成： [50, 84], [70, 83], [60, 88], [80, 87], [61, 99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]

● 第二遍（22 间隔排序）：按照间隔 22 分割子数组，共分成两组，分别是 [50, 60, 61, 83, 87], [70, 80, 84, 88, 99]。对他们进行插入排序，排序后它们分别变成： [50, 60, 61, 83, 87], [70, 80, 84, 88, 99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]。这里有一个非常重要的性质：当我们完成 22 间隔排序后，这个数组仍然是保持 55 间隔有序的。也就是说，更小间隔的排序能够不断地将上一次排序的结果进行优化，使数组逐渐回归有序

● 第三遍（11 间隔排序，等于直接插入排序）：按照间隔 11 分割子数组，分成一组，也就是整个数组。对其进行插入排序，经过前两遍排序，数组已经基本有序了，所以这一步只需经过少量交换即可完成排序。排序后数组变成 [50,60,61,70,80,83,84,87,88,99]，整个排序完成。

代码实现

    public static void shellSort01(int[] nums) {
        //确定间隔系列 即希尔增量序列，这里是数组长度不断除以2，直到间隔为1，进行一个整体的插入排序;
        for (int gap = nums.length / 2; gap >= 1; gap = gap / 2) {
            //使用插入排序中的位移法对每一分组进行排序;
            //插入排序的起始位置是gap,即从第一个间隔后面的元素开始,向前进行的插入排序;
            for (int currentIndex = gap; currentIndex < nums.length; currentIndex++) {
                int currentValue = nums[currentIndex];
                int preIndex = currentIndex - gap;//通过当前的指向的下标，获取同一组（gap间隔）的元素下标
                //只要当前下标currentIndex的前一个间隔下标preIndex大于等于0并且前一个下标的元素大于当前元素，才进行位移的操作，为当前currentIndex下标指向的元素寻找合适的位置
                while (preIndex >= 0 && nums[preIndex] > currentValue) {
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                //这里使用preIndex+gap的原因是:如果没有进入上方的while循环，preIndex+gap = currentIndex
                //如果进入了while循环，while循环都会执行preIndex-=gap的操作，这时候导致我们的下标指向了前一个间隔的函数，这时候我们需要向后移动一个间隔，指向正确的插入位置
                nums[preIndex + gap] = currentValue;
            }
        }
    }

分析

每一遍排序的间隔在希尔排序中被称之为增量，所有的增量组成的序列称之为增量序列，也就是本例中的 [5, 2, 1]。增量依次递减，最后一个增量必须为 1，所以希尔排序又被称之为「缩小增量排序」。这里的增量序列选取是通过数组长度/2，之后在这基础上不断除以2。

增量序列的选定会极大地影响希尔排序的效率。增量序列如果选得不好，希尔排序的效率可能比插入排序效率还要低，举个例子：

像这一个例子，以8、4、2为间隔的排序都没有起作用，真正对起作用的是1间隔的排序，这时候的时间复杂度要大于直接使用插入排序的时间复杂度。

原因就在于，我们选择的增量序列之间存在着公因子，不互相为质数，这样导致小的增量根本不起作用，在排序时出现一些不必要的重复操作，从而影响排序算法的性能。

一般来说，为了保证希尔排序的效率，我们希望选择的增量序列中的元素是互质的，这样可以最大程度地减少不必要的比较和交换操作，提高排序的效率。

代码优化

这里推荐增量选取使用 knuth 增量序列：D_1 = 1; D_{k+1} = 3 * D_k + 1，也就是 1,4,13,40,...，数学界猜想它的平均时间复杂度为 O(n^{3/2})；

使用 Knuth 序列进行希尔排序的代码如下：

    public static void shellSortByKnuth(int[] arr) {
        // 找到当前数组需要用到的 Knuth 序列中的最大值
        int maxKnuthNumber = 1;
        while (maxKnuthNumber <= arr.length / 3) {
            maxKnuthNumber = maxKnuthNumber * 3 + 1;
        }
        // 增量按照 Knuth 序列规则依次递减
        for (int gap = maxKnuthNumber; gap > 0; gap = (gap - 1) / 3) {
            // 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
            for (int i = gap; i < arr.length; i++) {
                // currentNumber 站起来，开始找位置
                int currentNumber = arr[i];
                // 该组前一个数字的索引
                int preIndex = i - gap;
                while (preIndex >= 0 && currentNumber < arr[preIndex]) {
                    // 向后挪位置
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                // currentNumber 找到了自己的位置，坐下
                arr[preIndex + gap] = currentNumber;
            }
        }
    }

时间-空间复杂度分析

时间复杂度分析：希尔排序时间复杂度非常难以分析，它的平均复杂度界于 O(n) 到 O(n^2) 之间，普遍认为它最好的时间复杂度为 O(n^{1.3})。不同的增量序列会有不同的时间复杂度。

空间复杂度：采用的都是常数级的临时变量，所以空间复杂度为O（1）

堆排序

前置知识

堆：符合以下两个条件之一的完全二叉树：

● 根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；

● 根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆。

完全二叉树：

若一棵二叉树的所有叶子节点都在最后一层或者倒数第二层，并且最后一层的叶子节点左边连续，倒数第二层的叶子节点右边连续，则我们称此二叉树为完全二叉树。

●   对于完全二叉树中的第 i 个数，它的左子节点下标：left = 2i + 1

●   对于完全二叉树中的第 i 个数，它的右子节点下标：right = left + 1

●   对于有 n 个元素的完全二叉树(n≥2)(n≥2)，它的最后一个非叶子结点的下标：n/2 - 1（n为对应数组的长度）

基本思想

1. 用数组构建出一个大顶堆，取出堆顶的数字；

2. 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；

3. 循环往复，完成整个排序。

堆排序并不是使用二叉树进行排序，而是在使用数组去模拟二叉树的结构，是一些特定的数组范围进行排序。

构建大顶堆的过程是很多初学者不明白的，其实大顶堆的构建非常简单，我们可以将这个数组的初始状态看成是一个完全二叉树，从最后一个非叶子节点开始自下而上地构建大顶堆，当我们依次向上将每一个子树都构建成大顶堆，构建到根节点的时候，数组最终形成了一个大顶堆结构。

如图所示，我们构建以3为根节点的大顶堆，再构建以2为根节点的大顶堆，最后构建以1为节点的大顶堆。其实，这一个过程就是我们的基本思想中第二步，调整剩余数组，重新构建大顶堆。值得注意的是，我们在进行大顶堆构架的时候，一定要注意交换元素后的对于其左右子树的影响，一定要保持住大顶堆的结构。

动图演示如下：

代码实现

public class heapSortDemo {
    public static void main(String[] args) {
        int[] nums = {5, 0, 1, 9};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
 
    public static void heapSort(int[] nums) {
//        1.构建大顶堆
        constructMaxHeap(nums);
/*        2.大顶堆构建完成，之后将堆顶元素依次同末尾元素进行交换即可。
            注意：一旦发生了交换，构建大堆顶一定是有范围的，不再是全体数组了,不然永远都是值比较大的元素同其叶子节点的元素进行交换;*/
        for (int i = nums.length - 1; i >= 0; i--) {
            swap(nums, 0, i);
            maxHeapify(nums, 0, i);
        }
    }
 
    /**
     * 构建堆的过程就是实现一个特定结构的降序排列 类似于希尔排序
     * 我们采用自下而上的构建方式，从二叉树的最后一个非叶子节点开始构建
     * 构建的过程注意，后一次元素交换后，对于其叶子节点的影响，要同叶子节点进行比较。
     */
    public static void constructMaxHeap(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, i, nums.length);
        }
    }
 
    /**
     * 堆中每一个节点的初始化操作，以节点、子树为单位堆的构建。
     * 这是一个根据当前的节点，构建最大堆的方法
     * @param nums         待排序的数组
     * @param currentIndex 当前构建堆的下标
     * @param heapSize     本次排序的数组范围
     */
    public static void maxHeapify(int[] nums, int currentIndex, int heapSize) {
        int leftIndex = 2 * currentIndex + 1;
        int rightIndex = 2 * currentIndex + 2;
 
        // 记录根结点、左子树结点、右子树结点三者中的最大值下标
        int largest = currentIndex;
        // 与左子树结点比较
        if (leftIndex < heapSize && nums[leftIndex] > nums[largest]) {
            largest = leftIndex;
        }
        // 与右子树结点比较
        if (rightIndex < heapSize && nums[rightIndex] > nums[largest]) {
            largest = rightIndex;
        }
        if (largest != currentIndex) {
            // 将最大值交换为根结点
            swap(nums, currentIndex, largest);
            // 再次调整交换数字后的大顶堆
            maxHeapify(nums, largest, heapSize);
        }
    }
 
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

分析

大顶堆构建完成之后，堆顶元素同末尾元素的交换，一定要进行数组范围的缩减，这里是使用heapSize进行控制的。

时间-空间复杂度

堆排序总的时间复杂度为 O(nlog⁡n)。

堆排序的空间复杂度为 O(1)，只需要常数级的临时变量。

堆排序和选择排序一样，是对数组进行部分排序，每次排好一个最大值或者最小值。适合寻找第几大的值这样的算法。

快速排序

快速排序算法由 C. A. R. Hoare 在 1960 年提出。它的时间复杂度也是 O(nlogn)，但它在时间复杂度为 O(nlogn) 级的几种排序算法中，大多数情况下效率更高，所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用，使得快速排序深受面试官的青睐，所以掌握快速排序的思想尤为重要。

基本思想

1. 从数组中取出一个数，称之为基数（pivot）

2. 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域

3. 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

pivot中文意思是轴，每一次数组的遍历就是把基数左边的数字大于基数的数字，旋转到右边；把基数右边小于基数的数字旋转到左边，形成一个基数左边都小于等于基数，右边都大于基数的数组结构。【pivot的选取是快速排序算法的核心，快速排序算法的优化也都大都围绕着pivot轴的选取和pivot的增加进行。所谓双轴快排就是一次选取两个基数，将数组分为三个区域进行旋转】

对于pivot轴的选择：

基数的选择没有固定标准，随意选择区间内任何一个数字做基数都可以。

通常来讲有三种选择方式：

● 选择第一个元素作为基数 【入门推荐，方便理解，本文依次为例】

● 选择最后一个元素作为基数

● 选择区间内一个随机元素作为基数 【优化推荐，降低最坏情况出现的概率】

代码实现

public class quickSortDemo {
    public static void main(String[] args) {
        int[] nums = {6, 2, 1, 3, 5, 5, 1, 4};
        //  为了方便调用，书写的重载方法
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
 
    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }
 
    public static void quickSort(int[] nums, int start, int end) {
        //什么时候退出递归，当本次快速排序的数组元素个数为0或者为1的时候，文章下方有解释
        if (start >= end) return;
        int middle = partitionRandom(nums, start, end);
        quickSort(nums, start, middle - 1);
        quickSort(nums, middle + 1, end);
    }
 
    // 将 待排序数组arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
    public static int partition(int[] arr, int start, int end) {
        // 取第一个数为基数
        int pivot = arr[start];
        // 从第二个数开始分区,左边界
        int left = start + 1;
        // 右边界
        int right = end;
        // left、right 相遇时退出循环
        while (left < right) {
            // 找到第一个大于基数的位置
            while (left < right && arr[left] <= pivot) left++;
            // 交换这两个数，使得左边分区都小于或等于基数，右边分区大于基数
            //这里会出现left和right相等的情况，上面的while循环导致的,这里我们不对这种情况进行判断
            if (left != right) {
                swap(arr, left, right);
                right--;
            }
        }
        // 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
        // 如果arr[right] > pivot 的话，我们需要让right--，直接进行交换的话，会导致交换后的左区第一个数大于pivot,
        // 而right--后的元素一定是小于pivot的，这是我们之前遍历过的。
        //如果arr[right] <= pivot 的话，我们可以直接交换操作
        if (left == right && arr[right] > pivot) right--;
        // 将基数和中间数交换,如果到头了，就不需要交换，此时start(pivot)右边的数全部大于pivot
        if (right != start) swap(arr, start, right);
        // 返回中间值的下标
        return right;
    }
 
}

分析

对于递归退出的边界，这里为什么是start >= end呢？

递归的数组元素个数为0或者为1的时候退出递归。因为这时候进行任何排序都是没有任何意义的。最原始的条件应该是下方代码这样的。

    public static void quickSort(int[] nums, int start, int end) {
        int middle = partitionRandom(nums, start, end);
         // 当左边区域中至少有 2 个数字时，对左边区域快速排序
        if(start != middle && start != middle-1) quickSort(nums, start, middle - 1);
         // 当右边区域中至少有 2 个数字时，对右边区域快速排序
        if(end != middle+1 && end != middle) quickSort(nums, middle + 1, end);
    }

我们对边界进行简化：

• 当进行左边区域的递归时

如果start == middle 表示将要递归的数组范围内元素的个数为0；

如果start == middle-1表示将要递归的数组范围内元素的个数为1 ；

我们带着这样的条件进入递归中，可以得出start和end的关系

当start == middle时，进行递归后，start=start,middle-1=end---> start = end+1;

当start == middle-1时，进入递归后，start=start,end=middle-1--->start = end;

• 当进行右边区域的递归时

如果end == middle 表示将要递归的数组范围内元素的个数为0；

如果end == middle+1 表示将要递归的数组范围内元素的个数为1；

我们带着这样的条件进入递归中，可以得出start和end的关系

当end== middle时，进行递归后，start=middle+1,end=end---> start = end+1;

当end == middle+1时，进入递归后，start=middle+1,end=end--->start = end;

综上所述，进入递归后的终止条件可以改变成 start！=end || start！=end+1。

根据我们的程序设定，middle>=start&&middle<=end一定成立,除了start==end||start==end+1外，其他情况下start都小于end,所以我们可以将这一个判断条件再次改为，只要left>=right就退出递归。由于我们是在下一次递归中进行这一系列的推理。递归的终止条条件应该放到partition前面，递归退出的条件改变为

● start == end: 表明区域内只有一个数字
● start == end + 1: 表明区域内一个数字也没有，

public static void quickSort(int[] arr, int start, int end) {
    // 如果区域内的数字少于 2 个，退出递归
    if (start >= end) return;
    // 将数组分区，并获得中间值的下标
    int middle = partition(arr, start, end);
    // 对左边区域快速排序
    quickSort(arr, start, middle - 1);
    // 对右边区域快速排序
    quickSort(arr, middle + 1, end);
}

优化

双指针分区算法

    public static int doublePointerPartition1(int[] arr, int start, int end) {
        int pivot = arr[start];
        int left = start + 1;
        int right = end;
 
        while (left <= right) {
            //从left开始寻找大于pivot的值
            while (left <= right && arr[left] < pivot) left++;
            //从right开始寻找大于pivot的值
            while (left <= right && arr[right] >= pivot) right--;
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        if (start != right)   swap(arr,start,right);
        return right;
    }

归并排序

1945 年，约翰·冯·诺伊曼提出了归并排序。归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。

基本思想

归并排序主要由两个环节组成：拆分-合并

拆分环节：将长度为n的数组不断进行拆分，直到拆分成长度为1的数组。

合并环节：将拆分成长度为1的数组不断地进行特定排序的合并，直到数组的长度为n。

为什么我们要将数组拆分成长度为1的数组才进行合并操作：

当我们将数组拆分成长度为1的数组，这时候就没有了有序无序的概念。这时候我们就可以将两个长度为1的数组合并成有序数组。

代码实现

public class MergerSortDemo {
    public static void main(String[] args) {
        int[] nums = new int[]{6, 2, 5, 9, 7, 1, 4, 8};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
    
    public static void mergeSort(int[] nums) {
        if (nums.length == 1) return;
        //我们将归并排序的结果返回成一个新的数组;
        int[] result = mergeSort(nums, 0, nums.length - 1);
        //通过for循环将排序好的结果赋值给原数组
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
    }
 
 
    private static int[] mergeSort(int[] nums, int start, int end) {
        //归并排序的终止条件是什么？本次拆分只有一个元素 [向下到底]
        if (start == end) return new int[]{nums[start]};
        int middle = (start + end) / 2;
        //向左进行分区递归
        int[] left = mergeSort(nums, start, middle);
        //向右进行分区递归
        int[] right = mergeSort(nums, middle + 1, end);
        //左右都分好了，进行合并的操作 [向上返回]
        return merge(left, right);
    }
 
    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int index1 = 0, index2 = 0;
        while (index1 < left.length && index2 < right.length) {
            if (left[index1] < right[index2]) result[index1 + index2] = left[index1++];
            else if (right[index2] < left[index1]) result[index1 + index2] = right[index2++];
        }
        while (index1 < left.length) result[index1 + index2] = left[index1++];
        while (index2 < right.length) result[index1 + index2] = right[index2++];
        return result;
    }
}

分析

数组的拆分和合并过程可以使用二叉树来进行模拟，我们的拆分过程是向下递归，我们的合并过程是向上返回。我们对数组的拆分顺序类似于二叉树的前序遍历，直到数组的能够并拆分成两个长度范围为1的左右区域时，我们才进行合并的操作。

优化

归并排序的优化体现在空间复杂度的优化上面。在上面的代码中，我们每一次递归都返回left或者right数组，不断地开辟空间。为了减少在递归过程中不断开辟空间的问题，我们可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可。

class UpdatedMergerSort {
    public static void main(String[] args) {
        int[] nums = new int[]{6, 2, 5, 9, 7, 1, 4, 8};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
 
    public static void mergeSort(int[] nums) {
            if (nums.length == 1) return;
            int[] result = new int[nums.length];
            mergeSort(nums, 0, nums.length - 1, result);
    }
 
    /**
     * 归并算法进行递归拆分的主要步骤:
     * @param nums   待排序数组
     * @param start  待排序数组起始
     * @param end    待排序数组结尾
     * @param result 多余空间，方便进行归并
     */
    private static void mergeSort(int[] nums, int start, int end, int[] result) {
        if (start == end) return;
        int middle = (start + end) / 2;
//        左边区域进行归并排序
        mergeSort(nums, start, middle, result);
//        右边区域进行归并排序
        mergeSort(nums, middle + 1, end, result);
        //对左区和右去的部分数组进行向上归并
        merge(nums, start, end, result);
        // 在合并操作之后,我们要对已经排好序的数组返回进行更新,不然会导致我们在利用本次排序的结果是出现错误。
        for (int i = start; i <= end; i++) {
            nums[i] = result[i];
        }
    }
 
    /**
     * 并排的核心算法,用于合并两个范围的元素合并成一个数组;
     *
     * @param nums   待排序数组
     * @param start  起始
     * @param end    终点
     * @param result 结果储存空间，用于存放数组
     *               1.未优化前是数组下标同数组的长度进行比较的。
     *               2.优化后数组下标同数组的下标进行比较的，所以这个时候需要在判断条件上加上==
     */
    private static void merge(int[] nums, int start, int end, int[] result) {
        int middle = (start + end) / 2;
        int start1 = start, end1 = middle;  // 左边数组的范围
        int start2 = middle + 1, end2 = end;// 右边数组的范围
        int index1 = start1,index2 = start2;// 左边右边数组的下标
        int index = start1;//result数组的下标
        while (index1 <= end1 && index2 <= end2){
            if (nums[index1] <= nums[index2]) result[index++] = nums[index1++];
            else if (nums[index2] < nums[index1]) result[index++] = nums[index2++];
        }
        while(index1 <= end1) result[index++] = nums[index1++];
        while(index2 <= end2) result[index++] = nums[index2++];
    }
}

时间复杂度 & 空间复杂度

归并排序的复杂度比较容易分析，拆分数组的过程中，会将数组拆分 logn 次，每层执行的比较次数都约等于 n 次，所以时间复杂度是 O(nlogn)。

空间复杂度是 O(n)，主要占用空间的就是我们在排序前创建的长度为 n的 result 数组。