首先堆是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值，如下是一个堆得示例：

         9>8,9>5;8>3,8>1;5>2   由此发现非叶子结点的值均不小于左右孩子结点的值，所以这是个大顶堆，即堆顶的值是这个堆中最大的一个。

        下面的问题是我们怎么样在计算机中存储这个堆呢？也许有人会想到树的存储，确实，刚看这个堆我也是这么想的。然而事实并非如此，这个堆可以看成是一个一维数组A[6]={9,8,5,3,1,2}，那么相应的这个数组需满足性质：A[i]<=A[2*i] && A[i]<=A[2*i+1] 。其中A[i]对应堆中的非叶子结点，A[2*i]和A[2*i+1]对应于左右孩子结点。并且最后一非叶子结点下标为[n/2]向下取整。

         为什么是[n/2]向下取整呢？在这里我简单的说明一下：设n1表示完全二叉树中有一个孩子的结点，n2表示表示完全二叉树中有两个孩子的结点，d表示非叶子结点的个数，那么总的结点个数：n=n1+2*n2+1。

        （1）当n为奇数时，n1=0，n2=(n-1)/2，d=n2+n1=(n-1)/2

        （2）当n为偶数时，n1=1，n2=n/2-1，d=n2+n1=n/2

          由此可以看出d=[n/2]向下取整.

          注：请大家一定要结合完全二叉树形式的堆以及堆的数组存储形式来看下面的内容，这样才能真正理解堆排序的过程及其本质。

      b.筛选法调整堆

        （1）引出：

        现给定一个大顶堆：  即：A[6]={9,8,5,3,1,2}，如果我们稍做破坏，把9跟2互换，同时把a[6]这个结点从堆中去掉，于是得到下面这个完全二叉树：

        A[5]={2,8,5,3,1}

       显然它不是一个堆，那我们怎么把它调整为一个堆呢？首先观察，我们只是改变了根结点的值，所以根结点左、右子树均是大顶堆。其次思考，既然是根结点可能破坏了堆的性质，那我们就可以把根结点往下沉，让最大值网上浮，即比较根结点和左、右孩子的值，若根结点的值不小于孩子结点的值，说明根结点并没有破坏堆的性质，不用调整；若根结点的值小于左右孩子结点中的任意一个值，则根结点与孩子结点中较大的一个互换，互换之后又可能破坏了左或右子树的堆性质，于是要对子树进行上述调整。这样的一次调整我们称之为一次筛选。

      （2）代码：

<span style="font-size:14px;"> //堆调整，使其生成最大堆  
    private static void maxHeap(int[] data, int parentIndex) {  
        int lastIndex = data.length -1;
        int left,right,largest;  
        largest=left=2 * parentIndex + 1;  

        // 如果左子节点大于父节点，则将左子节点作为最大节点  
        if (left > lastIndex) {  
            return;
        }  
        right = left + 1;
        // 如果右子节点比最大节点还大，那么最大节点应该是右子节点  
        if(right<=lastIndex && data[right] > data[left]){  
            largest=right;  
        } 

        if(data[largest] > data[parentIndex] ){//根结点的值不是最大时,交换a[i]，a[largest]  
            swap(data, largest, parentIndex);
            //自上而下调整堆  
            maxHeap(data, largest);  
        }  
    }  </span>

（3）示例

以这个完全二叉树为例 ：        A[5]={2,8,5,3,1}

第一次筛选：2和8交换

   A[5]={8,2,5,3,1}

第二次筛选：2和3交换

   A[5]={8,3,5,2,1}

筛选完毕，得到大顶堆A[5]={8,3,5,2,1}。

（4）时间代价分析

每一次筛选的过程就是调用一次maxHeap函数，需要的时间是O（1）。那么要执行多少次筛选呢？从上述中可以看出，每一次筛选根结点都往下沉，所以筛选次数不会超过完全二叉树的深度：（[log2n]向下取整+1），其中n为结点个数,2为底数,即时间复杂度为O（log2n）

 为什么n个结点的完全二叉树的深度是([log2n]向下取整+1)呢？这里给出简单的说明：

         深度为h的完全二叉树至多有2^h-1个结点，即2^(h-1)<=n<2^h,推出h-1<=log2n<h;由于h是一个整数，所以h=[log2n]向下取整+1 . 

    c.建堆

       b中叙述了堆的筛选过程，但是给定一个待排序的序列，怎样通过筛选使这个序列满足堆的性质呢？

        给定待排序序列  A[6]={3,5,8,9,1,2},怎样使它变成一个堆呢？

        仔细想一想筛选法的前提条件是什么：根结点的左右子树已经是堆。那么这棵树中哪个结点的左右子树是堆呢，很自然的发现是最后一个非叶子结点，所以我们在这里需要自下而上的调整这个完全二叉树。

      （2）代码：

    static void creatHeap(int[] a){  
        //自下而上调整堆  
        for(int i=(a.length - 1) / 2; i >= 0; i--)  
            maxHeap(a, i);  
        System.out.println("建堆:"+Arrays.toString(a));   
    } 

      （3）示例

         待排序序列：  A[6]={3,5,8,9,1,2},     

         以8为根结点调整堆后：因为8>2，此处不进行记录移动操作

         以5为根结点调整堆后：5<9,5跟9互换 

             A[6]={3,9,8,5,1,2}

         以3为根结点调整堆后：3<9,3跟9互换

            A[6]={9,3,8,5,1,2}

         以9为根的左子树不满足大顶堆的性质，所以以3为跟调整堆,即交换3和5，得A[6]={9,5,8,3,1,2}

       （4）时间代价分析

           从最后一个非叶子结点到第二个结点，总共循环了n/2-1次，每次调用maxHeap函数，4.3中已经分析过maxHeap时间复杂度为O（log2n）。所以建堆的时间复杂度为O（n*log2n） 

     d.堆排序

      （1）堆排序过程

       也许有的朋友想问：不是讲堆排序吗，为什么不直接讲呢，而是先叙述筛选法和建堆呢？因为筛选法和建堆就构成了堆排序，讲到这里，堆排序可以说是水到渠成。所以一定要理解筛选法和建堆的过程。

       过程描述：1、建堆  2、将堆顶记录和堆中最后一个记录交换  3、筛选法调整堆，堆中记录个数减少一个，重复第2步。整个过程中堆是在不断的缩减。

      （2）代码

    public static  void sort(int[] a){   
        System.out.println("开始排序:"+Arrays.toString(a));   
        int arrayLength=a.length;   
        //建堆    
        creatHeap(a);

        //循环调整堆
        for(int i = arrayLength-1;i > 0 ;i--){   
            //交换堆顶和最后一个元素   
            swap(a, 0, i);   
            System.out.println("交换:"+Arrays.toString(a));   

            maxHeap(a, 0);   
            System.out.println("调整堆:"+Arrays.toString(a));   

        }   
    }   

      （3）示例
        0.待排序序列：

         A[6]={3,5,8,9,1,2},  

        1.建堆后（建堆过程参见4.4）：

        A[6]={9,3,8,5,1,2}

       2.9和2交换，然后把9从堆中去掉后：

         A[6]={2,3,8,5,1,9}

      3.筛选法调整堆A[5]={2,3,8,5,1}后（调整过程参见4.3）：

       A[6]={8,3,2,5,1,9}

      4.堆顶记录与最后一个记录互换，重复第二步，但是堆顶记录和最后一个记录的值变了

    （4）堆排序性能分析

       此外堆排序是不稳定的原地排序算法。

      堆排序时间=建堆时间+调整堆时间。从上文中知道建堆时间复杂度为O（n*log2n）。筛选法调整堆（maxHeap函数）时间O（log2n），总共循环了n-1次maxHeap函数，所以调整堆时间复杂度为O（n*log2n）。得出堆排序时间复杂度O（n*log2n）。

       熟悉了堆排序的过程后，可以发现堆排序不存在最佳情况，待排序序列是有序或者逆序时，并不对应于堆排序的最佳或最坏情况。且在最坏情况下时间复杂度也是O（n*log2 n）。

初始时，i = 0;  j = 9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为：

 i = 3;   j = 7;   X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

      最坏时间复杂度：最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n-1 次划分，第 i 次划分开始时区间长度为 n-i-1, 所需的比较次数为 n-i(1<=i<=n-1), 故总的比较次数达到最大值 Cmax =n(n-1)/2=O(n^2) 。如果按上面给出的划分算法，每次取当前无序区的第 1 个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。

       最好时间复杂度：在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果与基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为 O(n×lgn)。 

        用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为 O(lgn), 而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过 n，故整个排序过程所需要的关键字比较总次数C(n)=O(n×lgn) 。因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O(n^2 )，最好时间复杂度为 O(n×lgn)。

综上可知：归并排序其实要做两件事：

（1）“分解”——将序列每次折半划分。

（2）“合并”——将划分后的序列段两两合并后排序。

我们先来考虑第二步，如何合并？

在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。

这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。

先将他们合并到一个局部的暂存数组R2中，带合并完成后再将R2复制回R中。

为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。

每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。

经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。

核心代码 

 private static void merge(int[] a, int left, int middle, int right) {
        int[] tmpArr = new int[a.length];
        int mid = middle+1; //右边的起始位置
        int tmp = left;
        int third = left;
        while(left<=middle && mid<=right){
            //从两个数组中选取较小的数放入中间数组
            if(a[left]<=a[mid]){
                tmpArr[third++] = a[left++];
            }else{
                tmpArr[third++] = a[mid++];
            }
        }
        //将剩余的部分放入中间数组
        while(left<=middle){
            tmpArr[third++] = a[left++];
        }
        while(mid<=right){
            tmpArr[third++] = a[mid++];
        }
        //将中间数组复制回原数组
        while(tmp<=right){
            a[tmp] = tmpArr[tmp++];
        }
    }

掌握了合并的方法，接下来，让我们来了解  如何分解。

在某趟归并中，设各子表的长度为gap，则归并前R[0...n-1]***有n/gap个有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。

调用Merge将相邻的子表归并时，必须对表的特殊情况进行特殊处理。

若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为n-1。 

核心代码

private static void mergeSort(int[] a, int left, int right) {
        if(left<right){
            int middle = (left+right)/2;
            //对左边进行递归
            mergeSort(a, left, middle);
            //对右边进行递归
            mergeSort(a, middle+1, right);
            //合并
            merge(a,left,middle,right);
        }
    }

      2.不回写+非递归优化归并排序      

      3.利用自然合并排序优化归并排序

      4.双向自然合并排序优化归并排序算法

     基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），

LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。

注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。

在进行完最低位数的分配后再合并回单一的数组中。