@
目录
Part4：数组及其常用操作
- 数组：具有相同数据类型的数据的集合，可以存储基本数据类型的数据和引用类型的数据。数组是在内存中分配的一连串的空间。
- 声明方法：（以整型数组为例）
一维数组：int[] array 或 int array[];
二维数组：int[][] array 或 int array[][]; - Java语言中声明数组时不能指定其长度(数组中元素的数),应该是
int[] array = new int[10];
Example01：将二维数组的行列交换
运行结果：
实现代码：
public class Example01 {
public static void main(String[] args) {
int[][] array = {{1,2,3},{4,5,6},{7,8,9}};
System.out.println("行列调换前：");
exchange(array);
int[][] newArray = new int[array.length][array.length];
for (int i = 0;i<array.length;i++) { //调整数组行列数据
for (int j = 0; j < array.length; j++) {
newArray[i][j] = array[j][i];
}
}
System.out.println("行列调换后：");
exchange(newArray);
}
public static void exchange(int[][] array){
for (int i = 0;i<array.length;i++){ //遍历数组
for (int j = 0;j<array.length;j++){
System.out.print(array[i][j]+"\t");
}
System.out.println();
}
}
}
要点： 创建两个相同大小的数组，并使用双层的for循环遍历这两个二维数组，同时把新数组与原数组的行列索引交换进行元素赋值，从而实现行列互换的功能。
Example02：使用选择排序法对数组进行排序
选择排序(Selection Sort)是一种简单直观的排序算法。
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。-
过程如下：
初始数组 【63 4 24 1 3 15】
第一趟排序 【4 24 1 3 15】 63
第二趟排序 【4 1 3 15】 63 24
第三趟排序 【4 1 3】 15 24 63
第四趟排序 【1 3】 4 15 24 63
第五趟排序 【1】 3 4 15 24 63
运行结果：
实现代码：import java.util.Random; public class Example02 {
public static int[] array = new int[10];
public static void main(String[] args) {
Random random = new Random();
System.out.println("初始数组为：");
for (int i = 0;i<array.length;i++){
array[i] = random.nextInt(50);//生成50以内的随机数组
System.out.print(array[i]+" ");
}
System.out.println("\n选择排序后的数组为：");
SelectSort(array);
}
public static void SelectSort(int[] array){
int index = 0;
for (int i = 0;i<array.length-1;i++) {
index = i;
for (int j = i+1; j < array.length; j++) {
if (array[j]<array[index]) {
index = j;
}
}
//交换在array.length-i和index（最大值）位置的两个数
if (i != index) {
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
for (int num:array) {
System.out.print(num+" ");
}
}
} 要点：利用选择排序法从数组中挑选最大值并放在数组最后，而遇到重复的相等值不会做任何处理，所以如果程序允许数组有重复值的情况，建议使用选择排序法，因为它的数据交换次数较少，相对速度也会稍微提升，这取决于数组中重复值的数量。
Example03：使用冒泡排序法对数组进行排序
运行结果:
实现代码：
import java.util.Random;
public class Example03 {
public static int[] array = new int[10];
public static void main(String[] args) {
Random random = new Random();
System.out.println("初始数组为：");
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(50);//生成50以内的随机数组
System.out.print(array[i] + " ");
}
System.out.println("\n冒泡排序后的过程为：");
BubbleSort(array);
}
public static void BubbleSort(int[] array){
for (int i = 1;i<array.length;i++) {
//比较相邻两个元素，较大的往后冒泡
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j]; //把第一个元素值保存到临时变量中
array[j] = array[j + 1]; //把第二个元素值保存到第一个元素单元中
array[j + 1] = temp; //把临时变量也就是第一个元素原值保存到第二个元素中
}
System.out.print(array[j]+" ");
}
System.out.print("【");
for (int j = array.length-i;j<array.length;j++){
System.out.print(array[j]+" ");
}
System.out.print("】\n");
}
}
}
- 要点：冒泡排序的基本思想是对比相邻元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把大的元素移动到数组后面。冒泡算法在双层循环中实现，其中外层循环中实现，是要排序数组长度-1次。而内层循环主要是用于比较临近元素的大小，以确定是否交换位置，对比和交换次数依排序轮数而减少。
Example04：使用快速排序法对数组排序
- 快速排序（Quick Sort）是对冒泡排序的一种改进，其排序速度相对较快。
- 过程如下：（通常选第一个数据）
先用基准值和最后一个值比较，直到找到第一个比基准值小的值才交换。找到这个值后，又从前往后开始比较，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前的索引，结束第一次循环。
运行结果：
实现代码：
import java.util.Random;
public class Example04 {
public static int[] array = new int[10];
public static void main(String[] args) {
Random random = new Random();
System.out.println("初始数组为：");
for (int i = 0;i<array.length;i++){
array[i] = random.nextInt(50);//生成50以内的随机数组
System.out.print(array[i]+" ");
}
System.out.println("\n快速排序法的过程如下：");
QuickSort(array,0,array.length-1);
}
public static void QuickSort(int[] array,int low,int high) {
int min = low;
int max = high;//最小索引和最大索引
int key = array[low]; //分界点元素
while (min < max) {
//从后往前比较
while ((min < max) && (array[max] >= key)) {
//如果没有比关键值小的比较下一个，直到找到比分界点小的交换位置
max--;
}
if (min < max){
swap(array,min,max);
min++;
}
while ((min < max) && (array[min] <= key)) {
//直到找到比关键值大的交换位置
min++;
}
if (min < max) {
swap(array, min, max);//交换两个索引的值
max--;
}
}
//对key左边快排
if (min > low) {
QuickSort(array, low, min - 1);
}
//对key右边快排
if (max < high) {
QuickSort(array, min + 1, high);
}
}
public static void swap(int swapArray[],int i,int j){
int t = swapArray[i];
swapArray[i] = swapArray[j];
swapArray[j] = t;
for (int k = 0;k<array.length;k++){
System.out.print(array[k]+" ");
}
System.out.println();
}
}
要点：快速排序法的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这两部分数据进行快速排序。整个排序过程可以递归进行，以此使整个数据变成有序数列。
- 快速排序还有更高效的实现方法，请尝试。------
Example05：使用直接插入法对数组进行排序
- 插入排序的思想：将n个有序数存放在数组a中，要插入的数为x，首先确定x插在数组中的位置p，数组中p之后的元素都后移一个位置，空出a(p)，并将x插入进去。
运行结果：
实现代码：
import java.util.Random;
public class Example05{
public static int[]array=new int[7];
public static void main(String[]args){
Random random=new Random();
System.out.println("初始数组为：");
for(int i=0;i<array.length;i++){
array[i]=random.nextInt(50);//生成50以内的随机数组
System.out.print(array[i]+" ");
}
System.out.println("\n直接插入排序法后的数组为：");
InsertSort();
}
public static void InsertSort(){
int t,j;
for(int i=1;i<array.length;i++){
t = array[i];
for (j = i-1;j >= 0 && array[j] > t;j--){
array[j+1] = array[j]; //数组元素交换
}
array[j+1] = t;
}
for (int a:array){
System.out.print(a+" ");
}
}
}
- 在使用排序算法时，开发人员必须手动编写一堆代码，有的实现起来比较麻烦。Java的Arrays类提供了sort()，使用该方法对数组进行排序，大大降低了数组排序的难度。
Example06：使用sort()方法对数组排序
运行结果：
代码实现：
import java.util.Arrays;
import java.util.Scanner;
public class Example06 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入：");
String s = scanner.nextLine();
String[] array = s.split(" "); //拆分输入的数组
int[] newArray = new int[array.length]; //创建整型数组
System.out.println("初始数组为：");
for (String string : array){
System.out.print(string+" ");
}
for (int i = 0;i<array.length;i++){ //初始化整型数组
newArray[i] = Integer.parseInt(array[i]);
}
Arrays.sort(newArray); //使用sort()方法对整型数组排序
System.out.println("\nsort()排序后的结果为：");
for (int a : newArray){
System.out.print(a+" ");
}
}
}
- 要点：Arrays类提供了创建、操作、搜索和排序数组的方法。Arrays类位于java.util包，它是数组的一个工具类，包含很多方法，它有很多重载格式，可以接收任何数据类型的数组并执行不同类型的排序。