排序算法总结

排序算法的总结。

总结

算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

复杂度

冒泡排序Bubble Sort

冒泡排序容易给人的误解是，「冒泡」意为着「上浮」，就是每次都把最小的排到水面最上面（即数组的最后面）。

其实不然，所谓的「冒泡」只是一种形象的比喻，让每一轮都有一个数字成为最大或最小的那一个并被排列到固定的一端，并依次缩小比较范围。所以需要两个指针来控制，第一个指针控制要比较-交换的轮次，第二个指针负责遍历当前轮次的有效数据范围内的数据。

如果想让最大的往右排，则需找到arr[i] > arr[i+1]并交换。

如果想让最小的往右排列，则需找到arr[i] < arr[i+1]并交换。

该算法的时间复杂度为 O(n2) ，使用双层 for 循环，外层控制控制冒泡次数，内层对未冒泡部分的数据依次进行比较&交换。特点如下：

一共冒泡 len - 1 次，最后一次时待比较集合只有一个元素，已经是排好序不用再比较
内层每一轮进行比较的元素依次减少，冒泡了几次就减少几次，这里用 len - 1 - i 来控制
交换不符合条件的相邻位置的元素，每一轮保证将最大或最小的元素「交换」到当前轮最后的位置

public static void bubbleSort(int arr[]){
    int n = arr.length;
    for (int i = 0; i < n - 1 ; i++) {
        boolean isSort = true;
        for (int j = 0; j < n - 1 - i ; j++) {
            int temp = 0;
            // 升序排列
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false;
            }
        }
        // 如果遍历了一圈发现没有交换过数据，证明已经有序直接返回
        if (isSort) { 
            break;
        }
    }
}

代码中对特殊情况「已经排好序的数组」进行了优化，如果任何一轮比较没有发现不符合条件的情况，则认为数组已经排序完毕。

因为冒泡排序每一轮都是从第一个位置（index=0）开始往后依次比较index和index+1位置的元素，并对符合条件的元素间进行交换位置，这样比较完毕一轮后，当前轮中最大的元素将置于当前轮元素集合序列的尾部（已经冒完泡的位置的集合）。

如果恰好待排序数组是降序排列好的，会导致每一轮的比较都会交换所有index和index+1位置的元素，效率最低。

选择排序Selection Sort

选择排序的思路是这样的：

首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置

第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置

如此循环，直到整个数组排序完成

特点如下：

一共选择 len - 1 次，最后一次时待比较集合只有一个元素，已经是排好序不用再比较
依次从第 i 下标位置的元素开始和后面的元素依次比较，找比它更小的元素，如果有，则交换数组中的位置
此时第 i 下标位置的数已经是当前待选择数据中最小的， i 递增，继续比较它后面的元素

每一轮比较的时间复杂度是 O(n) ，一共比较n - 1 次，所以时间复杂度为 O(n2) 。

public static void selectionSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        // 本轮最小元素的下标
        int min = i; 
        // 从后面依次对比找到最小的值的位置
        for (int j = i + 1; j < n ; j++) {
            if (arr[j] < arr[min]) {
                min = j; // 找最小值
            }
        }
        // 当前轮待更新的位置已经是所有后续中最小的，无需交换
        if (min != i) {
            // 交换位置
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

选择排序 和 冒泡排序 的不同是:

选择排序的每一轮最多只交换一次，而冒泡排序每一轮可能要交换len-1-i次，即第一个位置需要和后面所有位置都交换一遍

因为选择排序是选择（比较）完所有位置的最小（最大）位置后直接「一次性」交换，而冒泡排序是在比较的过程中就执行了交换赋值。但正因为如此，冒泡排序可以提前知道当前数组是否已经排好序，因为一旦未排好序就涉及到至少一次的交换，如果本轮未交换任何元素，则认为已经排好序，直接退出即可。而选择排序由于仅知道本轮的最小（最大）元素的位置，对其他元素之间的关系是不知道的，所以只能依次执行完全部轮次的选择比较&交换。

选择排序的每一轮需要比较完所有的未排序元素，而冒泡排序在上一轮全部比较完毕后如果未发生交换，则无需开始下轮的比较

插入排序Insertion Sort

插入排序的思想和我们打扑克摸牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。

那如果我们不是从牌堆里摸牌，而是左手里面初始化就是一堆乱牌呢？

一样的道理，我们把部分牌（n-1张）往手的右边挪一挪，左边只留下一张，然后在右边依次抽一张出来，插入到左边，

再抽一张出来，插入到左边，再抽一张，插入到左边，每次插入都插入到左边合适的位置（伴随着不符合条件的数字的向右移动），时刻保持左边的牌是有序的，直到右边的牌抽完，则排序完毕。

public static void insertionSort(int[] arr) {
    int n = arr.length;
    // 直接从第二位置的数据开始与其前面的集合倒序比较，所谓的插入是插入一个已经存在的集合（最小长度为1）中
    for (int i = 1; i < n; ++i) {
        // 保存当前待插入集合中的数据
        int value = arr[i];
        // 保存单签待插入数据的前一个位置
        int j = i - 1; 
        // 倒序与待插入位置元素之前的元素进行比较，找到最适合value的位置
        for (; j >= 0; j--) {
            // 如果小于则腾出该位置
            if (arr[j] > value) {
                // 将j位置的数据向后一位赋值，给i位置数据留出位置
                arr[j + 1] = arr[j]; 
            } else {
                // 退出，前面的已经是排好序的了
                break; 
            }
        }
        // 插入本轮待比较数据到最合适的位置，如果该位置未改变，则无需移动
        if (j + 1 != i) {
            // 此时j+1和j+2的值是一样的，因为j+1位置的元素刚移动到了j+2位置
            arr[j + 1] = value;     
        }
    }
}

最好情况的时间复杂度是 O(n)，即数组已经排好序了，经过一轮比较即可。最坏情况的时间复杂度是 O(n2)，然而时间复杂度这个指标看的是最坏的情况，而不是最好的情况，所以插入排序的时间复杂度是 O(n2)。

插入排序区别于冒泡和选择排序的一个显著特征是：

前者每轮的比较次数是依次增大的，并且比较是从后往前依次比较，每一轮的结果保证此轮所有待排序元素是排好序的
后者两个每轮的比较次数是依次减少的，并且比较是从前往后依次比较，每一轮的结果保证此轮所有待排序元素范围「之后的」数据是排好序的，如冒泡排序是「尾部」是已经排好序的，只需要调整「头部」，而插入排序是「头部」是已经排好序的，需要通过尾部的新元素继续调整「头部」。

同样，插入排序也可以进行优化，即第一次比较待插入元素和前一个j位置的元素时，如果不满足条件，如待插入元素比前一个元素大，说明已经无需比较和j-1之间的关系了，因为前面已经排好序了，直接从下轮开始。

插入排序可以理解为每一轮待比较的元素已经知道了明处的牌（即头部已经排好序的部分），但是不知道暗处的牌，即它后面的部分的数据，所以每次只能将自己和明处的牌进行比较和排序，不知道全局的情况，全局的情况只能等最后一个元素处理完才知道。

冒泡排序是每一轮都知道明处的牌（即尾部已经排好序的，不可能再改变位置的元素），还有暗处的牌（即尾部前面所有的元素），每一轮都要和这些所有元素进行比较，即每一轮都知道当前全局是否已经有序。

选择排序更像是选美，一开始就选谁最美，然后依次选择第二第三美的。。，所以每轮确定的是余留的下一个位置，具体的人不确定需要每次都从剩下的人堆里选择。每一轮都要比较未排位的人，交换只要一次。

希尔排序Shell’s Sort

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为「缩小增量排序」。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。

而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。

希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2 ，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1} ，称为 增量序列 。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为「希尔增量」，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

public class ShellSort {

    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static void sortBySwap(int []arr){
        // 增量gap，并逐步缩小增量
       for(int gap = arr.length / 2; gap > 0; gap /= 2){
           // 从第gap个元素开始，逐个对每个元素以及其所在组中的数据进行直接插入排序操作
           for(int i = gap; i < arr.length; i++){
               int j = i;
               // 依次从后向前做比较，把后面的小元素移动到前面的位置
               // 不满足时直接退出，说明前面的元素已经排好序了
               while(j - gap >= 0 && arr[j] < arr[j - gap]){
                   // 插入排序采用交换法
                   swap(arr, j, j - gap);
                   j -= gap;
               }
           }
       }
    }

    public static void swap(int []arr, int a, int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }
    
    
    /**
     * 希尔排序 针对有序序列在插入时采用移动法。
     * @param arr
     */
    public static void sortByMove(int []arr){
        // 增量gap，并逐步缩小增量
        for(int gap = arr.length/2; gap > 0; gap /= 2){
           // 从第gap个元素开始，逐个对每个元素以及其所在组中的数据进行直接插入排序操作
            for(int i = gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j - gap]){
                    while(j - gap >= 0 && temp < arr[j - gap]){
                        //移动法，减少交换法中的赋值操作
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    
}

上面实现了两种方法，一种是基于交换的，交换次数较多会影响性能，如最小的元素刚好在最后，需要不断的根据gap来移动到最前边；一种是基于先移动最后再赋值到最佳位置的，后者比前者少了交换中的计算量。

快速排序Quick Sort

快速排序的核心思想是「分治法」，分而治之，即将一个大问题分割为若干个小问题，每个小问题依次解决后大问题就自然求解。

它的实现方式是每次从序列中选出一个基准值pivot，其他数依次和基准值做比较，

比基准值大的放在pivot右边，比基准值小的放pivot左边，然后再对左边和右边的两组数分别按照相同的思路处理，重复步骤，

直到最后一轮时的pivot两侧的数组都是单个元素时，整个数组也就成了有序的序列。

快速排序使用「分治法」，其中使用了「递归」的思想：

跳出条件是 endIndex <= startIndex，此时已经无需再比较（和移动），因为待排序集合只有一个元素了
执行逻辑：在当前数据范围内找到一个 pivot ，以该点为中心， pivot 怎么选呢？比如以第一个位置的元素当做基准数，然后分别用两个指针在最左侧和最右侧依次向中间的方向寻找第一个大于或小于 pivot 的数的下标。如果找到则将两个位置的数据进行交换，保证排序的规则，然后继续让两个指针按照原来的方向继续寻找，一直到两个指针相遇，则相遇位置即为当前轮次的pivot位置元素需要放到的位置，此时其他所有位置都满足pivot左侧小于它右侧大于它，所以全局层面pivot位置的元素的位置已经确定了。剩下的左右两侧的元素集合继续按照这个思路继续处理即可。

// 递归处理，因为每一次处理的元素的范围不同，则最好定义一个新的方法增加下标参数
// 但注意arr的引用一直都没有变，即内存地址一直没有变，变的是内存地址内数组元素位置和值
public static void quickSort(int[] arr) {
    quickSort0(arr, 0, arr.length - 1);
}

private static void quickSort0(int[] arr, int startIndex, int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    // 切分点计算
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 分治divide
    quickSort0(arr, startIndex, pivotIndex - 1);
    quickSort0(arr, pivotIndex + 1, endIndex);
}


private static int partition(int[] arr, int low, int high) {
    int left = low;
    int right = high;
    int pivot = arr[low]; // 取第一个元素为基准值

    while (true) {
        // 从左往右扫描，找到比pivot大的则退出
        while (arr[left] <= pivot) {
            left++;
            if (left == right) {
                break;
            }
        }

        // 从右往左扫描，找到比pivot小于等于的则退出
        while (pivot < arr[right]) {
            right--;
            if (left == right) {
                break;
            }
        }

        // 左右指针相遇
        if (left >= right) {
            break;
        }

        // 交换左右指针下标对应的数据，使得满足左小于右大于pivot
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    // 将基准值插入序列
    int temp = arr[low];
    arr[low] = arr[right];
    arr[right] = temp;
    return right;
}

传统的 C 语言版的实现：

void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int i = low;
        int j = high;
        /*默认使用最低位的元素作为比较值*/
        int k = arr[low]; 
        while (i < j)
        {
            /*从右向左找第一个小于k的数*/
            while(i < j && arr[j] >= k)     
            {
                j--;
            }
 
            if(i < j)
            {
                arr[i++] = arr[j];
            }
 
            /*从左向右找第一个大于等于k的数*/
            while(i < j && arr[i] < k)      
            {
                i++;
            }
 
            if(i < j)
            {
                arr[j--] = arr[i];
            }
        }
        
        /*将pivot值赋值到i位置，此时i==j*/
        arr[i] = k; 
 
        /*递归调用*/
        /*排序k左边*/
        QuickSort(arr, low, i - 1);     
        /*排序k右边*/
        QuickSort(arr, i + 1, high);    
    }
}

C语言和Java语言的实现在交换i和j位置数据的时候有一点点不一样，C是按照一个方向判断，如果不满足则直接保存到另外一侧，但保留当前位置等待另外一侧不满足的赋值过来。 Java版本的是直接找到两侧不满足条件的位置后，直接进行i和j位置的交换，本质上和C算法是一样的。

极端情况

快速排序的时间复杂度和归并排序一样，O(nlog n)，但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，比如排一个有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，选取基准值 9 ，那么需要切分 n - 1 次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了 O(n2)，当然极端情况出现的概率也是比较低的。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。若直接选择第一个或最后一个数据作为分区点，不考虑数据的特点，肯定就会出现最坏情况的时间复杂度。

所以说，快速排序的时间复杂度是 O(nlogn)，极端情况下会退化成 O(n2)，为了避免极端情况的发生，选取基准值应该做到随机选取，或者是打乱一下数组再选取。

另外，快速排序的空间复杂度为 O(1)。

权衡

实际排序程序会采用多种算法的组合，即混成方法。在一些复杂排序算法里，也需要处理较短序列的排序问题。快排和归并排序就是这方面的典型：

快速排序算法中，序列被划分为越来越短的片段。若序列已经很短，例如短于几个元素，快排还需要做几次递归调用（进栈、出栈）。这些赋值操作很耗时，表现在复杂度描述中忽略了的常量因子。对于很短的序列，采用插入排序，效果很可能优于快速排序。
归并排序正好与快排相反，是从短的有序序列归并出越来越长的序列。从很多个各自包含一个元素的序列出发，通过几遍归并得到最终的有序序列，这其中需要做许多函数调用工作。与这几个元素做简单插入排序相比，归并排序消耗时间会更多。

在实际程序里的排序功能，特别是各自程序库里的排序函数，通常不是纯粹第采用一种算法，而是使用两种或两种以上方法的组合。

常见的是归并排序和插入排序的组合，以及快速排序和插入排序的组合。

堆排序Heap Sort

堆(heap)又被为优先队列(Priority Queue)。尽管名为优先队列，但堆并不是队列。

因为队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。

而堆虽然在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的(即建立堆的过程就是选择目前数据集合中的下一个有序数的过程)。

堆的一个经典的实现是完全二叉树(Complete Binary Tree)，这样实现的堆称为二叉堆(Binary Heap)。这里来说明一下满二叉树的概念与完全二叉树的概念：

满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树
完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧

堆的特性：

必须是完全二叉树
任一结点的值是其子树所有结点的最大值或最小值

本文以大顶堆为例介绍：

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一

构造初始堆。将给定无序序列构造成一个大顶堆（一般升序排列数组使用大顶堆的方式，顶端元素每次都是当前最大的，已出堆中最小的)。

步骤二

将堆顶元素与末尾元素进行交换，使末尾元素最大，并调整末尾的指针向前移动一个位置。然后继续调整堆：将新的堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

public static void heapSort(int[] arr) {
    int totalLength = arr.length;
    // 构建堆
    buildHeap(arr, totalLength);
    int newLength = totalLength;
    for ( int i = totalLength - 1; i > 0; i-- ) {
        // 将堆顶元素（当前堆中最大）与当前堆末尾元素调换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 新堆数组长度-1 隐藏全局数组尾部已全局有序元素
        newLength--;
        // 新的堆不满足条件，需要将「堆顶元素」下沉，将该节点下的最大值调整到堆顶上来
        sink(arr, 0, newLength); // length用于控制每一轮调整堆结构时排除的部分的边界，即已有序部分不参与堆的重建
    }
}

// 对已有数组arr或者说是「无序堆」进行构建大顶堆结构
private static void buildHeap(int[] arr, int length) {
    // 从第一个非叶子节点开始调整，即length/2 - 1的位置开始调整子堆，调整完毕后，继续调整每个小于i的位置的子堆结构
    // 注意因为堆是完全二叉树，所以一定满足i--后的位置一定是非叶子节点
    // Q:为什么第一次建堆需要从第一个非叶子节点开始依次调整每一个子堆，而后续交换堆顶元素后可以直接从堆顶位置开始调整？
    // A:因为之前的子堆已经建立好了堆结构，只需从第一个子节点开始调整
    for (int i = length / 2 - 1; i >= 0; i--) {
        sink(arr, i, length);
    }
}

// 下沉调整，如果调整后下一层仍不满足条件则继续调整，一直递归处理
private static void sink(int[] arr, int index, int length) {
    int leftChild = 2 * index + 1; // 左子节点下标
    int rightChild = 2 * index + 2; // 右子节点下标
    int sinkMe = index; //要调整的节点下标

    // 下沉到左边
    if (leftChild < length && arr[leftChild] > arr[sinkMe]) {
        sinkMe = leftChild;
    }

    // 如果右边更大，则改为下沉到右边，即让左右孩子中最大的往上浮
    if (rightChild < length && arr[rightChild] > arr[sinkMe]) {
        sinkMe = rightChild;
    }

    // 如果下标不相等了，证明index需要和sinkMe位置的孩子进行交换
    if (sinkMe != index) {
        // 交换值
        int temp = arr[index];
        arr[index] = arr[sinkMe];
        arr[sinkMe] = temp;

        // sinkMe此时已经下沉，从该节点开始继续处理下沉逻辑，递归
        sink(arr, sinkMe, length); // 递归
    }
    // 如果相同，则证明已经满足节点是左右子树中最大的节点值，退出
}

再简单总结下堆排序的基本思路：

　a.将无序序列构建成一个堆，根据是得到升序or降序结果集的需求选择使用大顶堆或小顶堆;

　b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

　c.重新调整（不包括移除的元素集合）结构，使其满足堆定义，然后继续交换堆顶元素与当前轮末尾元素，反复执行调整+交换步骤，直到整个序列有序。

复杂度

堆排序是一种选择排序，整体主要由「构建初始堆（当前轮集合）」+「交换堆顶元素和末尾元素（当前轮最后一个位置）并重建堆」两部分组成。

其中构建初始堆经推导复杂度为 O(n) ，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2).. .1]逐步递减，近似为 nlogn 。所以堆排序时间复杂度一般认为就是 O(nlogn) 级。

对于有 n 个节点的堆来说，其高度 d = log2n + 1。根为第 0 层，则第 i 层结点个数为 2i，考虑一个元素在堆中向下移动的距离：

大约一半的结点深度为 d-1 ，不移动(叶)
四分之一的结点深度为 d-2 ，而它们至多能向下移动一层
树中每向上一层，结点的数目为前一层的一半，而子树高度加一

堆有 logn 层深，所以插入、删除的平均时间和最差时间都是 O(logn) 。

public class MinHeap <E extends Comparable<E>> {
    private ArrayList<E> data;

    public MinHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }

    public MinHeap() {
        data = new ArrayList<>();
    }

    // 返回堆中的元素个数
    public int size() {
        return data.size();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    public int parent(int i) {
        return (i -1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    public int leftChild(int i) {
        return i * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    public int rightChild(int i) {
        return i * 2 + 2;
    }

    public void swap(int i, int j) {
        if (i < 0 || i >= size() || j < 0 || j >= size())
            throw new IllegalArgumentException("Index is illegal.");

        E temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    public void add(E e) {
        // 特性1：新插入的元素首先放在数组最后，保持完全二叉树的特性
        data.add(e);
        siftUp(data.size() - 1);
    }

    private void siftUp(int i) {
        // 特性2：比较插入值和其父结点的大小关系，小于父结点则用父结点替换当前值，index位置上升为父结点
        // 当上浮元素大于父亲，继续上浮。并且不能上浮到0之上
        // 直到i 等于 0 或 比 父亲节点小了。
        while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {
            // 数组Array中添加方法swap
            this.swap(i, parent(i));
            i = parent(i); // 这句话让i来到新的位置，使得循环可以查看新的位置是否还要大。
        }
    }

    public E findMin() {
        return data.get(0);
    }

    public E extratMin() {
        E ret = findMin();
        swap(0, size() - 1); // 0位置元素和最后一个元素互换。
        data.remove(size() - 1); // 删除此时的最后一个元素(最小值)
        siftDown(0); // 对于0处进行siftDown操作
        return ret;
    }

    // k位置元素下移
    private void siftDown(int k) {
        while (leftChild(k) < size()) {
            int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
            if (j + 1 < size() && data.get(j + 1).compareTo(data.get(j)) < 0) {
                j ++;
                // data[j] 是 leftChild 和 rightChild 中的最小值
                // 该值将和data[k]进行比较，保证每次交换都是交换当前最小的子节点
            }
            if (data.get(j).compareTo(data.get(k)) >= 0) {
                // 如果parent已经小于最小值，则直接退出
                break;
            }
            // 否则交换k和j的数据
            swap(k, j);
            // 让k从j的位置继续和子节点去比较
            k = j;
        }
    }
}

归并排序Merge Sort

归并字面上的意思是「合并」，归并算法的核心思想是「分治法」，将已有序的子序列合并，并依次得到更大的序列，最终得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为「二路归并」。

先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用merge函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序；

Recursively decompose problem until it is small enough for sequential

基本步骤：

1、判断参数的有效性，也就是递归的出口，即当只有一个元素时；
2、否则，直接把当前数组平分成两个子数组；
3、递归调用本函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；
4、然后调用排序函数，把两个有序的数组合并成一个有序的数组；
5、排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中；

public static void mergeSort(int[] arr) {
    int[] tempArr = new int[arr.length]; // 初始化临时变量，全局共享
    mergeSort0(arr,  tempArr,  0,  arr.length-1);
}

/**
 * 归并排序，将arr数组中从startIndex到endIndex部分的数据进行排序
 * @param arr 排序数组
 * @param tempArr 临时存储数组
 * @param startIndex 排序起始位置
 * @param endIndex 排序终止位置
 */
private static void mergeSort0(int[] arr, int[] tempArr, int startIndex, int endIndex){
    // 退出条件，左右指针相逢，待合并数组只有一个元素
    if(endIndex <= startIndex){ 
        return;
    }
    // 二路归并，计算中部下标
    int middleIndex = startIndex + (endIndex - startIndex) / 2; // 注意防止溢出

    // divide
    // 分解为左右两部分并各自进行递归排序
    mergeSort0(arr, tempArr, startIndex, middleIndex);
    mergeSort0(arr, tempArr, middleIndex + 1, endIndex);

    // conquer
    // 注意merge前[startIndex, middleIndex]和[middleIndex+1, endIndex]两部分已经分别由下一层merge()递归排好序了
    merge(arr, tempArr, startIndex, middleIndex, endIndex);
}

/**
 * 归并，将左右两部分已经排好序的数据依次进行比较后重新赋值给arr中
 * e.g. 0235 4678 -> 02345678
 * @param arr 待排序数组
 * @param tempArr 临时存储数组，用于赋值排序
 * @param startIndex 归并起始位置
 * @param middleIndex 归并中间位置
 * @param endIndex 归并终止位置
 */
private static void merge(int[] arr,  int[] tempArr,  int startIndex,  int middleIndex,  int endIndex) {    
    // 复制本次start~end范围内的数据到临时数组
    // 只将待合并区间的数据复制到临时数组即可，其他相邻同长度的区域由上一层merge来处理合并
    for (int s = startIndex; s <= endIndex; s++) {
        tempArr[s] = arr[s];
    }

    int l = startIndex; 
    int r = middleIndex + 1; 
    
    // 选择排序，局部有序
    for (int k = startIndex; k <= endIndex; k++) {
        if(l > middleIndex){ // 左头指针超过了自己的边界
            arr[k] = tempArr[r++];
        } else if (r > endIndex){ // 右头指针超过了自己的边界
            arr[k] = tempArr[l++];
        } else if (tempArr[r] < tempArr[l]){ // 两部分比较取最小 
            arr[k] = tempArr[r++];
        } else {
            arr[k] = tempArr[l++];
        }
    }
}

复杂度分析

时间复杂度 merge 方法中只有一个 for 循环，直接就可以得出每次合并的时间复杂度为 O(n) ，而分解数组每次「对半切割」，属于对数时间 O(log n) ，总的时间复杂度为 O(nlogn) 。
空间复杂度如果对merge的每个递归调用都声明一个临时数组，那么任一时刻可能会有logn个临时数组处于活动期，这对小内存机器是致命的。另一方面，如果merge动态分配并释放最小量临时空间，会增加时间开销。因此在任一时刻只需要一个临时数组活动，可以使用该临时数组的任意部分（通过下标控制）在不同的分割阶段；我们将使用和输入数组arr相同的部分。这样的话，该算法的空间占用为o(n)，即待排序的数组元素个数。

以时间换空间

摘自这篇博客

我看到网上很多blog分享空间复杂度只有O(1)的归并排序法；因为传统的归并排序所消耗的空间主要是在归并函数（把两个有序的函数合并成一个有序的函数），所以如果要让时间复杂度为 O(1) ，那么也只能在归并函数中做文章了。代码就不列出来了，其主要思想就是借助于快速排序（其实就是相当于归并函数被快速排序函数替换了）；这样的方法虽然可以减少内存的消耗，但是却会在时间上带来损失，因为这样时间复杂度却变成了 O(n^2) 了；所以这种方法并不是一个两全其美的idea；

归并和快排

归并排序和快速排序有那么点异曲同工之妙：

快速排序：先把数组粗略的排序成两个子数组（只有pivot位置的数据是排好序的并且它大于左侧所有数据，小于右侧所有数据），然后递归再将pivot 左右两侧的数组以相同的方式继续寻找对应的pivot和排序好左右两侧的数据，直到左右子数组里面只有一个元素，那么就自然整个集合就排好序了，可以总结为：先(基于pivot粗略)排序再递归(粗略排序后的pivot的左半部分和右半部分，两边彼此独立)，每一轮给pivot元素寻找存放位置的时候都会随时做数据的移动，所以是边divide边conquer；
归并排序：先什么都不管，把数组分为两个子数组，一直递归把数组划分为两个子数组，直到数组里只有一个元素，这时候才开始排序，让两个数组间排好序，依次按照递归的返回来把两个数组进行排好序，到最后就可以把整个数组排好序，可以总结为：先递归再排序，divide and conquer比较完美的提现；

虽然归并排序的时间为O(nlogn)，但是它很难用于主存排序，因为合并两个排序的表需要线性附加内存，整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的附加工作，这严重影响排序的速度。对于重要的内部排序应用而言，往往选择快速排序。合并的方法是大多数「外部排序算法」的基石。

References

https://cxyxiaowu.com/articles/2019/06/11/1560233679033.html
https://www.cnblogs.com/chengxiao/p/6129630.html
https://ipine.me/2018-11-04/
https://blog.csdn.net/u013074465/article/details/42043967
https://www.cnblogs.com/chengxiao/p/6104371.html

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

Sorting Algorithms Summary

总结