冒泡排序、选择排序、插入排序~java版

1、冒泡排序（Bubble Sort）

冒泡排序的基本思想是多次遍历待排序序列，每次遍历时两两比较相邻元素，如果顺序不对则交换，直到整个序列有序为止。

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果一轮遍历中没有发生交换，说明已经有序
            if (!swapped) {
                break;
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = { 5, 2, 9, 3, 6, 1, 8, 7, 4 };
        bubbleSort(arr);
        System.out.println("array: " + Arrays.toString(arr));
    }
}

2、选择排序（Selection Sort）

选择排序的基本思想是每次从未排序部分选择最小（或最大）的元素，然后与未排序部分的第一个元素交换位置。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将找到的最小元素与当前位置交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = { 5, 2, 9, 3, 6, 1, 8, 7, 4 };
        selectionSort(arr);
        System.out.println("array: " + Arrays.toString(arr));
    }
}

3、插入排序（Insertion Sort）

插入排序的基本思想是将未排序部分的元素逐个插入到已排序部分的合适位置，初始时已排序部分只有第一个元素。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将比key大的元素都向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入key
            arr[j + 1] = key;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = { 5, 2, 9, 3, 6, 1, 8, 7, 4 };
        insertionSort(arr);
        System.out.println("array: " + Arrays.toString(arr));
    }
}