【Java】从头开始的Java复健day8

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

day1(3.1-3.3): 【Java】从头开始的Java复健day1

day2(3.4-3.8): 【Java】从头开始的Java复健day2

day3(4.1-4.4): 【Java】从头开始的Java复健day3

day4(4.5-5.2): 【Java】从头开始的Java复健day4

day5(5.3-5.4): 【Java】从头开始的Java复健day5

day6(5.5-5.9): 【Java】从头开始的Java复健day6

day7(6.1-6.4): 【Java】从头开始的Java复健day7

第六章 数组

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();
    }
}