《算法导论》第二章demo代码实现（Java版）
2020-02-23 16:01:27来源：博客园 阅读 ()
《算法导论》第二章demo代码实现（Java版）
《算法导论》第二章demo代码实现（Java版）
前言
表示晚上心里有些不宁静，所以就写一篇博客，来缓缓。囧
拜读《算法导论》这样的神作，当然要做一些练习啦。除了练习题与思考题那样的理论思考，也离不开编码的实践。
所以，后面每个章节，我都会尽力整理出章节中涉及的算法的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类
之所以在归并排序中增加这个硬盘操作，是因为我做这道题想起来很久之前遇到的一道面试题。就是问如何用1G的空间，去排序8G的数据。答案就是采用归并排序（当时原理说出来了，但是白板没写好）。
package tech.jarry.learning.test.algorithms.mergesort;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 模仿真实硬盘，进行数据的存储与打印数据
*/
public class Disk {
private static List<Integer> diskIntegerInstance = new ArrayList<>();
public static void store(int element) {
diskIntegerInstance.add(element);
}
public static void printAll() {
Iterator<Integer> integerIterator = diskIntegerInstance.iterator();
while (integerIterator.hasNext()) {
System.out.println(integerIterator.next());
}
}
}
算法测试
package tech.jarry.learning.test.algorithms.mergesort;
import java.util.Arrays;
public class MergeSortTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
// 3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12
// correct result: [0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18]
int[] resultArray = MergeSort.mergeSort(testArray);
System.out.println(Arrays.toString(resultArray));
}
}
结果输出
[0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18]确定两数之和为固定值
这道题在leetcode中是存在的，之前的博客也有对应的解析。甚至leetcode还有求三数之和为确定值的题目。
算法实现
package tech.jarry.learning.ch2.algorithms.twosum;
import tech.jarry.learning.ch2.algorithms.mergesort.MergeSort;
public class TwoSum {
// 题目中只要求实现确定是否存在，而无需返回对应index。否则，需要注意剔除相同index的问题，并修改binarySearch的返回值
public static boolean twoSum(int[] array, int target) {
array = MergeSort.mergeSort(array);
for (int i = 0; i < array.length; i++) {
int branchTarget = target - array[i];
// 二分查找的时间复杂度为lgn
if (binarySearch(array, branchTarget)) {
return true;
}
}
return false;
}
private static boolean binarySearch(int[] array, int target) {
return binarySearch(array, target, 0, array.length - 1);
}
private static boolean binarySearch(int[] array, int target, int startIndex, int endIndex) {
if (endIndex > startIndex) {
int middleIndex = (endIndex + startIndex) / 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 true;
}
}
return false;
}
}
算法测试
package tech.jarry.learning.test.algorithms.twosum;
public class TwoSumTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
int target = 80;
System.out.println(TwoSum.twoSum(testArray, target));
}
}
结果输出
false由于书中的demo只要求输出存在与否，而leetcode类似的题目，则要求返回两个元素的index。感兴趣的朋友，可以看我之前写的有关leetcode求两数之和解法的博客。
总结
其实，这章算法的demo还是比较容易实现的。更多的是找找实现算法的感觉吧。
如果代码存在什么问题，或者你们存在什么疑惑，可以私信或@我。
愿与诸君共进步。
原文链接:https://www.cnblogs.com/Tiancheng-Duan/p/12343859.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- 数组小Demo 2020-05-25
- 并发编程之CountDownLatch demo与源码 2020-05-14
- error in ./src/views/demo/ueditor.vue Module build f 2020-04-26
- Shiro 入门demo 2020-03-30
- 反射Demo 2020-03-27
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签