2017/06/24

目录导读：

- 1.常见排序
    ┌ 插入排序：直接插入排序(稳定)、→希尔排序(不稳定)
    │
    │ 交换排序: 冒泡排序(稳定)、→快速排序(不稳定)
    │
    │ 选择排序：简单选择排序(不稳定)、→堆排序
    │
    │ 归并排序：2路归并排序
    │
    │ 桶排序：稳定排序，比快排还要快(缺点是相当耗费空间)
    │ 
    └ 基数排序：

- 2.二叉树排序
- 3.拓扑排序
  这里的排序并不是常规意义下的安大小排序，主要是为解决一个工程能否顺序进行的问题，

**排序：**
假设有n个记录(即序列元素)的序列{R1, R2, ..., Rn}, 按其某类关键字(如价格、年龄、分数等)
排列成有序(非递增、非递减)的序列：{Rp1, Rp2, ... , Rpn}
     
排序算法的首要衡量指标就是：速度

基本有序：指关键字小的记录基本在前面，关键字大的记录基本在后面，关键字不大不小的记录基本在中间.

**排序的稳定性：**
假设两个记录的关键字 ki=kj (其中 1 <= i <= n, 1 <= j <= n, i != j)，且在排序前的序列中的 Ri 的位置领先 Rj， 如果排序后仍有 Ri 的位置领先 Rj,则称为该类排序方法是稳定的；反之则是不稳定的

    ┌ 稳定排序：相同关键字的记录排序前后其相对位置(即前后位置)是不变化的
    │       如：快速排序
    │
    └ 不稳定排序：相对位置发生变化

内排序与外排序：
    根据在排序过程中待排序的记录是否全部被放置在内存中，可分为：内排序、外排序
    
    ┌ 内排序(重要)：在排序的整个过程中，待排序的所有记录全部同时被放置在内存中。
    │
    │
    └ 外排序：由于排序的记录个数太多，不能同时放置在内存中，只能分批放入内存中。整个排序过程中需要在内外存之间多次交换数据才能进行
            
    对于内排序，该类算法的性能受下面3方面影响：
        1)时间性能(主要衡量指标)
            影响算法的效率(快慢)。主要受关键字的比较次数、记录移动的次数
        2)辅助空间
            算法执行过程中额外需要的存储空间
        3)算法的复杂性
            指算法自身的复杂度（过于复杂，难以理解）

按排序策略分：（各个策略中具体的排序算法越靠后效率越高）

        ┌ 插入排序：直接插入排序(稳定)、→希尔排序(不稳定)
        │
        │ 交换排序: 冒泡排序(稳定)、→快速排序(不稳定)
        │
        │ 选择排序：简单选择排序(不稳定)、→堆排序
        │
        │ 归并排序：2路归并排序
        │
        └ 基数排序：

        
各种排序算法的性能总结
    ┌───────────────────────┬───────────────────────────────┬───────────┬──────┐
    │                       │         时间复杂度            │           │      │
    │       排序算法名称      ├─────────────┬────────┬────────┤空间复杂度 │稳定性│
    │                       │平均情况     │最坏情况│最好情况│           │      │    
    ├──────────┬────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │直接插入排序│ O((n^2)/4)  │ O(n^2) │ O(n)   │ O(1)      │ 稳定 │
    │ 插入排序 ├────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │希尔排序    │O(nlogn~n^2) │ O(n^2) │O(n^1.5)│ O(1)      │不稳定│
    ├──────────┼────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │冒泡排序    │ O(n^2)      │ O(n^2) │ O(n)   │ O(1)      │ 稳定 │
    │ 交换排序 ├────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │快速排序    │ O(nlogn)    │ O(n^2) │O(nlogn)│ O(1)      │不稳定│     
    ├──────────┴────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │简单选择排序│(n-1)(n+2)/2 │ O(n^2) │ O(n^2) │ O(1)      │不稳定│
    │ 选择排序 ├────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │堆排序     │ O(nlogn)    │O(nlogn)│O(nlogn)│ O(1)      │不稳定│
    ├──────────┼────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │2路归并排序 │ O(nlogn)    │O(nlogn)│O(nlogn)│ O(n)      │ 稳定 │
    │ 归并排序 ├────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │            │             │        │        │           │      │
    ├──────────┼────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │            │             │        │        │           │      │
    │ 基数排序 ├────────────┼─────────────┼────────┼────────┼───────────┼──────┤
    │          │            │             │        │        │           │      │
    └──────────┴────────────┴─────────────┴────────┴────────┴───────────┴──────┘
    
    注: 对于同样是 O(n^2) 的排序，直接插入排序法的性能就要比冒泡和简单选择排序的性能好一些
        冒泡排序法的时间复杂度也是O(n^2),但简单选择排序的性能要优于冒泡排序法。
        直接插入排序法 > 简单选择排序 > 冒泡排序法
    
        
        

1.插入排序：
    1)直接插入排序(Straight Insertion Sort)
    基本思想：将一个记录插入到已经排好序的有序表中。从而得到一个新的、记录数增1的有序表
    
    打扑克牌时的过程
    
    算法分析：
        空间复杂度(只需一个辅助空间)：O(1)
        时间复杂度：
            最好情况(待排序列有序)：只需进行 n-1 次比较而已，移动0次，因此 T[n] = O(n)=n;
            
            最坏情况(逆序)：需要比较次数： ∑i= 2 + 3 + ... + n = (n-1)(n+2)/2 ≈ n^2/2
                            移动次数：∑(i+1) = 3 + 4 + .. + n = (n-1)(n+4)/2 ≈ n^2/2
                            
                            注意：这里多了个加1，是因为最后"sort[j] = sort[0];"的移动，这个思路是大话数据结构中的

            如果从平均情况来看，根据概率相同的原则，平均比较和移动的次数约为：n^2/4
            因此，时间复杂度：O(n) = n^2;
    
    注意：
    1.对于同样是 O(n^2) 的排序，直接插入排序法的性能就要比冒泡和简单选择排序的性能好一些(怎么得出来的？从平均复杂度得出来的)
    2.上面的复杂度是按《大化数据结构》中的思路来的：将sort[0]的位置空出来，作为哨兵，这个方式比本文中的方式好很多，减少了每次比较(j >= 1),
    
         
    '代码描述'
    package chapter08.sort.insertsort;
    /**
     * 直接插入排序
     * @author Administrator
     *
     */
    public class StraightInsertSort {   
        public void insertSort(int[] sort) {
            int temp; //临时存储单元
            int j;
            for(int i = 1; i < sort.length; i++) {
                if(sort[i] < sort[i-1]) {
                    //表明要插入的这个元素比当前位置的元素关键字小
                    temp = sort[i]; 
                    /** 
                    * 加了"j >= 1"的条件是为了防止数组越界，如果将0下标处的单元空出来
                    * 用作临时存储单元(即这里temp的作用)就可以不加着个条件，《大话数据结构》中就是这么做的。大话数据中的做法比较好，能减少比较次数。
                    */
                    for(j = i; j >= 1 && temp < sort[j-1]; j--) {
                        sort[j] = sort[j - 1];                  
                    }
                    sort[j] = temp;
                }
            }
        }
    }
    


    2)希尔排序(shell Sort)
    是直接插入排序算法的改进,为什么会比直接插入排序效果好呢？原因就在于后面的直接插入排序步骤是建立在前面这些插入排序的基础之上的，而每经一次插入排序后，数列就会向基本有序迈进一步，从而会使的后面的排序会越来越快。

    基本思想：
    先取一个正整数d1(0<d1<n, 筛选步长),把全部记录分成d1个组，所有相距为d1倍数的记录看成是一组，然后各个组内进行插入排序；接着取d2(d2<d1, 例如采用d2 = d1/2)，重复上述过程，直到di=1(i>=1)即所有的分组记录成为一个组时，结束。

    算法分析：
    shellSort有三层循环，最外层循环是logn数量级的，中间for是n数量级的，内循环远低于n数量级（随着分组越来越少，序列越来越有序，循环次数不会增加）。因此，希尔排序的时间复杂度在O(nlogn)和O(n^2)之间，大约为O(n^3/2)

    '代码描述'
    package chapter08.sort.insertsort;
    /**
     * 希尔排序
     * @author Administrator
     *
     */
    public class ShellSort {
        /**
         * 希尔排序算法
         * @param sort
         */ 
        public void shellSort(int[] sort) {
            int temp; //临时存储变量
            int j;
            //用于控制增量的变化,即控制分组情况
            for(int d = sort.length/2; d >= 1; d = d/2) {
                //对组内元素进行直接插入排序：从第一个分组的第一个元素(索引为d)开始依次向后遍历
                for(int i = d; i < sort.length; i++) {
                    if (sort[i] < sort[i - d]) {
                        //表明该小组内i处的元素比前面(i-d处)元素小，因此有向后移动的必要
                        temp = sort[i];
                        //从此位置之后，将相距d位置的元素进行直接插入排序
                        for(j = i; j >= d && sort[j-d] > temp; j -= d) {
                            sort[j] = sort[j-d];
                        }
                        sort[j] = temp;
                    }
                }
            }
        }
    }


    
2.交换排序：                     
    1)冒泡排序(Bubble Sort)
    基本思想：两两比较相邻记录的关键字，如果反序(例如关键字的是大小，小的在下大的在上)则交换，直到没有反序的记录为止。
    
    ★冒泡排序算法复杂度分析：(只是针对改进型的) 
    (1)时间复杂度：
    最好的情况就是该序列本身就是有序，因此只需进行 1 趟，比较 n-1 次，移动0次
    时间复杂度：O(n)
    
    最坏的情况就是该序列完全逆序：需要进行 n-1 趟，共比较：1+2+...+n= n(n-1)/2 次，并移动 n(n-1)/2 次
    时间复杂度：O(n^2)
            
    
    '代码描述'
    /**
     * 各类冒泡排序算法
     * @author Administrator
     *
     */
    public class BubbleSort {
        
        /**
         * 最简单的冒泡排序（严格来说都不算冒泡排序）
         * 因为冒泡排序的定义是相邻连个元素的比较,况且这种方式是非常低效的，对哪些
         * 没有排好序的部分没有一点贡献，反之很有可能将那些较小的沉到低下去了
         * @param sort
         */
        public void bubbleSort1(int[] sort) {
            
            for (int i = 0; i < sort.length; i++) {
                for(int j = i + 1; j < sort.length; j++) {
                    if(sort[j] < sort[i]) {
                        swap(sort, i, j);                   
                    }
                }
            }
        }
        
        /**
         * 正宗的冒泡排序——上升 :比较一趟会将最小的冒到顶端
         * 从后向前比较
         * @param sort
         */
        public void bubbleSort2(int[] sort) {
            for(int i = 0; i < sort.length; i++) {
                //一趟比较下来，就可以将最小元素交换到最顶端（即数组的 0 处）
                for(int j = sort.length - 2; j >= i; j--) {
                    if(sort[j] > sort[j+1]) {
                        //将较小的交换到前面,
                        swap(sort, j, j + 1);
                    }           
                }   
            }
        }
        
        /**
         * 正宗的冒泡排序——下沉 :比较一趟会将最大的沉到底部
         * 从前面向后比较
         * @param sort
         */
        public void bubbleSort3(int[] sort) {
            for(int i = 0; i < sort.length; i++) {
                //一趟比较下来，就可以将大元素交换到最底部（即数组的最大处）
                for(int j = 0; j < sort.length - i - 1; j++) {
                    if(sort[j] > sort[j+1]) {
                        //将较大的交换到后面,
                        swap(sort, j, j + 1);
                    }           
                }   
            }
        }
        
        /**
         * 冒泡排序的改进: 
         *  若在中途就已经使原序列有序了，那么后面的比较久没有意义了
         *  为了防止，对后面做无意义的比较，可设置一个标志位
         * @param sort
         */
        public void bubbleSort4(int[] sort) {
            boolean isExchange = true; //默认是true
            for(int i = 0; i < sort.length && isExchange; i++) {
                //进行一趟排序前将标志位置为false;
                isExchange = false;
                for(int j = sort.length - 2; j >= i; j--) {
                    if(sort[j] > sort[j+1]) {
                        swap(sort, j, j + 1);
                        //表示已经交换过了，所以将此标记位置零
                        isExchange = true; 
                    }
                }
            }
        }
            
        /**
         * 交换数组 i, j 处的元素位置
         * @param sort
         * @param i
         * @param j
         */
        private void swap(int[] sort, int i, int j) {
            int temp = sort[i];
            sort[i] = sort[j];
            sort[j] = temp;     
        }
    }
    
    
        
    2)快速排序(Quick Sort) —— 递归思想的体现
    
    本质仍是交换排序，是冒泡排序的升级：通过不断比较和移动交换来实现来排序，增大了
    记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字小的记录
    直接从后面移动到前面，从而减少了比较和移动交换的次数。
    
    基本思想：通过一趟排序后，将待排记录分割成独立的两部分，其中一部分记录的关键字
            均比另一部分记录的关键字小。然后分别对这两部分的记录继续进行上面的排序
            操作，直到最后。从而可以达到整个序列有序的目的。
            
    快排算法的时间复杂度：
        最优的情况下(每次划分的很均匀，其递归过程是一颗平衡二叉树)： O(nlogn)
        最坏的情况下(序列为正序或逆序，其递归过程是一颗斜树)： O(n^2)
    
    空间复杂度：主要是递归造成的栈空间的使用
        最好情况下，递归树(平衡二叉树)的深度为 logn，因此，其空间复杂度为 O(logn)，
        最坏情况下，递归树(为斜二叉树)的深度为 n-1, 因此，其空间复杂度 O(n-1)
    
    '代码描述'
    package chapter08.sort.exchangesort;
    /**
     * 快速排序
     * @author Administrator
     */
    import chapter08.sort.insertsort.StraightInsertSort;
    
    public class QuickSort {
        
        //用于衡量待排序列数量的大小
        private final int MAX_LENGTH_INSERT_SORT = 7; 
         //为了后面优化用的
        private StraightInsertSort inSort = new StraightInsertSort();
        
        //快排,
        public void quickSort(int[] sort) {
            qSort(sort, 0, sort.length - 1);//这里封装函数是为了递归调用
        }
        
        //实际排序的函数
        private void qSort(int[] sort, int low, int high) {
            /**
             * 注意：对于该快速排序而言，当数据量较大时，其算法优势大于递归造成的性能下降
             *      而当数据量较小时(如7个以下),递归的影响就会大起来，此时，直接插入排序
             *      的性能是最好的（适合小数据量的情况）。因此，需要分类处理
             */
            if ((high - low) > MAX_LENGTH_INSERT_SORT) {
                //当数据量较大时
                int pivot; //作为分割的关键字，称为枢轴
                if (low < high) {
                    /**
                     * 这是整个快排的核心代码段,选择一个关键字，以此枢轴将序列分为
                     * 左右两部分，并在最后给出该枢轴的位置：pivot
                     * 这里还有算法可以优化的可能性，因为下面进行了两次递归，其实对于
                     * 第二个递归是可以转换为迭代来实现的。
                     */
                    while(low < high) {
                        pivot = partition(sort, low, high); //该函数相当重要,它使得序列sort变的基本有序
                        qSort(sort, low, pivot - 1); //将左半段(小于枢轴)继续排序   
                        /**
                         * 注意到第一次递归后，变量low就没有用了，所以可以在它上面
                         * 做文章, 可以考虑为递归来优化 ？
                         */
                        low = pivot + 1;                    
                    }
                    
                    //qSort(sort, pivot + 1, high); //将右半段(大于枢轴)继续排序
                    
                }
            } else {
                //当数据较小时，用直接插入排序法
                inSort.insertSort(sort);    
            }
            
        }
        
        //核心代码
        //以枢轴将序列划分为两部分,并使得序列sort变的基本有序
        private int partition(int[] sort, int low, int high) {
            
            int pivotkey;//每次它的选取越靠近序列中间位置越好(序列有序状态下的中间位置)      
            /**
             * pivotkey = sort[low]; //以序列的第一个元素作为枢轴
             * 这种方式对于第一个元素是序列中间值时效率还可以，否则效率将会很低下
             * 其实对于以任何固定地方的的元素作为枢轴都是不可取的。
             * 因此，该枢轴的选取做进一步优化的：
             *  方法1（随机枢轴法）：选取low和high之间的随机数作为枢轴，有撞大运的嫌疑，不太好
             *  方法2（三数取中法）：取左、右、中间位置的三个数(其实也可以从序列中随机选取三
             *                  个数，这种方法同左中右选取三数效果一样，但随机数生成器
             *                  会造成系统额外开销，因此就不考虑了)，排序后取中间的数作为枢轴。
             *      不是很明白具体的程序写法？
             *  方法3（九数取中）：分三次取样，每次取三个数，从中各取出一个中间数，然后
             *                  从这三个数中再取中间数
             */
            //pivotkey = sort[low]; //以序列的第一个元素作为枢轴
            
            int mid = low + (high - low) / 2;
            //排序：左（中间值）、 中（最小的值）、 右（最大的值）
            if(sort[low] > sort[high]) {
                swap(sort, low, high);          
            }
            if(sort[mid] > sort[high]) {
                swap(sort, high, mid);
            }
            if(sort[mid] > sort[low]) {
                swap(sort, mid, low);           
            }   
            
            pivotkey = sort[low];
            
            /**
             * 下面的swap方法交换了两个记录的位置，其实这里的交换是不必要的，可以
             * 将其省略,直接进行替换
             */
            int temp = pivotkey;//将枢轴关键字备份起来
            
            //开始比较划分:从序列的两端开始向中间扫描
            while(low < high) {     
                //先从high端开始 (必须要先从high端开始)
                while(low < high && sort[high] >= pivotkey) {
                    high --;                
                }
                //表明此时high端出现了比关键字小的元素了，所以需要将其交换到low端
                // swap(sort, low, high); //为了优化性能，不进行交换，而是直接替换
                sort[low] = sort[high];
                
                //再从low端开始
                while(low < high && sort[low] <= pivotkey) {
                    low ++;             
                }
                //表明此时左边出现了比关键字大的元素了，所以需要将其交换到high端位置（即右端）
                // swap(sort, low, high); //为了优化性能，不进行交换，而是直接替换
                sort[high] = sort[low];         
            }
            
            sort[low] = temp; // 将枢轴值替换会
            return low; //返回枢轴所在的位置 
        }
        
        
        
        /**
         * 交换数组 i, j 处的元素位置
         * @param sort
         * @param i
         * @param j
         */
        private void swap(int[] sort, int i, int j) {
            int temp = sort[i];
            sort[i] = sort[j];
            sort[j] = temp;     
        }
        
    }




3.选择排序：
基本思想：每趟在 n-i+1(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录
    
    1)简单选择排序(Simple Selection Sort)
    基本思想：就是通过 n-i 次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和
    第i(1<= i <= n)个记录交换位置。共进行n-1趟
    
    算法分析：
    (1)时间复杂度：
         比较次数：最好情况和最坏情况一样，第i趟需要进行n-i次关键字的比较, ∑(n-i) = n-1+n-2+...+1=n(n-1)/2
         交换次数：最好情况为0，最坏情况为 n-1 次，
         综上，T[n]= n(n-1)/2 + n-1 = (n-1)(n+2)/2 = O(n^2)
    (2)空间复杂度：O(1)
    
    注意：与冒泡排序法的时间复杂度也是O(n^2),但简单选择排序的性能要优于冒泡排序法。
    
    '代码描述'
    package chapter08.sort.selecetionsort;
    import util.MyTools;

    /**
     * 简单选择排序
     * @author Administrator
     */
    public class SimpleSelecetionSort {     
        public void selectSort(int[] sort) {
            int min; //记录最小的元素
            //int tempIndex = 0; //临时辅助单元
            //int j;
            for(int i = 0; i < sort.length; i++) {      
                //min = sort[i];
                min = i;
                //进行n-i次比较，寻找n-i中最小的记录
                for(int j = i + 1; j < sort.length; j++) {
                    //发现比min处还小的数，就要进行更改最小位置索引
                    if(sort[j] < sort[min]) {
                        //min = sort[j];
                        //tempIndex = j;
                        min = j;
                    }   
                }
                /**
                 * 进行i与min的交换:注意，如果最小位置索引没有被交换，就没必要进行
                 * 下面的交换操作
                 */
                if(min != i) {
                    MyTools.swap(sort, i, min);
                }
                //sort[tempIndex] = sort[i];
                //getClass().sort[i] = min;         
            }   
        }
    }


    
    2)堆排序(Heap Sort)
    是简单选择排序的改进，特点是将每次比较选取最小元素时，将元素交换的结构也保留住，
    这样下次继续比较时省去许多不必要的交换操作。
    
基本过程：
1.首先将待排序的数组调整大定堆(或小顶堆)：具体的将数组当成是一个完全二叉树的层
序遍历结果，在此基础上将其调整为大顶堆。
2.其次选出最大(最小)的元素：将上一步得到的大顶堆的根结点和最后一个元素进行交换。
3.最后对n-i个元素重新进行调整为大顶堆(小顶堆)，重复2,3步骤
    
    "堆"的本质是一颗完全二叉树，且有大顶堆与小顶堆之分。
        大顶堆：每个结点的值都大于或等于其左右孩子结点的值
        小顶堆：每个结点的值都小于或等于其左右孩子结点的值
    
    堆排序的算法分析：
        时间复杂度(最坏、平均、最好都一样)：O(nlogn) 
        空间复杂度：O(1)
    由于其最好、最坏、平均时间复杂度均为O(nlogn)，因此，它的性能要远远好于冒泡、简单
    选择排序、直接插入排序。
    
    '代码描述'
    package chapter08.sort.selecetionsort;
    import util.MyTools;

    /**
     * 堆排序
     * @author Administrator
     *
     */
    public class HeapSort {
        
        public void heapSort(int[] sort) {
            //先将原始数据构建成一个大堆
            for(int i = sort.length / 2 - 1; i >= 0; i--){
                //调整为大堆
                heapAdjust(sort, i, sort.length - 1);
            }
            
            for(int j = sort.length - 1; j >= 0; j--) {
                MyTools.swap(sort, 0, j);
                heapAdjust(sort, 0, j - 1);         
            }       
        }
        
        /**
         * 堆调整
         * @param sort
         * @param s
         * @param m
         */
        private void heapAdjust(int[] sort, int s, int m) {
            int temp = sort[s]; //临时存储单元
            //先从结点的左右孩子中选出最大的孩子
            for(int i = 2*s + 1; i <= m; i = 2*i + 1) {
                if (i < m && sort[i] < sort[i + 1]) {
                    //表名该结点s的左孩子结点值小于右孩子的结点值，因此指向右孩纸
                    i++;
                }
                //判断结点值最大孩子的值与其父结点之间的大小,
                if (sort[i] <= temp) {
                    //表名父结点的值大，因此不用交换
                    break;
                }
                //表明孩子结点的值大于父结点，因此要交换
                sort[s] = sort[i];
                //调整到其孩子结点处，重复上述过程
                s = i;
            }
            //将父结点值交换至其子结点的位置
            sort[s] = temp;     
        }
    }

    
    
4.归并排序(Merging Sort)：
基本思想：利用归并的思想实现的排序方法。假设初始序列含有 n 个记录，则可以看成是 n 个有序的子记录，每个子序列的长度为 1，然后两两归并，得到[n/2]个长度为 2 或 1 的有序子序列；再两两合并，...，如此重复，直到得到一个长度为 n 的有序序列位置。这种排序方法称为 2 路归并排序。

先对半分割至单个元素，再“两两”合并(要进
行排序合并)，最后达到排序的目的

注：归并排序还有其他的方式实现(称为多路归并)，这里只是2路归并

算法分析：

    1.递归实现方法
        时间复杂度：每递归一次，需要将待排序列扫描一遍放入新的数组中，需要O(n)，
                一共需要递归 logn 次，因此，总的时间复杂度为：O(nlogn)
        空间复杂度：归并过程中需要与原始序列同样数量的存储空间：n
                再由于，递归深度为logn， 因此，空间复杂度：O(n+logn)
    
        注意：递归实现方式虽然代码结构很清楚，但造成了时间和空间上的性能损耗，
                因此，应该将递归实现的代码转换为'迭代'实现就会好很多
    
    2.迭代实现方法
        相比较与递归法，主要是在空间性能上进行了提升，只是真用了申请的sort.length长度
        的空间，因此，空间复杂度为：O(n)
        时间复杂度稍微有一点提升，基本同上面。
            
    '代码描述'
    package chapter08.sort.mergesort;
    /**
     * 这里只实现了2路归并排序
     * 实现方法1: 递归法(代码结构清晰，但是时间和空间性能却不尽人意)
     * 实现方式2：迭代法(代码结构简单，空间复杂度降低)
     * @author Administrator
     */
    public class MergeSort {
        
        //1.递归方法实现的
        public void mergeSort(int[] sort) {
            recurMerSort(sort, sort, 0, sort.length -1);        
        }
        //2.非递归实现的
        public void nonRecurMerSort(int[] sort) {
            //申请额外的空间
            int[] dupArr = new int[sort.length];
            //归并步长
            int k = 1; 
            while(k < sort.length) {
                //将sort[]中相隔为k的子序列两两归并到dupArr[]中
                mergePass(sort, dupArr, k, sort.length - 1);
                k = 2 * k;
                //将dupArr[]中相隔为k的子序列两两归并到sort[]中
                mergePass(dupArr, sort, k, sort.length - 1);
                k = 2 * k;          
            }       
        }
        
        /**
         * 非递归方式的辅助方法
         * 用于将无序数组sArr中相邻程度为s的子序列两两归并入newArr[]中
         * @param sArr
         * @param newArr
         * @param s
         * @param n
         */
        private void mergePass(int[] sArr, int[] newArr, int s, int n) {
            int i = 0;
            while(i <= n - 2*s + 1) {
                /**
                 *  将sArr[i, i+s-1]和sArr[i+s, i+2*s-1]有序的归并到newArr[i,i+2*s-1]中
                 *  当待排序列长度为9时，
                 *  mergePass()第1次被调用时：
                 *      (sArr, newArr, 0, 0, 1)
                 *      (sArr, newArr, 2, 2, 3)
                 *      (sArr, newArr, 4, 4, 5)
                 *      (sArr, newArr, 6, 6, 7)
                 *  mergePass()第2次被调用时：
                 *      (sArr, newArr, 0, 1, 3)
                 *      (sArr, newArr, 4, 5, 7)
                 *      (sArr, newArr, 6, 6, 7)
                 */
                recurMerSort0(sArr, newArr, i, i + s - 1, i + 2*s - 1);
                i = i + 2*s;
            }
            //归并剩下的序列
            if (i < n - s + 1) {
                //归并最后两个序列
                recurMerSort0(sArr, newArr, i, i + s - 1, n);
            }else {
                //归并最后一个序列
                for(int j = i; j <= n; j++) {
                    newArr[j] = sArr[j];                
                }           
            }       
        }
        
        /**
         * 方式1：递归法
         * 将序列sArr[start, end]归并到eArr[start, end]中
         * @param sArr
         * @param eArr
         * @param start
         * @param end
         */
        private void recurMerSort(int[] sArr, int[] eArr, int start, int end) {
            
            int m; //分割界线
            int[] dupArr = new int[sArr.length]; 
            if (start == end) {
                //当分割到每一路只有一个元素时
                eArr[end] = sArr[start];
            } else {    
                m = (start + end) / 2; //确定中间位置：m
                //将sArr[start, m]归并到dupArr[start, m]
                recurMerSort(sArr, dupArr, start, m);
                //将sArr[m+1, end]归并到dupArr[m+1, end]
                recurMerSort(sArr, dupArr, m + 1, end);
                //将dupArr[start, m]和dupArr[m+1, end]有序的归并到eArr[start, end]中
                recurMerSort0(dupArr, eArr, start, m, end);         
            }       
        }
        
        /**
         * 递归方法的辅助函数(非递归方法也用了)
         * 将sArr的[start, m] 和 [m+1, end]有序的归并为eArr[start, end]
         * @param sArr
         * @param eArr
         * @param start
         * @param m
         * @param end
         */
        private void recurMerSort0(int[] sArr, int[] eArr, int start, int m, int end) {
            
            int j; //控制后半部分
            int k = start; //控制新数组的下标,起始位置在当前小组的第一个位置
            
            //将sArr前后半段中数值较小的值排序后放入eArr数组中
            for(j = m + 1; start <= m && j <= end; k++) {
                if (sArr[start] > sArr[j]) {
                    //表明后半段这个值小
                    eArr[k] = sArr[j++];
                }else {
                    //表明前半段这个值小
                    eArr[k] = sArr[start++];
                }
            }   
            //程序走到这里，一般情况下有一段(前或后半段)中部分数据没有被放入eArr数组，因此需要放入
            //如果前半段有剩余的数据，就直接复制剩余的数据到新的数组中
            if(start <=  m) {
                for(int i = start; i <= m; i++) {
                    eArr[k++] = sArr[i];                
                }           
            }   
            //如果后半段有剩余的数据，就直接复制剩余的数据到新的数组中
            if(j <= end) {
                for(int i = j; i <= end; i++) {
                    eArr[k++] = sArr[i];                
                }           
            }   
        }
    }





        
            
            
            
/*************************  工具类 **********************************/
package util;
/**
 * 这是工具类
 * @author Administrator
 *
 */
public class MyTools {
    // 打印数组
    public static void printArray(int[] next) {
        System.out.print("[");
        for (int i = 0; i < next.length; i++) {
            if (i == next.length - 1) {
                System.out.println(next[i] + "]");
            } else {
                System.out.print(next[i] + ", ");
            }
        }
    }
    
    /**
     * 交换序列i,j 处的元素
     * @param sort
     * @param i
     * @param j
     */
    public static void swap(int[] sort, int i, int j) {
        int temp = sort[i];
        sort[i] = sort[j];
        sort[j] = temp;     
    }
}