小结常用排序方法（二）
接着上一篇继续写
1.树形选择排序：又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键勃进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直到选出最小键字的记录为止，这个过程可用一棵有n个叶子结点的完全二叉树表示，如下图所示：
图中展示了选择最小关键字13的过程，输出13后，将13改为最大值，再进行同样的过程选出次小关键字，如此循环直到完成；
?
由于这种排序方法存在辅助存储空间较多，而且“最大值”进行多余的比较，因为这些缺点，就产生了下面的堆排序；
2.堆排序：只需要一个记录大小的辅助空间，每个待排序的记录大小占有一个存储空间。
我们先看看什么是堆：堆的定义：n个元素的序列（k1,k2,....,kn）当且仅当满足下关系时，称之为堆：
??????????? ｛Ki<=K2i且Ki<=K2i+1｝?? 或????? ｛Ki>=K2i且Ki>=K2i+1｝??
若将和此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左，右孩子结点的值。由此，若序列（k1,k2,....,knk）是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。例如，下列两个序列为堆，对应的完全二叉树如下图所示：
?
堆排序思想：
先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前 n-1 记录进行“筛选”，重新将它调整为一个“大顶堆”再将堆顶记录和第 n-1 个记录交换，如此反复直至排序结束。所谓“筛选”指的是对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆.堆排序的特点：在以后各趟的“选择”中，利用在第一趟选择中已经得到的关键字比较的结果,整个过程如下图所示：
java代码示例：
/*** <p>堆排序方法* <p>基于大根堆的堆排序方法*/private void heapSort() { Integer tmp; // 用于交换的暂存单元 buildHeap(); // 执行初始建堆，并调整 for(int i=0; i<array.length; i++) { // 交换堆顶元素array[0]和堆中最后一个元素array[array.length-1-i] tmp = array[0]; array[0] = array[array.length-1-i]; array[array.length-1-i] = tmp; // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 adjustHeap(0, array.length-1-i); }}/*** <p>建堆方法* <p>调整堆中0~array.length/2个结点，保持堆的性质* */private void buildHeap() { // 求出当前堆中最后一个存在孩子结点的索引 int pos = (array.length-1)/2; // 从该结点结点开始，执行建堆操作 for(int i=pos; i>=0; i--) { adjustHeap(i, array.length); // 在建堆过程中，及时调整堆中索引为i的结点 }}/*** <p>调整堆的方法* * @param s 待调整结点的索引* @param m 待调整堆的结点的数量(亦即：排除叶子结点)*/private void adjustHeap(int s, int m) { Integer tmp = array[s]; // 当前待调整的结点 int i = 2*s+1; // 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引) while (i<m) { if(i+1<m && array[i]<array[i+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点) i = i+1; } if(array[s]<array[i]) { array[s] = array[i]; // 孩子结点大于当前待调整结点，将孩子结点放到当前待调整结点的位置上 s = i; // 重新设置待调整的下一个结点的索引 i = 2*s+1; } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break; } array[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 }}?归并排序:是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
如 设有数列{6，202，100，301，38，8，1}
?
初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数
?
i=1?? ?[6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2??? [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
?
总计： 11次
?
?下图展示了归并排序的过程
java代码示例：
/***归并排序，要求待排序的数组必须实现Comparable接口*/public class MergeSort implements SortStrategy{ private Comparable[] bridge; /** *利用归并排序算法对数组obj进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The param can not be null!"); } bridge = new Comparable[obj.length]; //初始化中间数组 mergeSort(obj, 0, obj.length - 1); //归并排序 bridge = null; } /** *将下标从left到right的数组进行归并排序 *@param obj 要排序的数组的句柄 *@param left 要排序的数组的第一个元素下标 *@param right 要排序的数组的最后一个元素的下标 */ private void mergeSort(Comparable[] obj, int left, int right) { if (left < right) { int center = (left + right)/2; mergeSort(obj, left, center); mergeSort(obj, center + 1, right); merge(obj, left, center, right); } } /** *将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序 *@param obj 对象数组的句柄 *@param left 左数组的第一个元素的下标 *@param center 左数组的最后一个元素的下标 *@param right 右数组的最后一个元素的下标 */ private void merge(Comparable[] obj, int left, int center, int right) { int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= right) { //从两个数组中取出小的放入中间数组 if (obj[left].compareTo(obj[mid]) <= 0) { bridge[third++] = obj[left++]; } else bridge[third++] = obj[mid++]; } //剩余部分依次置入中间数组 while (mid <= right) { bridge[third++] = obj[mid++]; } while (left <= center) { bridge[third++] = obj[left++]; } //将中间数组的内容拷贝回原数组 copy(obj, tmp, right); } /** *将中间数组bridge中的内容拷贝到原数组中 *@param obj 原数组的句柄 *@param left 要拷贝的第一个元素的下标 *@param right 要拷贝的最后一个元素的下标 */ private void copy(Comparable[] obj, int left, int right) { while (left <= right) { obj[left] = bridge[left]; left++; } }}?
?
?
?