最近在学习算法的一些知识，发现这些知识并非可有可无，不再做一个只会使用API的程序员，这是一个漫长的学习过程。
以下为常用的几个算法的Java实现，写在一个Junit测试类中了，这样方便执行，也不至于文件太多。
1 package alg; 2 3 import java.util.Arrays; 4 import org.junit.Test; 5 6 public class Algorithm { 7 8 private static long arr[] = new long [ 10 ]; 9 10 static { 11 for ( int i = 0 ; i < arr.length; i ++ ) { 12 arr[i] = ( long ) (Math.random() * 100 ); 13 } 14 } 15 16 private void swap( long [] array, int i, int j) { 17 if (i == j) { 18 return ; 19 } 20 21 long temp = arr[i]; 22 arr[i] = arr[j]; 23 arr[j] = temp; 24 } 25 26 @Test 27 public void arraysSort() { 28 System.out.println( " 排序前： " + Arrays.toString(arr)); 29 30 Arrays.sort(arr); 31 32 System.out.println( " 排序后： " + Arrays.toString(arr)); 33 } 34 35 /** 36 * 37 * 冒泡排序----交换排序的一种 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序）， 38 * 下一次循环是将其他的数进行类似操作。 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4 39 * 40 */ 41 @Test 42 public void bubbleSort() { 43 System.out.println( " 排序前： " + Arrays.toString(arr)); 44 45 for ( int i = arr.length - 1 ; i >= 1 ; i -- ) { 46 47 for ( int j = 0 ; j < i; j ++ ) { 48 if (arr[j] > arr[j + 1 ]) { 49 swap(arr, j, j + 1 ); 50 } 51 } 52 } 53 54 System.out.println( " 排序后： " + Arrays.toString(arr)); 55 } 56 57 // 换一下泡泡的走向 58 @Test 59 public void bubbleSort2() { 60 System.out.println( " 排序前： " + Arrays.toString(arr)); 61 62 for ( int i = arr.length - 1 ; i >= 1 ; i -- ) { 63 64 for ( int j = i; j > 0 ; j -- ) { 65 if (arr[j] < arr[j - 1 ]) { 66 swap(arr, j, j - 1 ); 67 } 68 } 69 } 70 71 System.out.println( " 排序后： " + Arrays.toString(arr)); 72 } 73 74 /** 75 * 76 * 直接选择排序法----选择排序的一种 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 77 * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 性能：比较次数O(n^2),n^2/2 交换次数O(n),n 78 * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。 79 * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。 80 */ 81 @Test 82 public void selectSort() { 83 System.out.println( " 排序前： " + Arrays.toString(arr)); 84 85 for ( int i = 0 ; i < arr.length - 1 ; i ++ ) { 86 87 int index = i; 88 for ( int j = i + 1 ; j < arr.length; j ++ ) { 89 if (arr[index] > arr[j]) { 90 index = j; 91 } 92 } 93 94 swap(arr, i, index); 95 } 96 97 System.out.println( " 排序后： " + Arrays.toString(arr)); 98 } 99 100 /** 101 * 插入排序 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。 性能：比较次数O(n^2),n^2/4 102 * 复制次数O(n),n^2/4 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。 103 */ 104 @Test 105 public void insertSort() { 106 System.out.println( " 排序前： " + Arrays.toString(arr)); 107 108 for ( int i = 1 ; i < arr.length; i ++ ) { 109 long temp = arr[i]; 110 111 int j; 112 113 for (j = i; j > 0 ; j -- ) { 114 if (temp < arr[j - 1 ]) { 115 arr[j] = arr[j - 1 ]; 116 } else { 117 break ; 118 } 119 120 } 121 arr[j] = temp; 122 } 123 124 System.out.println( " 排序后： " + Arrays.toString(arr)); 125 } 126 127 // 来自于java.util.Arrays的源码 128 @Test 129 public void insertSort2() { 130 System.out.println( " 排序前： " + Arrays.toString(arr)); 131 132 for ( int i = 0 ; i < arr.length; i ++ ) { 133 134 for ( int j = i; j > 0 && arr[j - 1 ] > arr[j]; j -- ) { 135 swap(arr, j, j - 1 ); 136 } 137 } 138 139 System.out.println( " 排序后： " + Arrays.toString(arr)); 140 } 141 142 @Test 143 public void quickSort() { 144 System.out.println( " 排序前： " + Arrays.toString(arr)); 145 146 qSort(arr, 0 , arr.length - 1 ); 147 148 System.out.println( " 排序后： " + Arrays.toString(arr)); 149 } 150 151 private void qSort( long [] array, int low, int high) { 152 if (low < high) { 153 int pivot = partition(array, low, high); 154 155 qSort(arr, low, pivot - 1 ); 156 157 qSort(arr, pivot + 1 , high); 158 } 159 } 160 161 private int partition( long [] array, int low, int high) { 162 long pivot = array[low]; 163 164 int left = low; 165 int right = high; 166 167 while (left < right) { 168 169 while (array[left] <= pivot && left < right) { 170 left ++ ; 171 } 172 173 while (array[right] > pivot) { 174 right -- ; 175 } 176 177 if (left < right) { 178 swap(array, left, right); 179 } 180 } 181 182 swap(array, low, right); 183 184 return right; 185 } 186 } 187
找到一个参考网址http://www.cs.princeton.edu/introcs/40algorithms/
转载于:https://www.cnblogs.com/Jason_zhu/archive/2010/09/14/1826012.html
