Open Yhzhtk opened 8 years ago
排序算法编写,测试3次,每次10w个100以内的随机数。
系统排序,快速排序,合并排序,希尔排序,插入排序,选择排序,冒泡排序,堆 排序。
系统排序 耗时:66 快速排序 正确, 耗时 82 合并排序 正确, 耗时 72 希尔排序 正确, 耗时 32 插入排序 正确, 耗时 4868 选择排序 正确, 耗时 2314 冒泡排序 正确, 耗时 7296 堆 排序 正确, 耗时 29 系统排序 耗时:21 快速排序 正确, 耗时 65 合并排序 正确, 耗时 19 希尔排序 正确, 耗时 15 插入排序 正确, 耗时 5098 选择排序 正确, 耗时 2328 冒泡排序 正确, 耗时 7057 堆 排序 正确, 耗时 18 系统排序 耗时:16 快速排序 正确, 耗时 62 合并排序 正确, 耗时 21 希尔排序 正确, 耗时 12 插入排序 正确, 耗时 4896 选择排序 正确, 耗时 2333 冒泡排序 正确, 耗时 4622 堆 排序 正确, 耗时 16 实现代码
系统排序 耗时:66 快速排序 正确, 耗时 82 合并排序 正确, 耗时 72 希尔排序 正确, 耗时 32 插入排序 正确, 耗时 4868 选择排序 正确, 耗时 2314 冒泡排序 正确, 耗时 7296 堆 排序 正确, 耗时 29
系统排序 耗时:21 快速排序 正确, 耗时 65 合并排序 正确, 耗时 19 希尔排序 正确, 耗时 15 插入排序 正确, 耗时 5098 选择排序 正确, 耗时 2328 冒泡排序 正确, 耗时 7057 堆 排序 正确, 耗时 18
系统排序 耗时:16 快速排序 正确, 耗时 62 合并排序 正确, 耗时 21 希尔排序 正确, 耗时 12 插入排序 正确, 耗时 4896 选择排序 正确, 耗时 2333 冒泡排序 正确, 耗时 4622 堆 排序 正确, 耗时 16
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; /** * 排序算法编写 * * @author daihui.gu * @create 2016年2月16日 */ public class SortUtils { public static void main(String[] args) { // 测试3次,每次10w个100以内的随机数 for (int i = 0; i < 10; i++) { testSort(100000); } } /** * 测试所有排序的正确性,已经耗时 * * @author daihui.gu * @param len */ public static void testSort(int len) { Random r = new Random(); List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < len; i++) { list.add(r.nextInt(100)); } Integer[] srcArrs = list.toArray(new Integer[] {}); // 系统排序 long start = System.currentTimeMillis(); Collections.sort(list); long time = System.currentTimeMillis() - start; System.out.println("系统排序 耗时:" + time); // 快速排序 Integer[] arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); quickSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "快速排序", time); // 合并排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); mergeSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "合并排序", time); // 希尔排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); shellSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "希尔排序", time); // 插入排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); insertionSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "插入排序", time); // 选择排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); selectionSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "选择排序", time); // 冒泡排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); bubbleSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "冒泡排序", time); // 堆 排序 arrs = Arrays.copyOf(srcArrs, srcArrs.length); start = System.currentTimeMillis(); heapSort(arrs, 0, arrs.length - 1); time = System.currentTimeMillis() - start; assertEquals(list, arrs, "堆 排序", time); System.out.println(); } public static void assertEquals(List<Integer> list, Integer[] arrs, String msg, Long time) { for (int i = 0; i < list.size(); i++) { if (!arrs[i].equals(list.get(i))) { System.out.println(msg + " ERR Index:" + i); System.exit(1); } } System.out.println(msg + " 正确, 耗时 " + time); } /** * 堆排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void heapSort(Integer[] arrs, int s, int e) { // 创建最大堆 int n = (e + s) / 2; for (int i = n; i >= s; i--) { heapAdjust(arrs, i, e); } for (int i = e; i >= s; i--) { int tmp = arrs[s]; arrs[s] = arrs[i]; arrs[i] = tmp; heapAdjust(arrs, s, i - 1); } } /** * 堆排序调整方法 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void heapAdjust(Integer[] arrs, int s, int e) { // s 到 e 之间,仅有 s 位置需要调整,其余均是最大堆 int tmp = arrs[s]; int i = s; while (i * 2 + 1 <= e) { int index = i; int left = 2 * i + 1, right = left + 1; if (arrs[i] < arrs[left]) { index = left; } if (right <= e && arrs[i] < arrs[right] && arrs[left] < arrs[right]) { index = right; } if (index > i) { arrs[i] = arrs[index]; arrs[index] = tmp; i = index; } else { break; } } } /** * 合并排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void mergeSort(Integer[] arrs, int s, int e) { if (s >= e) { return; } int n = (s + e) / 2; mergeSort(arrs, s, n); mergeSort(arrs, n + 1, e); Integer[] sort = new Integer[e - s + 1]; int index = 0; int i = s, j = n + 1; while (i <= n && j <= e) { if (arrs[i] <= arrs[j]) { sort[index++] = arrs[i++]; } else { sort[index++] = arrs[j++]; } } while (i <= n) { sort[index++] = arrs[i++]; } while (j <= e) { sort[index++] = arrs[j++]; } for (int x = 0; x < sort.length; x++) { arrs[s + x] = sort[x]; } } /** * 希尔排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void shellSort(Integer[] arrs, int s, int e) { int n = e - s; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = s + gap; i < e + 1; i++) { if (arrs[i] < arrs[i - gap]) { int tmp = arrs[i]; int j; for (j = i - gap; j >= s && arrs[j] > tmp; j -= gap) { arrs[j + gap] = arrs[j]; } arrs[j + gap] = tmp; } } } } /** * 插入排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void insertionSort(Integer[] arrs, int s, int e) { for (int i = s; i < e + 1; i++) { int val = arrs[i]; int loc = i; for (int j = i - 1; j >= 0; j--) { if (arrs[j] > val) { arrs[j + 1] = arrs[j]; loc = j; } } if (loc < i) { arrs[loc] = val; } } } /** * 选择排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void selectionSort(Integer[] arrs, int s, int e) { for (int i = s; i < e; i++) { int min = arrs[i]; int loc = s; for (int j = i + 1; j < e + 1; j++) { if (min > arrs[j]) { min = arrs[j]; loc = j; } } if (loc > i) { arrs[loc] = arrs[i]; arrs[i] = min; } } } /** * 冒泡排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void bubbleSort(Integer[] arrs, int s, int e) { for (int i = s; i < e; i++) { for (int j = i + 1; j < e + 1; j++) { if (arrs[i] > arrs[j]) { int tmp = arrs[i]; arrs[i] = arrs[j]; arrs[j] = tmp; } } } } /** * 快速排序 * * @author daihui.gu * @param arrs * @param s * @param e */ public static void quickSort(Integer[] arrs, int s, int e) { int i = s, j = e; int val = arrs[i]; while (i < j) { while (val <= arrs[j] && i < j) { j--; } if (i < j) { arrs[i] = arrs[j]; arrs[j] = val; i++; } while (val >= arrs[i] && i < j) { i++; } if (i < j) { arrs[j] = arrs[i]; arrs[i] = val; j--; } } // 递归 if (s < i - 1) { quickSort(arrs, s, i - 1); } if (i + 1 < e) { quickSort(arrs, i + 1, e); } } }
查看排序动态效果 http://www.sorting-algorithms.com/
排序算法编写,测试3次,每次10w个100以内的随机数。
排序算法
系统排序,快速排序,合并排序,希尔排序,插入排序,选择排序,冒泡排序,堆 排序。
测试结果