java三种排序及二维数组

曾经终败给现在 2022-05-12 14:42 281阅读 0赞

# 排序 #

## 冒泡排序 ##

public class TestDemo {
        
        //冒泡排序
        public static void bubbleSort(int[] array) {
        
            boolean val = false;
            for (int i = 0; i < array.length - 1; i++) {
        
                for (int j = 0; j < array.length - 1 - i; j++) {
        
                    if (array[j] > array[j + 1]) {
        
                        int tmp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = tmp;
                        val = true;
                    }
                }
                if (!val) {
        
                    break;
                }
            }
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        1, 5, 15, 2, 9, 6, 35, 22};
            bubbleSort(array);
            System.out.println(Arrays.toString(array));
        }
    }

**时间复杂度：**  
最好情况 O(n) 当输入的数组有序就是最好情况  
最坏情况 O(n^2)  
**稳定性**：在输入数组中有两个及以上相同的数，排序结束后数字前后位置不变  
稳定

## 直接插入排序 ##

public class TestDemo {
           
        //直接插入排序
        public static void insertSort(int[] array) {
        
            int j = 0;
            for (int i = 1; i < array.length; i++) {
        
                int tmp = array[i];
                for (j = i - 1; j >= 0; j--) {
        
    
                    if (tmp < array[j]) {
        
                        array[j + 1] = array[j];
                    } else {
        
                        break;
                    }
                }
                array[j + 1] = tmp;
            }
        }
        
        public static void main(String[] args) {
        
            int[] array = {
        1, 5, 15, 2, 9, 6, 35, 22};
            insertSort(array);
            System.out.println(Arrays.toString(array));
        }
    }

**时间复杂度：**  
最好情况 O(n)  
最坏情况 O(n^2)  
**稳定性**：稳定

## 选择排序 ##

public class TestDemo {
          
        //选择排序
        public static void selectSort(int[] array) {
        
            for (int i = 0; i < array.length; i++) {
        
                for (int j = i + 1; j < array.length; j++) {
        
                    if (array[i] > array[j]) {
        
                        int tmp = array[j];
                        array[j] = array[i];
                        array[i] = tmp;
                    }
                }
            }
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        1, 5, 15, 2, 9, 6, 35, 22};        
            selectSort(array);
            System.out.println(Arrays.toString(array));        
        }
    }

**时间复杂度：**： O(n^2)  
**稳定性**：稳定

# 二维数组 #

## 定义 ##

int[][] array = new int[2][3];
    //第一种
    
    int[][] array2 = {
        {
        1,2,3},{
        4,5,6},{
        7,8,9}};
    //第二种
    
    int[][] array3 = new int[2][];
    array3[0] = new int[4];
    array3[1] = new int[5];
    //定义一个不规则数组

## 二维数组的拷贝 ##

与一维数组相同，四种拷贝方式皆为浅拷贝  
以下四种方法二维数组array1的初始值为10

#### for循环拷贝 ####

class Arr {
        
        private int val = 10;
    
        public void setVal(int val) {
        
            this.val = val;
        }
    
        public int getVal() {
        
            return this.val;
        }
    }
    
    public class TestDemo1 {
        
    	public static void main(String[] args) {
        
            Arr[][] array1 = new Arr[2][2];
            array1[0][0] = new Arr();
            array1[0][1] = new Arr();
            array1[1][0] = new Arr();
            array1[1][1] = new Arr();
            Arr[][] array2 = new Arr[2][2];
            for (int i = 0; i < array1.length; i++) {
        
                for (int j = 0; j < array1[i].length; j++) {
        
                    array2[i][j] = array1[i][j];
                }
            }
            for (int i = 0; i < array2.length; i++) {
        
                for (int j = 0; j < array2[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
            array2[0][0].setVal(100);
            System.out.println("================修改后===============");
    
            for (int i = 0; i < array2.length; i++) {
        
                for (int j = 0; j < array2[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

输出结果：  
![在这里插入图片描述][70]

#### .clone() ####

class Arr {
        
        private int val = 10;
    
        public void setVal(int val) {
        
            this.val = val;
        }
    
        public int getVal() {
        
            return this.val;
        }
    }
    
    public class TestDemo1 {
        
    	public static void main(String[] args) {
        
            Arr[][] array1 = new Arr[2][2];
            array1[0][0] = new Arr();
            array1[0][1] = new Arr();
            array1[1][0] = new Arr();
            array1[1][1] = new Arr();
            Arr[][] array2 = new Arr[2][2];
            for (int i = 0; i < array1.length; i++) {
        
                array2[i] = array1[i].clone();
                for (int j = 0; j < array1[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
            array2[0][0].setVal(100);
            System.out.println("================修改后===============");
            for (int i = 0; i < array2.length; i++) {
        
                for (int j = 0; j < array2[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
        }
    }

输出结果:  
![在这里插入图片描述][70 1]

#### Arrays.cpoyOf() ####

class Arr {
        
        private int val = 10;
    
        public void setVal(int val) {
        
            this.val = val;
        }
    
        public int getVal() {
        
            return this.val;
        }
    }
    
    public class TestDemo1 {
        
    	public static void main(String[] args) {
        
            Arr[][] array1 = new Arr[2][2];
            array1[0][0] = new Arr();
            array1[0][1] = new Arr();
            array1[1][0] = new Arr();
            array1[1][1] = new Arr();
            Arr[][] array2 = new Arr[2][2];
            //array2 = Arrays.copyOf(array1, array1.length);
            //或者将循环中的Arrays.copyOf方法删掉，用上一行的方法拷贝
            for (int i = 0; i < array1.length; i++) {
        
                array2[i] = Arrays.copyOf(array1[i], array1[i].length);
                for (int j = 0; j < array1[i].length; j++) {
        
                    // array2[j]=array1[j].clone();
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
            array2[0][0].setVal(100);
            System.out.println("================修改后===============");
            for (int i = 0; i < array2.length; i++) {
        
                for (int j = 0; j < array2[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
        }
    }

输出结果：  
![在这里插入图片描述][70 2]

#### System.arraycopy() ####

class Arr {
        
        private int val = 10;
    
        public void setVal(int val) {
        
            this.val = val;
        }
    
        public int getVal() {
        
            return this.val;
        }
    }
    
    public class TestDemo1 {
        
    	public static void main(String[] args) {
        
            Arr[][] array1 = new Arr[2][2];
            array1[0][0] = new Arr();
            array1[0][1] = new Arr();
            array1[1][0] = new Arr();
            array1[1][1] = new Arr();
            Arr[][] array2 = new Arr[2][2];
            for (int i = 0; i < array1.length; i++) {
        
                System.arraycopy(array1[i], 0, array2[i], 0, array1[i].length);            
                for (int j = 0; j < array1[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
            array2[0][0].setVal(100);
            System.out.println("================修改后===============");
            for (int i = 0; i < array2.length; i++) {
        
                for (int j = 0; j < array2[i].length; j++) {
        
                    System.out.print(array2[i][j].getVal() + " ");
                }
                System.out.println();
            }
        }
    }

输出结果：  
![在这里插入图片描述][70 3]

[70]: /images/20220504/461b37b9e8ba40b5861c918f4bd36fff.png
[70 1]: /images/20220504/98fdac4f20f742bcbfad295dd1bdb1b4.png
[70 2]: /images/20220504/12abef23ba9f40ca9bb67cfd5fd8a360.png
[70 3]: /images/20220504/0339326defe7444795795f393242f07e.png