JDK7的Collections.sort()的算法是TimSort, 适应性的归并排序, 比较晦涩难懂, 这里没有实现
public class mySort { // 冒泡排序 public static void myBubbleSort(int[] array) { int lastExchange = array.length - 1; //记录最后交换位置, 避免重复比较 for (int i = lastExchange - 1; i >= 0; --i) { for (int j = 0; j <= i; ++j) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; lastExchange = j; //特性:最后交互位置后的元素已经有序 } } } } // 插入排序 public static void myInsertSort(int[] array) { for (int i = 1; i <= array.length - 1; ++i) { int temp = array[i]; int j = 0; // 给值移位并寻找插入点 for (j = i - 1; j >= 0 && array[j] > temp; --j) { array[j + 1] = array[j]; } array[j + 1] = temp; } } // 选择排序 public static void mySelectSort(int[] array) { for (int i = 0; i < array.length - 1; ++i) { int minIndex = i; // 每次选出一极值 for (int j = i + 1; j <= array.length - 1; ++j) { if (array[j] < array[minIndex]) { minIndex = j; } } // 极值归位 if (minIndex != i) { int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } } } // 希尔排序 public static void myShellSort(int[] array) { int gap = 5; while (gap != 0) { //不必刻意分组, 组1->组2->组1->组2...轮流处理 for (int j = gap; j <= array.length - 1; ++j) { int temp = array[j]; int k = 0; for (k = j - gap; k >= 0 && array[k] > temp; k -= gap) { array[k + gap] = array[k]; } array[k + gap] = temp; } gap /= 2; //重新分组 } } // 快速排序 public static void myQuickSort(int[] array) { myQuickSortCore(array, 0, array.length - 1); } private static void myQuickSortCore(int[] array, int left, int right) { if (left >= right) { //递归出口 return; } int mLeft = left; int mRight = right; int base = array[mLeft]; //第一个元素作为基准, left空位可占 while(mLeft != mRight) { while (mRight > mLeft && array[mRight] >= base) { --mRight; } array[mLeft] = array[mRight]; //right可覆盖 while (mRight > mLeft && array[mLeft] <= base) { ++mLeft; } array[mRight] = array[mLeft]; } array[mRight] = base; //基准元素归位, l=r myQuickSortCore(array, left, mLeft - 1); //递归基准以左 myQuickSortCore(array, mRight + 1 , right); //递归基准以右 } // 归并排序 public static void myMergeSort(int[] array) { // 每个分组中有两个来自上层迭代的有序组, gap为有序组长度, 2 * gap为分组长度 for (int gap = 1; gap < array.length; gap *= 2) { int i = 0; // array下标 // 分组并内部排序 while (i + 2 * gap - 1 < array.length) { mergePiece(array, i, i + gap - 1, i + 2 * gap - 1); i += 2 * gap; } // 分组剩余部分排序, 只有超过一个gap才有内部排序的意义 if (i + gap - 1 < array.length) { mergePiece(array, i, i + gap - 1, array.length - 1); } } } // 将array中有序的两段piecewise1 和 piecewise2 合并成整体有序 public static void mergePiece(int[] array, int head, int mid, int tail) { int i = head; // piecewise1下标 [head, mid] int j = mid + 1; // piecewise2下标 [mid + 1, tail] // 临时数组, 保存结果 int[] arrayTemp = new int[tail - head + 1]; // combine int k = 0; // combine下标 while (i <= mid && j <= tail) { if (array[i] <= array[j]) { arrayTemp[k] = array[i]; ++i; ++k; } else { arrayTemp[k] = array[j]; ++j; ++k; } } // 复制多余部分 piecewise1 while (i <= mid) { arrayTemp[k] = array[i]; ++i; ++k; } // 复制多余部分 piecewise2 while (j <= tail) { arrayTemp[k] = array[j]; ++j; ++k; } // 结果复制到原始数组 k = 0; i = head; // 重置下标, i piecewise1 + piecewise2 while (i <= tail) { array[i] = arrayTemp[k]; ++i; ++k; } } // 堆排序 public static void myHeapSort(int[] array) { // 调整堆->大顶堆 for (int i = array.length / 2 - 1; i >= 0; --i) { // 从最后非叶子节点开始 adjustHeap(array, i, array.length); } // 调整堆->交换堆顶/末位元素 for (int j = array.length - 1; j > 0; --j) { int temp = array[0]; array[0] = array[j]; array[j] = temp; adjustHeap(array, 0, j); // 只需调整堆顶父节点 } } // 调整为大顶堆分布, node为父节点下标, adjustLen为涉及调整的长度(为排序使用) private static void adjustHeap(int[] array, int node, int adjustLen) { int temp = array[node]; // 拿出node形成可占空位 for (int i = node * 2 + 1; i < adjustLen; i = node * 2 + 1) { if (i + 1 < adjustLen && array[i] < array[i + 1]) { ++i; // 得到最大子节点 } if (array[i] > temp) { array[node] = array[i]; node = i; // 为下一层迭代更新父节点node, 最后为叶子 } else { break; } } array[node] = temp; } // 基数排序 public static void myRadixSort(int[] array) { int d = maxBit(array); int dec = 1; //进制迭代 final int R = 10; //桶个数 int[] tempArray = new int[array.length]; //临时数组, 代替桶存储数组, 代价是需记录下标/数量来分割桶 int[] bucketCapacity = new int[R]; //桶计数 for (int i = 1; i <= d; ++i) { for (int j = 0; j < R; ++j) { bucketCapacity[j] = 0; //清空桶容量 } //计数1 for (int j = 0; j < array.length; ++j) { int k = array[j] / dec % R; ++bucketCapacity[k]; } //计数2 变累计, 为分割 for (int j = 1; j < R; ++j) { bucketCapacity[j] = bucketCapacity[j - 1] + bucketCapacity[j]; } // 存储进桶 for (int j = array.length - 1; j >= 0; --j) { int k = array[j] / dec % R; tempArray[bucketCapacity[k] - 1] = array[j]; --bucketCapacity[k]; } // 写出 for(int j = 0; j < array.length; ++j) { array[j] = tempArray[j]; } // 下一位 dec *= 10; } } //求数组元素的最大位数 private static int maxBit(int[] array) { int bit = 1; int dec = 10; for (int i = 0; i < array.length; ++i) { while (array[i] >= dec) { ++bit; dec *= 10; } } return bit; }}