排序算法执行时间.doc

软件121 金凯 1102052019 算法 1000 10000 50000 100000 插入排序 1.1ms 49.9ms 1387.4ms 5692.6ms 归并排序 2.2ms 103.2ms 2742.2ms 10630.9ms 快速排序 0.9ms 30.5ms 978.6ms 5256.4ms 随机化快排 1.5ms 28.6ms 1020.0ms 5230.5ms 插入排序 /** * 插入排序 * * @param array */ public static int[] insertionSort(int[] array) { int i, j; int insertArg;// 要插入的数据 // 从数组的第二个元素开始循环将数组中的元素插入 for (i = 1; i array.length; i++) { // 设置数组中的第2个元素为第一次循环要播讲的数据 insertArg = array[i]; j = i - 1; while (j = 0 insertArg array[j]) { // 如果要播讲的元素小于第j个元素,就将第j个元素向后移动 array[j + 1] = array[j]; j--; } // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中 array[j + 1] = insertArg; } // 打印排序后的数组 System.out.println(Arrays.toString(array)); return array; } 归并排序 /** * 归并排序 * * @param data */ public static int[] mergeSort(int[] arrays) { sort(arrays, 0, arrays.length - 1); System.out.println(Arrays.toString(arrays)); return arrays; } public static void sort(int[] data, int left, int right) { // 判断左右两边的个数 if (left = right) return; // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, center, right); } /** * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序 * * @param data * 数组对象 * @param left * 左数组的第一个元素的索引 * @param center * 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * @param right * 右数组最后一个元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右数组第一个元素索引 int mid = center + 1; // third 记录临时数组的索引 int third = left; // 缓存左数组第一个元素的索引 int tmp = left; while (left = center mid = right) { // 从两个数组中取出最小的放入临时数组 if (data[left] = data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个） while (mid = right) { tmpArr[third++] = data[mid++