数组的反转和添加和冒泡排序

时间：2023-02-15 12:58:45

1. 数组的反转

1.1 要求：把数组的元素内容反转。arr {11,22,33,44,55,66} 反转成{66, 55,44,33,22,11}

1.1.1 方法1 while循环

public class Test19
{
public static void main(String[] args)
  {
int arr[] = {11,22,33,44,55,66};
int left=0;//定义左下标
int right=arr.length-1;//定义右下标
while(left<right)//当左下标小于右下标时才会停止循环
    {
int tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
left++;//left和right左右移动可以实现元素的交换
right--;
    }
for(int i=0;i<arr.length;i++)
    {
System.out.print(arr[i]+" ");//输出打印
    }
  }
}

1.1.2 方法2 for循环

//思路  
//1. 把 arr[0] 和 arr[5] 进行交换 {66,22,33,44,55,11}
//2. 把 arr[1] 和 arr[4] 进行交换 {66,55,33,44,22,11} 
//3. 把 arr[2] 和 arr[3] 进行交换 {66,55,44,33,22,11} 
//4. 一共要交换 3 次 = arr.length / 2 
//5. 每次交换时，对应的下标 是 arr[i] 和 arr[arr.length - 1 -i]
public class Test19
{
public static void main(String[] args)
  {
int arr[] = {11,22,33,44,55,66};
int temp = 0;//临时变量
int len = arr.length;//计算长度
for(int i=0;i<len/2;i++)
    {
temp=arr[len-1-i];
arr[len-1-i]=arr[i];
arr[i]=temp;
    }
for(int i=0;i<len;i++)
    {
System.out.print(arr[i]+" ");
    }
  }
}

方法3 使用逆序赋值方式 167

//使用逆序赋值方式 
//思路 
//1. 先创建一个新的数组 arr2 ,大小 arr.length
//2. 逆序遍历 arr ,将 每个元素拷贝到 arr2 的元素中(顺序拷贝) 
//3. 建议增加一个循环变量 j -> 0 -> 5
public class Test19
{
  public static void main(String[] args)
  {
    int arr1[] = {11,22,33,44,55,66};
    int arr2[] = new int[arr1.length];
    for(int i=arr1.length-1,j=0;i>=0;i--,j++)//i是arr1的逆序，j是arr2的正序
    {
      arr2[j]=arr1[i];
    }
    //4. 当 for 循环结束，arr2 就是一个逆序的数组 {66, 55, 44,33, 22, 11} 
    //5. 让 arr 指向 arr2 数据空间, 此时 arr 原来的数据空间就没有变量引用 会被当做垃圾，销毁
    arr1 = arr2;
    for(int i=0;i<arr1.length;i++)
    {
      System.out.print(arr1[i]+" ");
    }
  }
}

2. 数组的添加 168

2.1 添加

要求：实现动态的给数组添加元素效果，实现对数组扩容。

1) 原始数组使用静态分配 int[] arr = {1,2,3}

2) 增加的元素 4，直接放在数组的最后 arr = {1,2,3,4} 

public class Test19
{
public static void main(String[] args)
  {
// 思路分析 
// 1. 定义初始数组 int[] arr = {1,2,3}//下标 0-2 
// 2. 定义一个新的数组 int[] arrNew = new int[arr.length+1]; 
// 3. 遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组 
// 4. 将 4 赋给 arrNew[arrNew.length - 1] = 4;把 4 赋给 arrNew 最后一个元素
// 5. 让 arr 指向 arrNew ; arr = arrNew; 那么 原来 arr 数组就被销毁
// 6. 创建一个 Scanner 可以接受用户输入 
// 7. 因为用户什么时候退出，不确定，老师使用 do-while
int arr[]={1,2,3};
int arrNew[]=new int[arr.length+1];//扩容
//遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组
for(int i=0;i<arr.length;i++)
    {
arrNew[i]=arr[i];
    }
arrNew[arrNew.length-1]=4;
//让 arr 指向 arrNew
arr=arrNew;
//输出
for(int i=0;i<arr.length;i++)
    {
System.out.print(arr[i]+" ");
    }
  }
}

3) 用户可以通过如下方法来决定是否继续添加，添加成功，是否继续？y/n 169

import java.util.Scanner;
public class Test19
{
public static void main(String[] args)
  {
// 思路分析 
// 1. 定义初始数组 int[] arr = {1,2,3}//下标 0-2 
// 2. 定义一个新的数组 int[] arrNew = new int[arr.length+1]; 
// 3. 遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组 
// 4. 将 4 赋给 arrNew[arrNew.length - 1] = 4;把 4 赋给 arrNew 最后一个元素
// 5. 让 arr 指向 arrNew ; arr = arrNew; 那么 原来 arr 数组就被销毁
// 6. 创建一个 Scanner 可以接受用户输入 
// 7. 因为用户什么时候退出，不确定，老师使用 do-while
Scanner myScanner = new Scanner(System.in);
int arr[]={1,2,3};
do
    {
int arrNew[]=new int[arr.length+1];//扩容
//遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组
for(int i=0;i<arr.length;i++)
      {
arrNew[i]=arr[i];
      }
System.out.println("请输入要添加的元素");
int addNum = myScanner.nextInt();
//把 addNum 赋给 arrNew 最后一个元素
arrNew[arrNew.length-1]=addNum;
//让 arr 指向 arrNew
arr=arrNew;
//输出
for(int i=0;i<arr.length;i++)
      {
System.out.print(arr[i]+" ");
      }
System.out.println("还要继续添加吗y/n");
char key = myScanner.next().charAt(0);
if(key=='n')
      {
break;
      }
      }while(true);
System.out.println("以退出程序……");
  }
}

2.2 缩减

课后练习题

有一个数组 {1， 2， 3， 4， 5}， 可以将该数组进行缩减，提示用户是否继续缩减，每次缩减最后那个元素。当只剩 下最后一个元素，提示，不能再缩减。

import java.util.Scanner;
public class Test19
{
public static void main(String[] args)
  {
Scanner myScanner=new Scanner(System.in);
int arr[]={1,2,3,4,5};
int count=arr.length-1;
for(int i=0;i<arr.length;i++)
    {
System.out.print(arr[i]+" ");
    }
while(true) 
    {
System.out.println("是否要缩减y/n");
char c = myScanner.next().charAt(0);
if(c=='n')
      {
break;
      }
else
      {
int arrNew[]=new int[arr.length-1];//减容
for(int i=0;i<arrNew.length;i++)//遍历数组
        {
arrNew[i]=arr[i];
        }
arr=arrNew;
for(int i=0;i<arr.length;i++)
        {
System.out.print(arr[i]+" ");
        }
count--;
      }
if(count==0)
      {
System.out.println("这是最后一个元素不能缩减了");
break;
      }
    }
  }
}

3. 排序

排序是将多个数据，依指定的顺序进行排列的过程。

3.1 排序的分类：

3.1.1 内部排序:

指将需要处理的所有数据都加载到内部存储器中进行排序。包括(交换式排序法、选择 式排序法和插入式排序法)；

3.1.2 外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括(合并排序法和直接合并排序法)。

3.1.3 冒泡排序法

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素 的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

4. 重点介绍冒泡排序 172

下面我们举一个具体的案例来说明冒泡法。我们将五个无序：24,69,80,57,13 使用冒泡排序法将其排成一个从小到大的有 序数列。

4.1 思路

数组的反转和添加和冒泡排序

4.2 分布做法 173

public class Test20  
{
public static void main(String[] args)
  {
//数组 [24,69,80,57,13]
// 第 1 轮排序: 目标把最大数放在最后 
// 第 1 次比较[24,69,80,57,13] 
// 第 2 次比较[24,69,80,57,13]
// 第 3 次比较[24,69,57,80,13] 
// 第 4 次比较[24,69,57,13,80]
int[] arr = {24, 69, 80, 57, 13,};
int temp = 0;//辅助交换变量
for(int j=0;j<4;j++)
    {
if(arr[j]>arr[j+1])
      {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
      }
    }
System.out.println("====第一轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }

// 第 2 轮排序: 目标把第2大的数放在倒数第2的位置 
// 第 1 次比较[24,69,57,13,80] 
// 第 2 次比较[24,57,69,13,80]
// 第 3 次比较[24,57,13,69,80]
for(int j=0;j<4;j++)
    {
if(arr[j]>arr[j+1])
      {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
      }
    }
System.out.println("\n====第二轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }

// 第 3 轮排序: 目标把第3大的数放在倒数第3的位置 
// 第 1 次比较[24,57,13,69,80] 
// 第 2 次比较[24,13,57,69,80]
for(int j=0;j<4;j++)
    {
if(arr[j]>arr[j+1])
      {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
      }
    }
System.out.println("\n====第三轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }

// 第 4 轮排序: 目标把第4大的数放在倒数第4的位置 
// 第 1 次比较[13,24,57,69,80]
for(int j=0;j<4;j++)
    {
if(arr[j]>arr[j+1])
      {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
      }
    }
System.out.println("\n====第四轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }
  }
}

4.3 冒泡做法 173

n个元素需要排n-1趟

n个元素需要交换n-1-i次

//n个元素需要排n-1趟
//n个元素需要交换n-1-i次
public class Test20  
{
public static void main(String[] args)
  {
int[] arr = {24, 69, 80, 57, 13};
int temp = 0;//辅助交换变量
for(int i=0;i<arr.length-1;i++)
    {
for(int j=0;j<arr.length-1-i;j++)//交换元素
      {
if(arr[j]>arr[j+1])
        {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
        }
      }
System.out.println("\n====第"+(i+1)+"轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }
    }
  }
}

4.4 冒泡排序优化

public class Test20  
{
public static void main(String[] args)
  {
int[] arr = {24, 13,57,69, 80};
int temp = 0;//辅助交换变量
for(int i=0;i<arr.length-1;i++)
    {
int flag =1;//假设数组已经整序
for(int j=0;j<arr.length-1-i;j++)//交换元素
      {
if(arr[j]>arr[j+1])
        {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=0;//说明数组还不有序
        }
      }

System.out.println("\n====第"+(i+1)+"轮====");
for(int j=0;j<arr.length;j++)
    {
System.out.print(arr[j]+" ");
    }
if(flag==1)//数组有序则跳出循环，不在排序
      {
break;
      }
    }
  }
}













标签：

相关文章