Java中的选择排序和冒泡排序思想及代码实现

选择排序

选择排序基本思想(假设从大到小排序)：

初始化一个数组：int[] array={n个数据}

第1次排序：将索引为0的元素取出来，用该元素与之后的每一个元素做比较，比该元素小则不动，比该元素大则交换二者的数值，依次比较到最后，这样最大值就放到了索引为0的位置

第2次排序：将索引为1的元素取出来，用该元素与之后的每一个元素做比较，比该元素小则不动，比该元素大则交换二者的数值，依次比较到最后，这样数组中第二大值就放到了索引为1的位置

依次类推，将倒数第2个元素取出来，与最后一个元素做比较，比该元素小则不动，比该元素大则交换二者的位置

// 用代码实现上述思想
public class SelectSort {
    public static void main(String[] args) {
        // 静态初始化一个int类型的数组
        int[] array = {,,,,};

        // 第1次排序：取索引为0的元素与之后的元素做比较
        for (int x = ; x < array.length; x++) {
            if (array[] < array[x]) {
                int temp = array[];
                array[] = array[x];
                array[x] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
        // 输出结果为:[43, 1, 4, 6, 23]

        // 第2次排序：取索引为1的元素与之后的元素做比较
        for (int x = ; x < array.length; x++) {
            if (array[] < array[x]) {
                int temp = array[];
                array[] = array[x];
                array[x] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
        // 输出结果为：[43, 23, 1, 4, 6]

        // 第3次排序：取索引为2的元素与之后的元素做比较
        for (int x = ; x < array.length; x++) {
            if (array[] < array[x]) {
                int temp = array[];
                array[] = array[x];
                array[x] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
        // 输出结果为：[43, 23, 6, 1, 4]

        // 第4次排序：取索引为3的元素与之后的元素做比较
        for (int x = ; x < array.length; x++) {
            if (array[] < array[x]) {
                int temp = array[];
                array[] = array[x];
                array[x] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
        // 输出结果为：[43, 23, 6, 4, 1]
    }
}
           

观察上面的代码，我们发现如下规律：

1、for循环内容格式一样

2、排序次数为：数组长度-1(依次取出数组前n-1个元素与之后的元素做比较，最后一个不用取出)

3、每次排序，需要进行比较的次数为：从取出索引位置后面第一个元素开始到末尾，即从i+1次开始，到array.length-1

改进后的代码

// i 控制排序次数，取值从0到array.length-2，最后一个元素不用取出
        for(int i =  ;i<array.length-;i++) {  

        /* j 控制每次排序比较次数，每次比较从取出来要比较的值后面第一个元素
        开始，到该数组最后一个元素比较结束，所以每次比较j从i+1开始，到
        array.length-1结束*/

            for(int j = i+;j<array.length;j++) { 
                if(array[i]<array[j]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    count++;
                }
            }
        }
        System.out.println(Arrays.toString(array));
           

冒泡排序

冒泡排序基本思想(假设从大到小排序)：

第一次排序：将数组中的元素从0索引开始，两两做比较，数值较小者往后放，这样最小值就到了数组末尾

第二次排序：从0索引开始，两两做比较，数值较小者往后放，一直比到倒数第二个数，这样数组中第二小的数就放到了倒数第二的位置

依次类推，最后依次比较0索引和1索引两个位置元素的大小，较小者往后放

代码实现如下：

public class BubbleSort {
    public static void main(String[] args){
        //初始化一个数组
        int[] arr = {,,,,};

        //外层for循环代表排序次数，数组长度为arr.length-1，共比较arr.length-2次；
        for(int i = ;i<arr.length-;i++) {

            //内层for循环代表每次排序比较的次数，每次都是从0索引开始比较；
            //第一次从0比到arr.length-1,比较arr.length-2-0次;
            //第二次从0到arr.length-2，比较arr.length-2-1次;
            //......
            for(int j = ;j<arr.length--i;j++) {
                if(arr[j]<arr[j+]) {
                    int temp = arr[j];
                    arr[j] = arr[j+];
                    arr[j+] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
//输出结果为：[43, 23, 6, 4, 1]
           

选择排序和冒泡排序

选择排序是把每次比出来的结果往前放，冒泡排序是把每次比出来的结果往后放。

关于这两把排序方法，最主要的是掌握其思想，具体推理过程无须掌握，知道如何使用即可。