排序公共方法
/*** 判断 a > b ?*/public static boolean greater(Comparable a, Comparable b){return a.compareTo(b) > 0;}/*** 交换数组 a 和 b*/public static void exch(Comparable[] arr, int a, int b){Comparable temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
冒泡排序
/*** 冒泡排序*/public static void bubbleSort(Comparable[] arr){for(int i = 0; i < arr.length -1; i++){for(int j = 0; j < arr.length - i - 1; j++){if (greater(arr[j], arr[j+1])){exch(arr, j, j+1);}}}}
选择排序
/*** 选择排序*/public static void selectSort(Comparable[] arr){//最小数的索引，默认为0for(int i = 0; i < arr.length -2 ; i++){int minIndex = i;for(int j = i+1; j < arr.length; j++){if(greater(arr[minIndex], arr[j])){//如果前面大于后面，则重新赋值最小索引minIndex = j;}}//比较完一轮，交换最小索引if(i != minIndex)exch(arr, minIndex, i);}}
插入排序
/*** 插入排序*/public static void insertSort(Comparable[] arr){//外层循环次数为数组长度减一，默认arr[0]为已排序for (int i = 1; i < arr.length; i++){//与前一个比较，如果前一个大，就交换for (int j = i; j > 0; j--){if(greater(arr[j-1], arr[j])){exch(arr, j-1, j);}else{//如果前一个小，就结束内层循环break;}}}}
希尔排序
/*** 希尔排序*/public static void shellSort(Comparable[] arr){//根据数组长度，确定增长量的初始值 hint h = 1;while(h < arr.length/2){h = 2*h + 1;}// 如果 h>0 就排序// 3 4 8 5 9 1 2// |_____|_____|while(h > 0){//找到带插入元素，从第h个开始for(int i = h; i < arr.length; i++){//从第h个开始，往前每次减h个for(int j = i; j >= h; j -= h){if(greater(arr[j - h], arr[j])){//带插入元素arr[j] 和 arr[j-h] 比较，如果前面的大就交换exch(arr, j, j - h);}else{break;}}}//一轮排序完成，h = h/2h = h/2;}}