二维数组和简单排序

不念不忘少年蓝@ 2023-10-10 14:26 47阅读 0赞

Java 语言中提供的数组是用来存储固定大小的同类型元素。

### **概述** ###

二维数组实际上是由多个一维数组组成的，它的各个一维数组的长度可以相同，也可以不相同。比如：map\[\]\[\]是一个二维数组

int map \[\]\[\] =\{ \{1，2\}，\{3，4，5\}\}

map\[0\]是一个含有两个元素的一维数组，map\[1\]是一个含有三个元素的一维数组。我们也称之为数列不等的二维数组。

### 声明方式 ###

一维数组声明方式有：

**int \[\] x** 或者 int x\[\]

二维数组声明方式有：

int\[\]\[\] y 或者int\[\] y\[\] 或者 int y\[\]\[\]

### 初始化 ###

#### 动态初始化 ####

> int \[\]\[\]a = new int\[3\]\[\];  
>   
> 该代码定义了一个变量为a的二维数组，这个数组变量指向了一个长度为3的的数组，  
> 这个数组中每个元素都是一个int类型的**数组**，所以默认值为**null**

> int \[\]\[\]a = new int\[5\]\[2\];  
>   
> //该代码定义了一个a数组变量，这个数组变量指向一个长度为5的数组，  
> 这个数组的元素又是一个数组类型，它们是3个长度为2的int\[\]数组，  
> 每个数组元素的值为0。

#### 静态初始化 ####

> int \[\]\[\]b = \{ \{1,2\},\{3,4,5\}\};
> 
> //该代码定义了一个b数组变量，这个数组变量指向一个长度为2的数组；
> 
> 这个数组的元素又是一个数组类型，它们是分别是b\[0\]长度为2的int\[\]数组，元素为1，2；b\[1\]长度为3的int\[\]数组，元素为3，4，5。

### 冒泡排序 （稳定) ###

#### 原理： ####

1、**比较相邻的元素**。如果前一个元素比后一个元素大，就交换这两个元素的位置。（若按从小到大的顺序）

2、对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。

#### 时间复杂度为O(n\*n) ####

### 选择排序 （不稳定） ###

#### 原理： ####

遍历元素**找到一个最小（或最大）的元素**，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。

#### 时间复杂度为 O(n^2) ####

### 插入排序 （稳定） ###

#### 原理： ####

1.从第一个元素开始，该元素可以认为已经排好序。  
2.取出下一个新元素，然后**把这个新元素在已经排好序的元素序列中从后往前扫描进行比较**。  
3.如果该元素(已排序) 大于新元素，则将这个已排序的元素移到下一个索引位置。  
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。  
5.将新元素插入到该已排序的元素的索引位置后面。  
6.重复步骤2~5

#### 时间复杂度为 O(n^2) ####

代码：

public class test {
        public static void main(String[] args) {
            int[] arr = {23, 45, 12, 8, 3, 2, 55, 34, 87, 21};
           /*
           //冒泡排序  （经过依次比较相邻的两个元素，将最值往后传，重复此动作）
           int temp = 0;
            for(int i = arr.length-1; i>0;i--){
                for(int j = 0;j<i;j++){
                    if(arr[j] > arr[j+1]){ //当前元素与后一位元素比较，若为大于，则交换位置
                        temp =arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
    
                    }
                }
            }
            //打印数组元素
            for(int i = 0; i < arr.length; i++){
                System.out.print(arr[i]+" ");
            }*/
    
    /*
            //选择排序  （遍历当前索引往后的元素，找出最小值，与当前索引的元素交换，当前索引加一；重复此动作）
    
            for(int i = 0; i<arr.length-1; i++){
                int minIdex = i; // 用来记录最小值的索引位置，默认为i；
                for(int j = i+1; j<arr.length; j++) {
                    if (arr[j] < arr[minIdex]) {
                        minIdex = j; //遍历i+1到arr.length的值，找出最小值的索引
                    }
                }
                if(i != minIdex){
                    //交换当前索引i和minIdex 的值
                    int temp = arr[i];
                    arr[i] = arr[minIdex];
                    arr[minIdex] = temp;
                }
                //执行完一次循环，当前索引i的值为最小值
            }
            for(int i = 0; i<arr.length; i++){
                System.out.print(arr[i]+" ");
            }*/
    
            //插入排序
            int j; // 已排序列表下标
            int t;  //待排序元素
            for (int i = 1; i < arr.length; i++) { //遍历数组1~length的元素
                if (arr[i] < arr[i - 1]) { //如果当前索引位置的值比已排序i-1 的值小
                    t = arr[i];
                    for (j = i - 1; j >= 0 && arr[j] > t; j--) {
                        arr[j + 1] = arr[j]; // 从后往前遍历已排序列表，逐个和待排序元素比较，如果已排序元素较大，则将它后移
                    }
                    arr[j + 1] = t; // 将待排序元素插入到正确的位置
    
                }
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }