【Java】从头开始的Java复健day8-526互联

用的书：《Java从入门到精通》

第六章数组

6.5 数组排序算法

冒泡排序

最常用的数组排序算法之一总是把小数往前放大数往后放像水中冒泡一样故得此名

基本思想

对比相邻元素值如果满足条件就交换元素值

把较小的元素移动到数组前边大的元素移动到数组后边

看图就很清楚了

图源：菜鸟教程

在第一轮结束之后最大的那个就已经垫底了在第二轮的时候只用比较到倒数第二个就行了

因为是两两比较所以轮次是长度减一 eg 三个数字的情况下两两比较只要2轮就可以了
算法示例

冒泡算法由双层循环实现
- 外层用于控制排序轮数一般要为数组长度-1 因为最后一次循环只剩下一个数组元素不需要对比
- 内层主要用于对比数组中每个邻近元素的大小以确定是否交换位置
算法实现

直接选择排序

比冒泡排序稍微快些

基本思想

将指定排序位置与其他数组元素分别对比如果满足条件就交换元素值

与冒泡排序的区别

不是交换相邻元素而是交换指定的排序位置的元素
算法示例

每一轮次从中选出最小（或最大）的一个元素放在最后
算法实现

反转排序

就是把数组倒序

基本思想

最后一个元素和第一个元素替换倒数第二和第二个替换 ……
算法实现

public class Java6_5 {
    public static void main(String[] args) {
        int[] arr = {4, 7, 2, 6, 2, 6, 1, 4};
        //bubbleSort(arr);
        Java6_5 sorter = new Java6_5();
        // sorter.bubbleSort(arr);
        // sorter.selectSort(arr);
        sorter.reverseSort(arr);
        sorter.showArr(arr);
    }

    // 这里给出了两套方法
    // 一套是被注释掉的使用静态函数然后main函数中直接调用
    // 另一套是创建类的实例之后访问成员函数
    // 如果不需要访问实例变量 如辅助函数 工具函数 则静态方法比较好
    // 如果需要需要访问对象状态和成员变量则使用创建实例的方法
    // public static void bubbleSort(int[] arr){
    public void bubbleSort(int[] arr){
        // 外层控制排序轮数
        for (int i=0; i < arr.length - 1; i++){
            // 内层对比数组中每个邻近元素的大小
            for (int j=0; j < arr.length-(i+1); j++){
                // 比较相邻元素大小 若左大于右则交换位置
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        /*
        这部分太常用了 拿出来写成一个函数
        for (int i : arr){
            System.out.print(i + " ");
        }
        */
    }

    public void selectSort(int[] arr) {
        int index;
        // 外层控制排序轮数
        for (int i = 1; i < arr.length; i++){
            // 每轮开始之前都要重置一下位置
            index = 0;
            // 因为index初始=0 故从arr[1]开始比较
            for (int j=1; j <= arr.length-i; j++){
                // 当前最大值的索引
                if (arr[j] > arr[index]){
                    index = j;
                }
            }
            // 交换最大值和最后一个未排序的元素的位置
            int temp = arr[arr.length-i];
            arr[arr.length-i] = arr[index];
            arr[index] = temp;
        }
    }

    public void reverseSort(int[] arr){
        int temp;
        for (int i=0; i<arr.length / 2; i++){
            temp = arr[i];
            arr[i] = arr[arr.length-(i+1)];
            arr[arr.length-(i+1)] = temp;
        }
    }

    public void showArr(int[] arr){
        for (int i : arr){
            System.out.print(i + " ");
        }
    }
}

6.6 小结略

略

6.7 测试

import java.util.Arrays;

public class Java_Test6_7 {
    public static void main(String[] args) {
        System.out.println("创建数组arr1和arr2 将arr1中索引位置是0~3的元素复制到arr2中");
        int[] arr1 = {1, 2, 6, 7, 5};
        int[] arr2;
        // 注意这里的终点索引应该是 4，不包含终点元素本身
        arr2 = Arrays.copyOfRange(arr1, 0, 4);
        showArr(arr1);
        showArr(arr2);
        System.out.println("将数组中最小的数输出");
        int min = arr1[0];
        for (int i : arr1){
            if (i < min){
                min = i;
            }
        }
        System.out.println(min);
        System.out.println("将arr中索引位置是2的元素替换为'bb'");
        String[] arr = {"hello", ",", " ", "world", "!"};
        for (String i : arr){
            System.out.print(i + " ");
        }
        System.out.println("");
        arr[2] = "bb";
        for (String i : arr){
            System.out.print(i + " ");
        }
        System.out.println("");
        System.out.println("将二维数组的行列互调显示出来 类似于转置矩阵");
        int[][] arr3 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[][] arr4 = new int[3][3];
        for (int i=0; i < arr3.length; i++){
            for (int j=0; j < arr3[i].length; j++){
                arr4[i][j] = arr3[j][i];
                System.out.print(arr4[i][j]);
            }
            System.out.println();
        }

    }

    public static void showArr(int[] arr){
        for (int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}