Java基础算法

这里只写了冒泡排序、选择排序、插入排序，后续还会更新。

1、原理

? 冒泡排序：

? 每次比较从第个数据开始，数据两两比较，如果左边数据比右数据大，则交换左右数据。继续比较。一次比较结束出现一个最大值在最后一个位置。

? 选择排序：

? 表现最稳定的排序算法之一，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

? 插入排序：

? 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2、代码测试

@SpringBootTest
class DemoApplicationTests {

    @Test
    void bubbleSort() {
        int arr[] = {5, 6, 9, 10, 25, 96, 32, 78, 54, 12, 36, 85, 789, 951, 75, 42, 62, 15, 16, 17, 18, 91, 82};
        String s = JSONArray.toJSONString(arr);
        System.out.println("排序前：" + s);
        //冒泡排序
        int[] bubbleSort = bubbleSort(arr);
        String s1 = JSONArray.toJSONString(bubbleSort);
        System.out.println("冒泡排序后：" + s1);

        //选择排序
        int[] selectionSort = selectionSort(arr);
        String s2 = JSONArray.toJSONString(selectionSort);
        System.out.println("选择排序后：" + s2);

        //插入排序
        int[] insertionSort = insertionSort(arr);
        String s3 = JSONArray.toJSONString(insertionSort);
        System.out.println("插入排序后：" + s3);

    }

    /**
     * 冒泡排序：每次比较从第个数据开始，数据两两比较，如果左边数据比右数据大，则交换左右数据。继续比较。一次比较结束出现一个最大值在最后一个位置。
     */
    public static int[] bubbleSort(int[] array) {
        if (array.length == 0)
            return array;
        //比较的次数
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                int tep = array[j];
                //数据的交换
                if (tep > array[j + 1]) {
                    array[j] = array[j + 1];
                    array[j + 1] = tep;
                }
            }
        }
        return array;
    }

    /**
     * 选择排序：表现最稳定的排序算法之一，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     */
    public static int[] selectionSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                //找到最小的数
                if (array[j] < array[minIndex])
                    //将最小数的索引保存
                    minIndex = j;
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

    /**
     * 插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

}