Java基础学习——数组及其常用算法(冒泡排序、二分查找)
数组
所谓数组,是有序的元素序列。在java语言中,数组是一种最简单的复合数据类型,它是由一些具有相同的数据类型的元素所构成的,可以用一个统一的数组名和下标来唯一地确定数组中的元素。数组有一维数组和多维数组。
一维数组
创建格式
其中第1、2种较为常用
1、数据类型[ ] 数组名称 = {数组内容1,数组内容2,……,数组内容n};
// 示例如下
int[] age = {1, 2, 3 ,4};
2、数据类型[ ] 数组名称 = new 数据类型[数组长度];
// 示例如下
int[] age = new int[4];
3、数据类型 [ ] 数组名称 = new 数据类型[ ] {数组内容1,数组内容2,……,数组内容n};
// 示例如下
int[] age = new int[]{1, 2, 3 ,4};
4、数据类型[ ] 数组名;
该种方法只创建了数组引用名,并未在内存中创建数组空间,只能通过以下方式进行初始化设置。
// 示例如下
int[] age;
age = new int[4];
通过下标对数据进行操作
赋值操作:
数组名[下标] = 值;
// 把13赋予了age数组中的第一个元素,该元素在数组中的编号为0
age[0] = 13;
取值操作:
数组名[下标]
// 示例如下
age[0];
获取数组的长度
数组名称.length
// 示例如下
age.length;
二维数组
创建格式
数据类型[ ][ ] 数组名 = new 数据类型[长度][(可写可不写) ];
// 示例如下
int[][] age = new int [4][];
数组常用算法
冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
【以下以升序排列为例】
算法原理
1、比较相邻两个数值的大小,将数值较大的移动到右边。
2、对每一对相邻元素都进行1中的比较,直到所有相邻元素都经过了比较。此时完成一次外层循环,将最大的数值移动到了数组最右边。
3、重复1、2的操作,直至所有的元素在数组中都按照从小到大的顺序排列。
算法实现
以数组nums = {1,15,9,5,7}为例
初始状态:
1 | 15 | 9 | 5 | 7 |
---|
第一次循环:
第1趟排序:
1和15相比较
1 | 15 | 9 | 5 | 7 |
---|
第2趟排序:
15和9相比较
1 | 9 | 15 | 5 | 7 |
---|
第3趟排序:
15和5相比较
1 | 9 | 5 | 15 | 7 |
---|
第4趟排序:
15和7相比较
1 | 9 | 5 | 7 | 15 |
---|
第二次循环:
第1趟排序:
1和9相比较
1 | 9 | 5 | 7 | 15 |
---|
第2趟排序:
9和5相比较
1 | 5 | 9 | 7 | 15 |
---|
第3趟排序:
9和7相比较
1 | 5 | 7 | 9 | 15 |
---|
第三次循环:
第1趟排序:
1和5相比较
1 | 5 | 7 | 9 | 15 |
---|
第2趟排序:
5和7相比较
1 | 5 | 7 | 9 | 15 |
---|
第四次循环:
第1趟排序:
1和5相比较
1 | 5 | 7 | 9 | 15 |
---|
最终输出
1 | 5 | 7 | 9 | 15 |
---|
代码实现
// 示例如下
int[] nums = {1,15,9,5,7};
for(int i=0; i<nums.length; i++) {
for(int j=0; j<nums.length-i-1; j++) {
//如果nums[j+1]的值小于nums[j],则交换两者位置,使得较大的数字在右边
if(nums[j+1]<nums[j]) {
nums[j+1] = nums[j] + nums[j+1];
nums[j] = nums[j+1] - nums[j];
nums[j+1] = nums[j+1] - nums[j];
}
}
}
//利用for循环输出数组
System.out.println("排序后的数组:");
for(int i=0; i<nums.length;i++)
System.out.print(nums[i]+" ");
编译结果
二分查找
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
算法原理
1、假设数组中元素是有序排列,将数组中间位置的数据与查找数据比较,如果两者相等,则查找成功。
2、否则利用中间位置记录将数组分成前、后两个子数组,如果中间位置数据大于查找数据,则进一步查找前子数
组,否则进一步查找后子数组。
3、重复以上过程,直到找到满足条件的数据,则表示查找成功,直到子数组不存在为止,表示查找不成功。
实现步骤
1、确定查找范围,最小——最大
2、计算中间下标 =(最小+最大)/2
3、比较中间下标和寻找的数据大小关系,如果中间下标所对应的元素比所寻找的数字小,则证明所要寻找的数字在数组的右半段,令最小下标 = 中间下标 + 1,中间下标 =(最小+最大)/2,最大下标不变,继续寻找。
4、如果最小下标 > 最大下标,说明数据不存在
代码实现
// 示例如下
//使用二分法查找6,nums为上述冒泡排序示例
int a = 6;
int max = nums.length - 1;
int min = 0;
int mid = (max + min)/2;
while(true) {
if(nums[mid] == a)
break;
//所要查找的数字在右半段
else if(nums[mid] < a) {
min = mid + 1;
mid = (max + min)/2;
}
//所要查找的数据在左半端
else if(nums[mid] > a) {
max = mid - 1;
mid = (max + min)/2;
}
if(min > max){
mid = -1;
break;
}
}
if(mid == -1)
System.out.println("没有这个数");
else
System.out.println("找到了"+a+",其下标为:"+mid);
编译结果:
当a = 6时,即所要查找的数字是6
当a = 9时,即所要查找的数字是9