教材学习内容总结
查找
查找的概念: 查找是在一组项内找到指定目标或是确定目标不存在的过程
线性查找: 从数组表头开始, 依次将某个值与目标元素比较, 最后找到目标或者目标不存在于数组中
核心代码
- private static int search(int[] arr, int key) {
- int index = -1;
- int i = 0;
- for (int n : arr) {
- if (n==key){
- index=i;
- break;
- }
- i++;
- }
- return index;
- }
二分查找: 将表中间位置的元素与目标元素比较, 如果两者相等, 则查找成功; 否则利用中间位置将表分成前, 后两个子表, 如果中间位置元素大于目标元素, 则进一步查找前一子表, 否则进一步查找后一子表.
核心代码
- public static int search(int[] nums, int num) {
- int low = 0;
- int high = nums.length - 1;
- while (low <= high) {
- int mid = (low + high) / 2;
- if (num> nums[mid]) {
- low = mid + 1;
- } else if (num <nums[mid]) {
- high = mid - 1;
- } else {
- return mid;
- }
- }
- return -1;
- }
哈希表查找: 哈希表是根据关键码值而直接进行访问的数据结构. 也就是说, 它通过把目标元素映射到表中一个位置来访问查找.
核心代码
- public void insert(T x) {
- List<T> whichList=theLists[myhash(x)];
- if(!whichList.contains(x)) {
- whichList.add(x);
- if(++currentSize>theLists.length)
- rehash();
- }
- }
- public void remove(T x) {
- List<T> whichList=theLists[myhash(x)];
- if(whichList.contains(x)) {
- whichList.remove(x);
- currentSize--;
- }
- }
- public boolean contains(T x) {
- List<T> whilchList=theLists[myhash(x)];
- return whilchList.contains(x);
- }
- public void makeEmpty() {
- for(int i=0;i<theLists.length;i++)
- theLists[i].clear();
- currentSize=0;
- }
排序
选择排序: 首先在未排序序列中找到最小 (大) 元素, 存放到排序序列的起始位置, 然后, 再从剩余未排序元素中继续寻找最小 (大) 元素, 然后放到已排序序列的末尾. 以此类推, 直到所有元素均排序完毕.
核心代码
- public class SelectionSort {
- public static String selectionSort(int[] arr) {
- for(int i=0; i<arr.length; i++) {
- int minIndex = i;
- for(int j=i; j<arr.length; j++) {
- if(arr[j] <arr[minIndex]) {
- minIndex = j;
- }
- }
- int tmp = arr[i];
- arr[i] = arr[minIndex];
- arr[minIndex] = tmp;
- }
- return Arrays.toString(arr);
- }
冒泡排序: 比较相邻的元素. 如果第一个比第二个大, 就交换它们两个. 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对. 在这一点, 最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤, 除了最后一个, 持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较.
核心代码
- public static void bubbleSort(int []arr) {
- for(int i =1;i<arr.length;i++) {
- for(int j=0;j<arr.length-i;j++) {
- if(arr[j]>arr[j+1]) {
- int temp = arr[j];
- arr[j]=arr[j+1];
- arr[j+1]=temp;
- }
- }
- }
快速排序: 先从序列中取出一个数作为基准数;
分区过程: 将把这个数大的数全部放到它的右边, 小于或者等于它的数全放到它的左边; 递归地对左右子序列进行不走 2, 直到各区间只有一个数.
核心代码
- public class TestQuickSort {
- private static int partition(int[] arr, int low, int high) {
- int i = low;
- int j= high;
- int x = arr[low];
- while(i<j){
- arr[j]
- while(arr[j]>=x && i<j){
- j--;
- }
- if(i<j){
- arr[i] = arr[j];
- i++;
- }
- while(arr[i]<x && i<j){
- i++;
- }
- if(i<j){
- arr[j] = arr[i];
- j--;
- }
- }
- arr[i] = x;//arr[j] = y
- return i; //return j;
- }
- private static void quickSort(int[] arr, int low, int high) {
- if(low < high){
- intindexpartition(arr,low,high);
- quickSort(arr,low,index-1);
- quickSort(arr,index+1,high);
- }
- }
归并排序: 归并排序是一种基于递归策略的排序算法. 它采用分治法, 归并排序将待排序的元素序列分成两个长度相等的子序列, 为每一个子序列排序, 然后再将他们合并成一个子序列. 合并两个子序列的过程也就是两路归并.
核心代码
- public class MergeSort {
- public void merge(int []a,int left,int mid,int right){
- int []tmp=new int[a.length];
- int p1=left,p2=mid+1,k=left;
- while(p1<=mid && p2<=right){
- if(a[p1]<=a[p2])
- tmp[k++]=a[p1++];
- else
- tmp[k++]=a[p2++];
- }
- while(p1<=mid) tmp[k++]=a[p1++];
- while(p2<=right) tmp[k++]=a[p2++];
- for (int i = left; i <=right; i++)
- a[i]=tmp[i];
- }
- public void mergeSort(int [] a,int start,int end){
- if(start<end){
- int mid=(start+end)
- mergeSort(a,start,mid);
- mergeSort(a,mid+1,end);
- merge(a, start, mid, end);
- }
- }
教材学习中的问题和解决过程
问题 1: 在 java 中线性查找和二分查找有什么区别?
优劣各是什么?
问题 1 解决方案: 二分查找法的查找次数比线性查找少, 查找速度快, 但是要求待查表为有序表, 且插入删除困难, 条件要求比线性查找多.
问题 2: 快速排序和归并排序哪个效率高?
问题 2 解决方案: 首先可各自的时间复杂度做一个比较, 通过比较两者均为 O(nlogn), 但大 O 的作用是给出一个规模的上的比较, 到底谁更快还得看具体的平均时间所处理的数据量, 下面是我从网上收集的测试数据:
代码调试中的问题和解决过程
问题 1: 提示无法找到两个变量的符号
问题 1 解决方案: 忘记定义静态变量
代码托管 https://gitee.com/zhang_jinghao/godzilla.git
上周考试错题总结
上周没有考试所以无错题
结对及互评
评分标准
基于评分标准, 我给本博客打分: 15 分. 得分情况如下:
正确使用 Markdown 语法(加 1 分):
模板中的要素齐全(加 1 分)
教材学习中的问题和解决过程, 加 3 分
代码调试中的问题和解决过程, 加 2 分
本周有效代码超过 300 分行的(加 2 分)
其他加分: 6
扣分: 0 分
点评模板:
博客中值得学习的或问题:
内容详实且精简
问题充分且已解决
代码中值得学习的或问题:
正确且简练
方法多样很值得学习
参考示例
点评过的同学博客和代码
本周结对学习情况
结对学习内容
查找的一系列方法
排序的一系列方法
其他(感悟, 思考等, 可选)
1, 这周学的内容又开始逐渐变难了, 有点跟不上, 但是多抽出点空闲时间还是能够学到更多东西的, 我会尽量抽出更多的时间去敲代码.
2, 多敲一敲课本上的代码, 累计代码量, 打好基础.
学习进度条
代码行数(新增 / 累积) | 博客量(新增 / 累积) | 学习时间(新增 / 累积) | 重要成长 | |
---|---|---|---|---|
目标 | 5000 行 | 30 篇 | 400 小时 | |
第一周 | 200/200 | 2/2 | 20/20 | |
第二周 | 300/500 | 2/4 | 18/38 | |
第三周 | 500/1000 | 3/7 | 22/60 | |
第四周 | 300/1300 | 2/9 | 30/90 |
尝试一下记录「计划学习时间」和「实际学习时间」, 到期末看看能不能改进自己的计划能力. 这个工作学习中很重要, 也很有用.
耗时估计的公式: Y=X+X/N ,Y=X-X/N, 训练次数多了, X,Y 就接近了.
参考: 软件工程软件的估计为什么这么难, 软件工程 估计方法
计划学习时间: XX 小时
实际学习时间: XX 小时
改进情况:
(有空多看看现代软件工程 课件
软件工程师能力自我评价表 https://www.cnblogs.com/xinz/p/3852177.html )
参考资料
《Java 程序设计与数据结构教程(第二版)》 https://book.douban.com/subject/26851579/
《Java 程序设计与数据结构教程(第二版)》学习指导 https://www.cnblogs.com/rocedu/p/5182332.html
...
来源: http://www.bubuko.com/infodetail-3272987.html