算法-学习笔记（一）

1 排序

1.1 插入排序

插入排序代码(Java)： /** * <b> 插入排序 * <br/> 从无序到有序，将无序组的数据 依次插入倒有序组 * @param array 输入数据 * @return int */ public static void insertionSort(int[] array){ for (int i = 1; i < array.length; i++) { int key = array[i], j=i-1; while(j >= 0 && array[j] > key){ array[j+1] = array[j]; j--; } array[j+1]=key; } } 测试代码(需导入junit包) public static int[] produceArray(int num){ //工具方法，用于生产num个随机数初始化的数组 Random random = new Random(); int[] a= new int[num]; for (int i = 0; i < num; i++) { a[i] = random.nextInt(100); } return a; } @Test public void insertionSort(){ int []a = Sort.produceArray(10000); System.out.println(Arrays.toString(a)); long beginTime = System.nanoTime(); //计时，单位纳秒 com.algorithm.sort.Sort.insertionSort(a); long overTime = System.nanoTime(); System.out.println(Arrays.toString(a)); System.out.println("耗时："+(overTime-beginTime)/1000000.0+"ms"); //耗时结果 }

1.2 归并排序

归并排序递归实现 /** * <b> 归并排序-递归实现 * <br/>采用分治法（分而治之） * @param array 待排序数组 * @param left 需排序的 左下标 * @param right 需排序的 右下标 * @return int[] 排序后的数组 */ public static void mergeSort(int[] array, int left, int right){ if(left<right){ // int middle = (int) Math.round((left+right)/2.0); int middle = (left+right)/2; mergeSort(array,left,middle); mergeSort(array,middle+1,right); merge(array,left,middle,right); } } /** * <b> 两堆有序数列合并 * @param array 原数组 * @param left 左下标 * @param middle 中下标 * @param right 右下标 * */ public static void merge(int[] array,int left, int middle, int right){ int n1 = middle-left+1; //左边数组个数 int n2 = right-middle-1+1; //右边数组个数，±1可省略，这里为了便于观察，添加上了 int[] arrayLeft = new int[n1+1]; //多添加一个，用于作为堆底 int[] arrayRight = new int[n2+1]; for (int i = 0; i < n1; i++) { //初始化两个有序数组 arrayLeft[i] = array[left+i]; } for (int i = 0; i < n2; i++) { arrayRight[i] = array[middle+i +1]; } arrayLeft[n1] = Integer.MAX_VALUE; //临界量赋值，用作堆底，也可称其为哨兵 arrayRight[n2] = Integer.MAX_VALUE; int pl=0,pr=0; //左右数组初始指针 for (int i = left; i <= right ; i++) { //从已排好序的两数组中，抽取一个较小值 放到原数组中 if(arrayLeft[pl] < arrayRight[pr]){ array[i] =arrayLeft[pl]; pl++; }else{ array[i] = arrayRight[pr]; pr++; } } } 测试代码（需junit包） @Test public void mergeSort(){ int size = 100000; //数据量大小 int []a = Sort.produceArray(size); //与上一测试代码相同的工具方法 System.out.println(Arrays.toString(a)); long beginTime = System.nanoTime(); com.algorithm.sort.Sort.mergeSort(a,0,size-1); long overTime = System.nanoTime(); System.out.println(Arrays.toString(a)); System.out.println("耗时："+(overTime-beginTime)/1000000.0+"ms"); }

1.3 算法时间对比

插入排序与归并排序所用时间

数据量越大两者的效率差距越大