[数据结构与算法]Java——冒泡排序法，选择排序法和插入排序法

1.冒泡排序法

1.1 算法描述

1）比较相邻的元素，后面数比前面的大，则需要交换两个数的值；

2）重复第一步的工作，直到最大的值排在最后；

3）重复1）2）的工作，剩下的数中最大的值排在已经排完的值前面一个；

1.2 程序编写

import java.util.Arrays;

public class Bubblesort {
    public static void main(String[] args) {
        //生成长度为10的随机数的整形数组
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(a));
        //冒泡排序
        //最后一轮就一个数了，不用比较，轮数可以减一
        for (int i = 0; i < a.length - 1; i++) {
            int flag = 0;
            //每一轮确定一个值，内循环需要把这个值除去不比较，每轮次数减一，因此-i
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    flag=1;
                    int tmp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = tmp;
                }
            }
            if (flag == 0) {
                System.out.println("经过" + i + "轮，排序完成");
                break;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

2.选择排序法

2.1 算法描述

1）每轮确定一个基准值，向后遍历，找到最小值，交换位置；

2）每一轮确定一个最小值；

3）记录最小值的值和位置；

4）把最小值位置的值和基准值互换；

2.2 程序编写

import java.util.Arrays;

public class Selectionsort {
    public static void main(String[] args) {
        //生成长度为10的随机数的整形数组
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(a));
        //选择排序
        //1.每轮确定一个基准值，向后遍历，找到最小值，交换位置
        //2.每一轮确定一个最小值
        for (int i = 0; i < a.length - 1; i++) {
            int min = a[i];  //基准值
            int minPosition = i;  //基准值位置
            for (int j = i + 1; j < a.length; j++) {
                if (min > a[j]) {  //在每一轮中找最小值
                    min = a[j];   //记录最小值的值和位置
                    minPosition = j;
                }
            }
            a[minPosition] = a[i];  //把最小值位置的值和基准值互换
            a[i] = min;
        }
        System.out.println(Arrays.toString(a));
    }
}

3.插入排序法

3.1 算法描述

1）从第二个值开始，向后扩展轮数；

2）确定循环每轮要插入的值；

3）不符合插入条的都后移一次，符合便插入；

4）遍历都没有符合条件，这个值便插入第一个；

3.2 程序编写

import java.util.Arrays;

public class Insertionsort {
    public static void main(String[] args) {
        //生成长度为10的随机数的整形数组
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(a));
        //插入排序
        //1.从第二个值开始，向后扩展轮数
        //2.从后向前遍历，执行插入元素的过程
        for (int i = 1; i < a.length; i++) {
            int tmp = a[i]; //每轮要插入的值
            boolean flag = true; //看看是否插入
            for (int j = i - 1; j >= 0; j--) {
                if (tmp < a[j]) { //不满足条件，这个元素往后移一个
                    a[j + 1] = a[j];
                } else {  //a[j]>=tmp，tmp可以插入了，flag可以改变值
                    flag = false;
                    a[j + 1] = tmp;
                    break; //插入后要break，不然a[j]前面排好的值都会被赋值
                }
            }
            if (flag) {  //没有找到插入的地方，tmp比a[j]都小，那么插在首位
                a[0] = tmp;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}