1.创建4万个随机数,然后用分别用冒泡法,选择法,二叉树法3种排序算法进行排序,比较哪种更快
1 package Collection; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 public class sortSpeedTest { 7 8 public static void main(String[] args) { 9 int num = 40000; // 元素个数 10 int rnd1[] = new int[num]; 11 for (int i = 0; i < rnd1.length; i++) { 12 rnd1[i] = (int) Math.round(Math.random() * 100000); 13 } 14 int rnd2[] = new int[num]; 15 int rnd3[] = new int[num]; 16 System.arraycopy(rnd1, 0, rnd2, 0, rnd1.length); 17 System.arraycopy(rnd1, 0, rnd3, 0, rnd1.length); 18 19 long startTime1 = System.currentTimeMillis(); 20 bubbleSort(rnd1); 21 long endTime1 = System.currentTimeMillis(); 22 23 long startTime2 = System.currentTimeMillis(); 24 selectSort(rnd2); 25 long endTime2 = System.currentTimeMillis(); 26 27 long startTime3 = System.currentTimeMillis(); 28 List res = binarySort(rnd3); 29 long endTime3 = System.currentTimeMillis(); 30 31 System.out.printf("冒泡排序耗时:%d ms \n", (endTime1 - startTime1)); 32 System.out.printf("选择排序耗时:%d ms \n", (endTime2 - startTime2)); 33 System.out.printf("二叉树排序耗时:%d ms \n", (endTime3 - startTime3)); 34 35 // System.out.println("验证rnd1"); 36 // for(int x:rnd1) 37 // System.out.printf(x+" "); 38 // System.out.println("\n验证rnd2"); 39 // for(int x:rnd2) 40 // System.out.printf(x+" "); 41 // System.out.println("\n验证rnd3"); 42 // System.out.println(res); 43 44 } 45 46 public static class Node { 47 public Node LNode; 48 public Node RNode; 49 public Object value; // 结点的值 50 51 public void add(Object v) { // 传入的参数是要加入二叉树的新结点的值,是数值!!! 52 if (this.value == null) { 53 value = v; 54 } else { 55 if ((Integer) v > (Integer) value) { // 新增的结点的值大于当前结点的值 56 if (RNode == null) { // 当前结点右子树为空,要新建右子树结点 57 RNode = new Node(); // 使当前结点的右子树指向新增的结点,此时RNode的value自然没有赋值,是null 58 } 59 // 如果RNode非空,说明该结点右子树非空,则在右子树的基础上继续调用add以把数值v添加到二叉树正确的位置, 60 // 如果RNode为空,自然是上面新建右子树结点,并且由于此时RNode的value肯定是null,于是调用本身的add方法,把v赋值到RNode的value 61 RNode.add(v); 62 } else { // 新增的结点的值小于当前结点的值 63 if (LNode == null) { 64 LNode = new Node(); 65 } 66 LNode.add(v); 67 } 68 } 69 70 } 71 72 // 二叉树的中序遍历,若二叉树本身是排序二叉树,则中序遍历能“有序输出”所有结点数值 73 public List<Object> values() { // 返回类型是List 74 List<Object> values = new ArrayList<Object>(); // 用来保存中途遍历的结果 75 if (LNode != null) { 76 values.addAll(LNode.values()); // 左子树非空,递归的“递” 77 } 78 79 values.add(value); // 把当前结点数值保存到values列表 80 81 if (RNode != null) { 82 values.addAll(RNode.values()); // 右子树非空,递归的“递” 83 } 84 85 return values; // 递归的“归”,先上层返回中途遍历结果 86 87 } 88 } 89 90 private static List binarySort(int[] rnd) { 91 // TODO Auto-generated method stub 92 Node root = new Node(); 93 for (int x : rnd) { 94 root.add(x); 95 } 96 return root.values(); 97 } 98 99 private static void selectSort(int[] rnd) { 100 // TODO Auto-generated method stub 101 int i, j, min, tmp, min_index; 102 for (i = 0; i < rnd.length; i++) { 103 min = 1000000; 104 min_index = i; 105 for (j = i; j < rnd.length; j++) { 106 if (min > rnd[j]) { 107 min = rnd[j]; 108 min_index = j; 109 } 110 } 111 tmp = rnd[i]; 112 rnd[i] = rnd[min_index]; 113 rnd[min_index] = tmp; 114 } 115 } 116 117 private static void bubbleSort(int[] rnd) { 118 // TODO Auto-generated method stub 119 int i, j, tmp; 120 for (i = rnd.length - 1; i > 0; i--) { 121 122 for (j = 0; j + 1 < rnd.length; j++) { 123 if (rnd[j] > rnd[j + 1]) { 124 tmp = rnd[j]; 125 rnd[j] = rnd[j + 1]; 126 rnd[j + 1] = tmp; 127 } 128 } 129 130 } 131 } 132 133 }
效果图:
验证语句取消注释后,简单测试100个数据元素的效果图:
完全正确~
原文:https://www.cnblogs.com/gilgamesh-hjb/p/12219509.html