首页 > 代码库 > Java基础知识二次学习--第五章 数组

Java基础知识二次学习--第五章 数组

第五章 数组
时间:2017年4月26日15:11:30~2017年4月26日15:15:54
章节:05章_01节 
视频长度:09:30
内容:一维数组的内存分析
心得:
Java中数组是引用类型 栈里面存的数组的引用 实际对象在堆内存里面
(C与C++是分配在栈里的)
内存图:
技术分享

 

 
元素为引用数据类型的数组
技术分享

 

引用类型的数组如上图
 
时间:2017年4月26日15:16:22~2017年4月26日15:19:00
章节:05章_02节 
视频长度:05:25
内容:数组元素的创建与使用
心得:
首先分配空间,再往里面添加内容
静态初始化:在定义数组的同时就为数组元素分配空间并赋值
例如 int a[]={3,2,4}
Java数组下标从0开始
 
时间:2017年4月26日15:19:17~2017年4月26日15:55:10
章节:05章_03节 ~05章_14节 
视频长度:6:24 +11:29 + 1:14 + 18:27+2:22 +6:44 +22:56+9:44 +19:26 +3:04 +5:33 +9:33
内容:数组的练习和一些基本算法的讲解
心得:
关于main方法的细节
public static void main (String[] args){
}
String 类型的数组 命令行中用于输出后面的参数
技术分享

 

 
 
args[] 的数组
 
题外:
 
基本类型分配在栈空间里,如果想强行放到堆里面
就需要将他们包装成为对象 这些包装类 存放在java.lang包中
这些包装类里面还封装了很多处理这些数据类型的方法
 
练习题目:用上面的命令行参数 输入2,4,6,7,3,5,1,9,8
转换成INT类型数组 再从小到大排好序 输出出来
思路:
1.首先在命令行输入这些数 空格分开
2.接着把main方法参数里 String类型的数组args[]转成Int类型 可以用Integer.parseInt的方法转换
3.排序 可以手动排 例如冒泡选择插入快排(关于排序之前有一些专门的整理)
这里暂时不贴了,在笔记本的另外部分
或者用Java自带的排序Array.sort()
最后输出
 
这里重新整理一下快速排序 直接贴出my eclipse中写的代码了。
package 算法;
 
import com.jhdx.uitl.usualMethod;
 
/*算法思想:选定一个数字,以这个数字为基准,将数组一分为二,将比他小的放在他左边,比他大的放在他右边
 * 接着分别再对左右两边的小数组进行同样的递归操作,直到数组有序
 * */
public class 快速排序 {
public static int getMiddle(int[] array,int low,int high){
      int temp=array[low];//默认将数组的第一个数作为中轴
      while (low<high) {
            while (low<high&&array[high]>=temp) {//如果高位数字大于等于中轴数字,则将高位标记往前推一位
                  high--;
            }
            array[low]=array[high];      //一直推到小于中轴数字为止,将这个高位数字换到低位去
            while (low<high&&array[low]<=temp) {//同理如果低位数字小于等于中轴数字,则将低位标记往后推一位
                  low++;
            }
            array[high]=array[low];//同理一直推到低位标记的数字大于中轴数字为止,将这个低位数字换到高位去
      }
      array[low]=temp;//将中轴数字放到应该在的位置
      return low;
}
 
public static void quickSort(int[] array,int low,int high){
      if (low<high) {
            int middle=getMiddle(array, low, high);
            quickSort(array, low, middle-1);//对一分为二的低位数组再次分割排序
            quickSort(array, middle+1, high);//对一分为二的高位数组再次分割排序
      }
}
public static void main(String[] args) {
      int array[]=usualMethod.getRandomArray(1000000);
      usualMethod.beforeMethod(array);
      int low=0;
      int high=array.length-1;
      quickSort(array, low, high);
      usualMethod.afterMethod(array);
}
}
 
 
 
 
 
这里整理一下 二分查找(折半查找)
之前的整理中没有整理到的
 
首先是算法思想
思想:
 
二分查找又称折半查找,它是一种效率较高的查找方法。
折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。
折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
 
说简单点就是 小时候玩的猜数游戏 你让别人猜一个数 你告诉他是大了还是小了  然后你每次都猜一半 这样很快就可以猜中
 
 
public class BinarySearch {
        /**
        * 二分查找算法
        * @param srcArray 有序数组
        * @param key 查找元素
        * @return key的数组下标,没找到返回-1
        */ 
        public static void main(String[] args) {

            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}; 
            System.out.println(binSearch(srcArray, 0, srcArray.length - 1, 81)); 
        }

        // 二分查找递归实现 
        public static int binSearch(int srcArray[], int start, int end, int key) { 
            int mid = (end - start) / 2 + start; 
            if (srcArray[mid] == key) { 
                return mid; 
            } 
            if (start >= end) { 
                return -1; 
            } else if (key > srcArray[mid]) {  //根据条件判断返回大数组还是小数组
                                               //然后通过递归调用自己再找
                return binSearch(srcArray, mid + 1, end, key); 
            } else if (key < srcArray[mid]) { 
                return binSearch(srcArray, start, mid - 1, key); 
            } 
            return -1; 
        }
 
       // 二分查找普通循环实现 
        public static int binSearch(int srcArray[], int key) { 
            int mid = srcArray.length / 2; 
            if (key == srcArray[mid]) { 
                return mid; 
            } 

            int start = 0; 
            int end = srcArray.length - 1; 
            while (start <= end) { 
                mid = (end - start) / 2 + start; 
                if (key < srcArray[mid]) { 
                  end = mid - 1; 
                } else if (key > srcArray[mid]) { 
                    start = mid + 1; 
                } else { 
                    return mid; 
                } 
            } 
            return -1; 
        }
        
}
 
 
关于进阶的讨论:
 
优点:ASL≤log2n,即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
缺点:因要求有序,所以要求查找数列必须有序,而对所有数据元素按大小排序是非常费时的操作。另外,顺序存储结构的插入、删除操作不便利。
考虑:能否通过一次比较抛弃更多的部分(即经过一次比较,使查找范围缩得更小),以达到提高效率的目的。……?
可以考虑把两种方法(顺序查找和折半查找)结合起来,即取顺序查找简单和折半查找高效之所长,来达到提高效率的目的?实际上这就是分块查找的算法思想。
 
 
时间:2017年4月26日16:00:04~2017年4月26日16:10:34
章节:05章_15节 05章_16节
视频长度:13:00 +14:49
内容:二位数组
心得:
int a[][]={{1,2},{3,4,5},{7,8,9}};
Java中多维数组的声明和初始化应该从高纬到低纬
内存图可以看出 先内存里要先分配高维的才能继续指向低维的
技术分享

 

 
可以这样动态初始化
技术分享

 

 
 
关于数组的拷贝
public static void arraycopu(Object src,int srcPos,object dest int destPos ,int length)
几个参数分别是拷贝的数组,开始的位置,被拷贝位置的数组,开始的位置,拷贝的长度
是直接通过内存地址拷贝 改变指向的位置 
 
之前整理插入排序的时候 用到过这个方法 所以比较熟悉 要给插入的数留一个位置
 
      //算法部分
      for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                  if (array[i]<array[j]) {
                        int temp=array[i];
                        System.arraycopy(array, j, array, j+1, i-j);//复制数组,从j序列复制到j+1,腾出一个位子,下标是j
                        array[j]=temp;
                  }
            }
      }
 
时间:2017年4月26日16:10:40~2017年4月26日16:12:30
章节:05章_17
视频长度:00:51
内容:总结
心得:
知识点总结
数组的内存布局
常见算法

Java基础知识二次学习--第五章 数组