表示晚上心里有些不宁静，所以就写一篇博客，来缓缓。囧
拜读《算法导论》这样的神作，当然要做一些练习啦。除了练习题与思考题那样的理论思考，也离不开编码的实践。
所以，后面每个章节，我都会尽力整理出章节中涉及的算法的Java代码实现。
二分查找 算法实现 package tech.jarry.learning.test.algorithms.binarysearch; public class BinarySearch { public static int binarySearch(int[] array, int target) { return binarySearch(array, target, 0, array.length - 1); } // 二分查找，要求输入的线性表必须是顺序的 public static int binarySearch(int[] array, int target, int startIndex, int endIndex) { if (endIndex > startIndex) { int middleIndex = (startIndex + endIndex) / 2; if (target < array[middleIndex]){ return binarySearch(array, target, startIndex, middleIndex); } else if (target > array[middleIndex]) { return binarySearch(array, target, middleIndex + 1, endIndex); } else if (target == array[middleIndex]) { return middleIndex; } } return -1; } } 算法测试 package tech.jarry.learning.test.algorithms.binarysearch; public class BinarySearchTest { public static void main(String[] args) { int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12}; System.out.println(BinarySearch.binarySearch(testArray, 100)); } }结果输出
-1这表示没有找到目标数据，可以将测试类中的target修改为其他数字。
冒泡排序 算法实现 package tech.jarry.learning.test.algorithms.bubblesort; public class BubbleSort { public static int[] bubbleSort(int[] array) { for (int i = 0; i < array.length; i++){ for (int j = i; j < array.length; j++) { if (array[j] < array[i]) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } return array; } } 算法测试 package tech.jarry.learning.test.algorithms.bubblesort; import java.util.Arrays; public class BubbleSortTest { public static void main(String[] args) { int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12}; System.out.println(Arrays.toString(BubbleSort.bubbleSort(testArray))); } }结果输出
[0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18] 插入排序 算法实现 package tech.jarry.learning.test.algorithms.insertsort; import java.util.Arrays; public class InsertionSort { public static int[]insertSort(int[] originArray) { // 从数组的第二个元素开始进行比较（总不能第一个元素和第一个元素自己比较大小吧） for (int j = 1; j < originArray.length; j++) { // 获取当前元素的值 int key = originArray[j]; // 获取前一个元素的下标 int i = j - 1; // 将key值前移（即将遇到的每个大于key的元素后移） while (i >= 0 && originArray[i] > key) { originArray[i + 1] = originArray[i]; i = i - 1; } // 直到遇到originArray[i] <= key，才对i+1进行赋值（而i+1元素之前已经后移复制了，即i+2位置保存了i+1位置的值） originArray[i + 1] =key; } return originArray; } public static int[] insertSortProWithBinarySearch(int[] array) { // 如果数据组织形式是数组，那么即使采用二分查找优化，底层的数组元素移动，依旧会导致最终的时间复杂度变为n^2，而不是期待的n*lgn return null; } } 算法测试 package tech.jarry.learning.test.algorithms.insertsort; import java.util.Arrays; public class InsertionSortTest { // test public static void main(String[] args) { int[] originArray = new int[]{9, 6, 4, 5, 8}; int[] resultArray = InsertionSort.insertSort(originArray); System.out.println(Arrays.toString(resultArray)); } }结果输出
[4, 5, 6, 8, 9] 归并排序 算法实现这个代码的实现，可能内容比较多。一方面是由于方法提取（提取哨兵创建的操作），另一方面是由于增加了练习题中提到的无哨兵归并排序的实现（在mergeSort方法中，可以自由选择是否使用哨兵）。
package tech.jarry.learning.test.algorithms.mergesort; import java.util.Arrays; /** * 归并排序 */ public class MergeSort { public static int[] mergeSort(int[] array) { return mergeSort(array, 0, array.length - 1); } public static int[] mergeSort(int[] array, int startIndex, int endIndex) { if (startIndex < endIndex) { int middleIndex = startIndex + (endIndex - startIndex) / 2; array = mergeSort(array, startIndex, middleIndex); array = mergeSort(array, middleIndex + 1, endIndex); // 使用哨兵，进行合并 // return merge(array, startIndex, middleIndex, endIndex); // 不适用哨兵，进行合并 return noSentinelMerge(array, startIndex, middleIndex, endIndex); } // 如果startIndex = endIndex，表示array只有一个元素 return array; } private static int[] merge(int[] array, int startIndex, int middleIndex, int endIndex) { int[] sentinelLeftArray = createSentinelArray(array, startIndex, middleIndex); int[] sentinelRightArray = createSentinelArray(array, middleIndex + 1, endIndex); for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) { if (sentinelLeftArray[m] < sentinelRightArray[n]) { // 这里千万别忘了startIndex，因为不同分支的起点不同 array[startIndex + i] = sentinelLeftArray[m++]; } else { array[startIndex + i] = sentinelRightArray[n++]; } // 不用考虑两个Integer.MAX_VALUE，因为最后两个数组分别剩下的元素必然是这两个哨兵元素 } return array; } private static int[] createSentinelArray(int[] array, int startIndex, int endIndex) { int length = endIndex - startIndex + 1; int[] sentinelArray = new int[length + 1]; for (int i = 0; i < length; i++) { sentinelArray[i] = array[startIndex + i]; } sentinelArray[endIndex - startIndex + 1] = Integer.MAX_VALUE; return sentinelArray; } // p.22_practise2.3-2 在不使用哨兵的前提下，进行归并排序的合并操作 private static int[] noSentinelMerge(int[] array, int startIndex, int middleIndex, int endIndex) { int[] leftArray = createNonSentinelBranchArray(array, startIndex, middleIndex); int[] rightArray = createNonSentinelBranchArray(array, middleIndex + 1, endIndex); for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) { if (leftArray[m] < rightArray[n]) { array[startIndex + i] = leftArray[m++]; if (m == leftArray.length) { // 将rightArray剩下的元素全部复制到array对应位置中 array = branchArray2Array(array, startIndex + i + 1, rightArray, n); break; } } else { array[startIndex + i] = rightArray[n++]; if (n == rightArray.length) { // 将leftArray剩下的元素全部复制到array对应位置中 array = branchArray2Array(array, startIndex + i + 1, leftArray, m); break; } } // 不用考虑两个Integer.MAX_VALUE，因为最后两个数组分别剩下的元素必然是这两个哨兵元素 } return array; } private static int[] createNonSentinelBranchArray(int[] array, int startIndex, int endIndex) { int length = endIndex - startIndex + 1; int[] branchArray = new int[length]; for (int i = 0; i < length; i++) { branchArray[i] = array[startIndex + i]; } return branchArray; } private static int[] branchArray2Array(int[] array, int targetIndex, int[] branchArray, int startIndex) { while (startIndex < branchArray.length) { array[targetIndex++] = branchArray[startIndex++]; } return array; } // 由于一些情况（如内存空间不足），数据可以直接保存到硬盘中。而不是保存在内存的数组中 private static void merge2Disk(int[] array, int startIndex, int middleIndex, int endIndex){ int[] sentinelLeftArray = createSentinelArray(array, startIndex, middleIndex); int[] sentinelRightArray = createSentinelArray(array, middleIndex + 1, endIndex); for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) { if (sentinelLeftArray[m] < sentinelRightArray[n]) { Disk.store(sentinelLeftArray[m++]); } else { Disk.store(sentinelRightArray[n++]); } // 不用考虑两个Integer.MAX_VALUE，因为最后两个数组分别剩下的元素必然是这两个哨兵元素 } } // test_creatreSentinelArray public static void main(String[] args) { int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0}; System.out.println(Arrays.toString(createSentinelArray(testArray, 0 , 2))); } } 补充：上述代码涉及的Disk类