小结常用排序方法（二）

接着上一篇继续写

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++;
　　　　　　　} }
}