package test;public class first {/*普通的插入排序*/public void insertSort(int[] list) {int i, j;list[0] = -999;//相當于設置一個監視哨兵，不用判斷是否越界，//但要求數組從第二個數開始即i=1開始存儲for (i = 1; i < list.length; i++) {j = i;while (list[j] < list[j - 1]) {int temp = list[j];list[j] = list[j - 1];list[j - 1] = temp;j = j - 1;}}}/*折半插入，在直接插入的基礎上，添加二叉查找*/public void binInsertSort(int[] r, int low, int high) {for (int i = low + 1; i <= high; i++){int temp = r[i]; // 保存待插入元素int hi = i - 1;int lo = low; // 設置初始區間while (lo <= hi){ // 折半確定插入位置int mid = (lo + hi) / 2;if (temp < r[mid])hi = mid - 1;elselo = mid + 1;}for (int j = i - 1; j > hi; j--)r[j + 1] = r[j]; // 移動元素r[hi + 1] = temp; // 插入元素}}/*希爾排序或shell */public void shellSort(int[] r, int low, int high, int[] delta){for (int k=0;k<delta.length;k++)shellInsert(r, low, high, delta[k]);}private void shellInsert(int[] r, int low, int high, int deltaK){for (int i=low+deltaK; i<=high; i++)if (r[i]<r[i-deltaK]){int temp = r[i];int j = i-deltaK;for(; j>=low&&temp<r[j]; j=j-deltaK)r[j+deltaK] = r[j];r[j+deltaK] = temp;}}/*簡單的選擇交換*/public void selectSort(int[] r, int low, int high) {for (int k = low; k < high - 1; k++) { // 作n-1 趟選取int min = k;for (int i = min + 1; i <= high; i++)// 選擇關鍵字最小的元素if (r[i] < r[min])min = i;if (k != min) {int temp = r[k]; // 關鍵字最小的元素與元素r[k]交換r[k] = r[min];r[min] = temp;}// end of if}}/*堆排序-大頂堆*/public void heapSort(int[] r){int n = r.length - 1;for (int i=n/2; i>=1; i--)heapAdjust(r,i,n);for (int i=n; i>1; i--){int temp = r[1];r[1] = r[i];r[i] = temp;heapAdjust(r,1,i-1);}}//調整堆private void heapAdjust(int[] r, int low, int high){int temp = r[low];for (int j = 2 * low; j <= high; j = j * 2) {if (j < high && r[j] < r[j + 1])j++;if (temp > r[j])break;r[low] = r[j];low = j;}r[low] = temp;}public static void main(String[] args) {first fs = new first();int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };int[] k={5,3,1};// fs.insertSort(a);//fs.binInsertSort(a, 0, a.length - 1);//fs.shellSort(a, 0,a.length-1,k);//fs.selectSort(a, 0, a.length-1);fs.heapSort(a);for (int i = 0; i < a.length; i++) {System.out.println(a[i]);}}}