代码更新自上篇，如下：

1 package ren.laughing.datastructure.algorithm;  2   3 import ren.laughing.datastructure.baseImpl.BinTreeNode;  4   5 /**  6  * 排序  7  *   8  * @author Laughing_Lz  9  * @time 2016年4月22日 10  */ 11 public class Sorter { 12     /** 13      * 直接插入排序(从小到大) 时间复杂度为O(n^2) 14      *  15      * @param arr 16      *            要排序的数组 17      * @param low 18      *            要排序的最低下标 19      * @param high 20      *            要排序的最高下标 21      * @return 排序后的数组 22      */ 23     public static void insertSort(int[] arr, int low, int high) { 24         for (int i = low + 1; i <= high; i++) { 25             int temp = arr[i];// 待插入元素 26             int j = i;// 记录待插入位置 27             for (; j > low && temp < arr[j - 1]; j--) {
   // 28                 arr[j] = arr[j - 1];// 后移 29             } 30             arr[j] = temp;// 插入 31         } 32         printResult("直接插入排序：", arr); 33     } 34  35     /** 36      * 折半插入排序 时间复杂度仍为O(n^2) 37      *  38      * @param arr 39      * @param low 40      * @param high 41      * @return 42      */ 43     public static void binInsertSort(int[] arr, int low, int high) { 44         for (int i = low + 1; i <= high; i++) { 45             int temp = arr[i]; 46             int lo = low; 47             int hi = i - 1; 48             while (lo <= hi) {
   // 注意'=' ★ 49                 int mid = (lo + hi) / 2; 50                 if (temp < arr[mid]) { 51                     hi = mid - 1;// 由此看出最终temp的位置在hi+1 52                 } else { 53                     lo = mid + 1;// hi+1等同于lo (此处应该没错吧？) 54                 } 55             } 56             for (int j = i - 1; j > hi; j--) {
   // 后移 57                 arr[j + 1] = arr[j]; 58             } 59             arr[hi + 1] = temp;// 插入 60         } 61         printResult("折半插入排序：", arr); 62     } 63  64     /** 65      * 希尔排序（缩小增量排序） 当n在某个范围内，时间复杂度可达到O(n^1.3) 66      *  67      * @param arr 68      * @param low 69      * @param high 70      * @param delta 71      *            步长序列 72      */ 73     public static void shellSort(int[] arr, int low, int high, int[] delta) { 74         for (int i = 0; i < delta.length; i++) {
   // 第一步：遍历步长序列 75             for (int m = low; m < low + delta[i]; m++) {
   // 第二步：循环起始点，保证每个被拆分的子序列都被直接排序 76                 for (int j = m + delta[i]; j <= high; j += delta[i]) {
   // 对每个子序列直接排序 77                     int temp = arr[j]; 78                     int k = j; 79                     for (; k > m && temp < arr[(k - delta[i])]; k -= delta[i]) { 80                         arr[k] = arr[(k - delta[i])];// 后移 81                     } 82                     arr[k] = temp;// 插入 83                 } 84             } 85         } 86         printResult("希尔排序：", arr); 87     } 88  89     /** 90      * 冒泡排序 时间复杂度为O(n^2) 91      *  92      * @param arr 93      * @param low 94      * @param high 95      */ 96     public static void bubbleSort(int[] arr, int low, int high) { 97         int len = high - low + 1; 98         for (int i = 1; i < len; i++) { 99             for (int j = low; j <= high - i; j++) {
   // 这里j<= high-i ★100                 if (arr[j] > arr[j + 1]) {101                     int temp = arr[j];// 交换102                     arr[j] = arr[j + 1];103                     arr[j + 1] = temp;104                 }105             }106         }107         printResult("冒泡排序：", arr);108     }109 110     /**111      * 快速排序 需要递归112      * 113      * @param arr114      * @param low115      * @param high116      */117     public static void quickSort(int[] arr, int low, int high) {118         if (low < high) {119             int pa = partition(arr, low, high);// 分治120             quickSort(arr, low, pa - 1);121             quickSort(arr, pa + 1, high);122         }123     }124 125     /**126      * 将序列划分为两个子序列并返回枢轴元素的位置127      * 128      * @param arr129      * @param low130      *            划分区间131      * @param high132      * @return133      */134     private static int partition(int[] arr, int low, int high) {135         int pivot = arr[low];// 首先定义枢轴为low所指元素136         while (low < high) {
   // 交替扫描137             while (arr[high] > pivot && low < high) {138                 high--;139             }140             arr[low] = arr[high];// 将比 pivot 小的元素移向低端141             while (arr[low] < pivot && low < high) {142                 low++;143             }144             arr[high] = arr[low];// 将比 pivot 大的元素移向高端145         }146         arr[low] = pivot;// 设置枢轴147         return low;148     }149 150     /**151      * 简单选择排序 时间复杂度为O(n^2)152      * 153      * @param arr154      * @param low155      * @param high156      */157     public static void selectSort(int[] arr, int low, int high) {158         for (int i = low; i < high - 1; i++) {159             int min = i;// 记录位置,不是元素是位置！★160             for (int j = i; j <= high; j++) {161                 if (arr[j] < arr[min]) {162                     min = j;// 更新最小元素位置163                 }164             }165             if (min != i) {
   // 交换166                 int temp = arr[min];167                 arr[min] = arr[i];168                 arr[i] = temp;169             }170         }171         printResult("简单选择排序：", arr);172     }173 174     /**175      * 堆排序，时间复杂度为O(nlogn) 堆排序中，arr[]数组的首位arr[0]弃用。所以这里arr[1]为根结点176      * 177      * @param arr178      */179     public static void heapSelectSort(int[] arr) {180         int n = arr.length - 1;181         for (int i = n / 2; i >= 1; i--) {
   // 遍历叶子结点的上层第一个结点及之前所有结点,i>=1是因为数组中首位元素弃用182             heapAdjust(arr, i, n);// 初始化建堆,i=n/2位置183         }184         for (int i = n; i > 1; i--) {
   //185             int temp = arr[1];// 堆顶元素（根节点）为最大元素，将它和堆底元素交换186             arr[1] = arr[i];187             arr[i] = temp;188             heapAdjust(arr, 1, i - 1);// 从根结点更新堆189         }190         printResult("堆排序：", arr);191     }192 193     /**194      * 创建堆195      * 196      * @param r197      *            数组元素根据二叉树层次遍历顺序存储198      * @param low199      *            遍历是否比左右孩子大的起始结点200      * @param high201      *            数组长度202      */203     private static void heapAdjust(int[] r, int low, int high) {204         int temp = r[low];// r[low]为要与左右孩子比较的父结点，以保证其比左右孩子都大205         for (int j = 2 * low; j <= high; j = j * 2) {
   // 需要循环保证该起始结点low以下的树都符合堆定义★206             if (j < high && r[j] < r[j + 1]) {
   // r[j]是r[low]的左孩子，r[j+1]是右孩子207                 j++;208             }209             if (temp > r[j]) {
   // 父结点与较大的孩子比较大小，若父结点小，交换210                 break;211             }212             r[low] = r[j];// 父结点存放的是三者中最大的元素213             low = j;214         }215         r[low] = temp;// 将原父结点的元素存入孩子结点216     }217 218     /**219      * 归并排序220      * 221      * @param arr222      * @param low223      * @param high224      */225     public static void mergeSort(int[] arr, int low, int high) {226         if (low < high) {
   // 分治227             mergeSort(arr, low, (low + high) / 2);228             mergeSort(arr, (low + high) / 2 + 1, high);229             merge(arr, low, (low + high) / 2, high);230         }231     }232 233     /**234      * 将两个有序区间[low,mid]和[mid+1,high]合并成一个有序区间235      * 236      * @param arr237      * @param low238      * @param mid239      * @param high240      */241     private static void merge(int[] arr, int low, int mid, int high) {242         int[] temp = new int[high - low + 1];243         int a = low;244         int b = mid + 1;245         int t = 0;246         while (a <= mid && b <= high) {
   // 注意这个循环★247             if (arr[a] < arr[b]) {248                 temp[t++] = arr[a++];249             } else {250                 temp[t++] = arr[b++];251             }252         }253         while (a <= mid) {254             temp[t++] = arr[a++];255         }256         while (b <= high) {257             temp[t++] = arr[b++];258         }259         for (int i = 0; i < temp.length; i++) {260             arr[low + i] = temp[i];261         }262     }263 264     /**265      * 程序入口266      * 267      * @param args268      */269     public static void main(String[] args) {270         int[] arr = new int[] { 2, 5, 7, 3, 4, 8, 1, 9, 6, 0 };271         int[] delta = new int[] { 5, 3, 1 };272         // insertSort(arr, 0, 9);273         // binInsertSort(arr, 0, 9);274         // shellSort(arr, 0, 9, delta);275         // bubbleSort(arr, 0, 9);276         // quickSort(arr, 0, 9);277         // printResult("快速排序：", arr);278         // selectSort(arr, 0, 9);279         // heapSelectSort(arr);280         mergeSort(arr, 0, 9);281         printResult("归并排序：", arr);282     }283 284     /**285      * 打印286      * 287      * @param str288      * @param arr289      */290     public static void printResult(String str, int[] arr) {291         System.out.print(str);292         for (int i = 0; i < arr.length; i++) {293             System.out.print(arr[i] + " ");294         }295         System.out.println();296     }297 }