归并排序
程序员文章站
2022-05-24 08:48:45
...
/** * 归并排序 * <ul> * <li>平均情况:O(nlog(2)n)</li> * <li>最好情况:O(nlog(2)n)</li> * <li>最坏情况:O(nlog(2)n)</li> * <li>辅助存储:O(n)</li> * <li>稳定</li> * <ul> * * @timestamp Mar 12, 2016 6:29:11 PM * @author smallbug */ public class MergeSort { public static void main(String[] args) { int[] data = DataUtil.getData(100000); // System.out.println(Arrays.toString(data)); long time = System.currentTimeMillis(); mergeSort(data); // System.out.println(Arrays.toString(data)); System.out.println("speed " + (System.currentTimeMillis() - time) + " ms"); System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否")); } private static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) >>> 1; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, right); } public static void merge(int[] data, int left, int right) { insertSort(data, left, right); } /** * 局部插入排序 * * @timestamp Mar 12, 2016 6:28:30 PM * @param data * @param left * @param right */ private static void insertSort(int[] data, int left, int right) { int temp; for (int i = left + 1; i <= right; i++) { temp = data[i];// 保存待插入的数值 int j = i; for (; j > 0 && temp < data[j - 1]; j--) { data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大,就向后移动一位 } data[j] = temp;// 插入 } } }