java数组
2018-12-20 本文已影响0人
ClawHub的技术分享
数组在内存中的存储
首先我们先看一段代码
/**
* <Description>数组<br>
*
* @author DaShi<br>
* @version 1.0<br>
* @taskId <br>
* @CreateDate 2018/12/20 14:50 <br>
*/
public class demo {
public static void main(String[] args) {
int[] a = new int[3];
System.out.println("a在内存中的地址" + a);
a[1] = 100;
System.out.println("数组a中第二个元素" + a[1]);
int[] b = {1,2,3};
System.out.println("b在内存中的地址" + b);
System.out.println("数组b中第二个元素" + b[1]);
int[] c = b;
System.out.println("c在内存中的地址" + c);
}
}
image.png
下面我们跟据上面的代码以及下面的图，来解释一下数组在内存中如何存储：
①首先程序从main方法开始执行，main方法会被加载到栈中（main方法进栈/压栈）
②然后执行int[] a = new int[3]这一句，new int[3]会在堆中开辟一块空间，然后数组对象a持有这一块空间的引用，数组每个元素在没被赋值的时候默认是0。
③然后把第二个元素换成100
image.png
数组排序
目前写到这里排序都有啥我都不知道我翻翻资料一个一个敲23333，我下面都只写升序的情况哈
①冒泡排序
冒泡排序就是把数组中的元素从头到尾两两比较，如果前面的数字比后面的大，那么这两个数互换位置，因此第一遍走完之后，最大的那个数一定在最末尾！第二遍的时候倒数第二大的数一定在倒数第二位，以此类推，下面上图，没图你说个JB0.0
image.png
代码实现：
public void bubbleSort(int [] numbers){
//交换数组用的
int temp = 0;
//看看数组大小一会才能知道循环多少遍啊
int length = numbers.length;
//外层循环 控制需要走多少遍
for(int i=0;i<length-1;i++){
//内层循环 控制每一次遍历要遍历 要前后比较几次
for(int k = 0;k < length - i -1;k++){
//如果前一个数大于后一个数 互换位置
if(numbers[k] > numbers[k + 1]){
temp = numbers[k +1];
numbers[k + 1] = numbers[k];
numbers[k]= temp;
}
}
}
}
②快速排序
快速排序的核心思想，就是选取一个基准值（通常都是第0位），然后把比基准值小的全放在他左边，大的全放在基准值右边，然后拆分成两个数组，再次选取基准值重复之前的步骤，直到每个小数组里面都只剩下一个数字，或者若干个相等的数字为止！
image.png
实现：
第1步：
选取基准然后左边比基准小，右边比基准大
public static int getMiddle(int[] numbers, int low,int high)
{
//数组的第一个作为基准
int temp = numbers[low];
//判断高位和低位不在一个位置上
while(low < high)
{
//高位坐标的数比基准大的时候，高位坐标前移 一定是大于等于啊，不然数组中有相同数字的时候，会陷入死循环！
//为什么里面也要判断low<high呢
while(low < high && numbers[high] >= temp)
{
high--;
}
//高位坐标的数字比基准小的时候，高位坐标指向的数字放在低位坐标所在的位置
numbers[low] = numbers[high];
//低位坐标的数字比基准小的时候，低位坐标后移
while(low < high && numbers[low] < temp)
{
low++;
}
//低位坐标的数字比基准大的时候，低位坐标指向的数字放在高位坐标所在位置
numbers[high] = numbers[low] ;
}
//现在已经跳出while循环，证明高低位坐标重合，那么这个位置放置基准
numbers[low] = temp ;
// 返回基准
return low ;
}
测试：
//test
public static void main(String args[]){
int[] a = {5,9,7,1,4,20,3};
getMiddle(a,0,a.length-1);
for(int array : a ){
System.out.print(array+",");
}
}
image.png
我们可以看到，以基准5为分水岭，左边都是比基准小的，右边都是比基准大的！
那么接下来我们要以基准为分界，把数组拆成两个
第2步：
使用递归，无限拆分！
public static void quickSort(int[] numbers,int low,int high)
{
if(low < high) {
//将numbers数组进行一分为二
int middle = getMiddle(numbers,low,high);
//对低字段表进行递归排序
quickSort(numbers, low, middle-1);
//对高字段表进行递归排序
quickSort(numbers, middle+1, high);
}
}
测试：
//test
public static void main(String args[]){
int[] a = {5,9,7,1,4,20,3};
//保证数组不为空，
if(a.length > 0){
quickSort(a,0,a.length-1);
}
for(int array : a ){
System.out.print(array+",");
}
}
image.png
看！已经排好了，是不是很厉害！！！！
③ 选择排序
快速排序的思想就是第一次选出最小的那个放在数组的第0位，第二次选出剩下的元素中最小的放在数组的第1位，以此类推~~~我们通过一张图来说一下步骤
image.png
简单说一下第一轮是怎么走的，第一轮我们待交换位置是第0位，i=0，我们从最后一位和第k=0位去比较，发现4比5小，那么我们会记录这个位置，此时K记录下数字4所在的位置（k=4），然后游标会继续往前走，1和k那个位置上的数字去比较，发现1比4小，那么此时k记录数字1所在的位置（k=3），游标继续往前一直到9，发现已经没有数字比1更小了，那么第一轮结束，数组的第0位和第K位交换位置！也就是1和5交换；第二轮待交换位置是数组第1位，依然从后往前比较，选出最小的，记录他的位置，和数组第1位交换，以此类推，直到指针指向数组最后一位，我们排序完成~~~
实现：
/**
* 选择排序算法
* 在未排序序列中找到最小元素，存放到排序序列的起始位置
* 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
* 以此类推，直到所有元素均排序完毕。
* @param numbers
*/
public static void selectSort(int[] numbers)
{
//数组的长度
int size = numbers.length;
//交换值的中介
int temp = 0 ;
for(int i = 0 ; i < size ; i++)
{
//记录当前最小值的位置
int k = i;
//从后往前比较一直到第i+1位结束
for(int j = size -1 ; j > i ; j--)
{
if(numbers[j] < numbers[k])
{
//k总是记录当前剩下的数字中最小的数的位置
k = j;
}
}
//把k位记录的最小值和第i位互换
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}
④ 插入排序
核心思想就是，把数组中的元素和他前面的有序数列依次比较，符合条件就交换位置。下面看张图
image.png
我们就仔细分析一下，第四轮的时候最末尾的数字4经历了什么吧
image.png
这样是不是就很清楚了呢？下面看一下代码实现：
public static void insertSort(int[] a){
//作为交换容器
int temp = 0;
for(int i = 1;i < a.length;i++){
// 从J位开始，依次和前面比较
for (int j=i; j>0 && a[j] < a[j-1];j--){
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
