Java中基本排序算法的实现和优化

Java中基本排序算法包括冒泡排序、选择排序、插入排序、快速排序等。这些算法虽然基本，但是在实际开发中经常用到。本文将对这些排序算法的实现和优化进行简单介绍。

1. 冒泡排序

冒泡排序是最简单的排序算法之一，基本思想是通过相邻元素比较和交换来把小的数交换到数组的前面。具体实现如下：

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡排序的时间复杂度为O(n^2)，比较低效，需要优化。优化的方法有两种：

（1）加入flag提前结束

如果在一轮循环中没有发生交换，说明已经有序，可以提前结束。具体实现如下：

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    boolean flag = true;
    for (int i = 0; i < n - 1 && flag; i++) {
        flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
    }
}

（2）记录最后一次交换的位置

在一轮循环中，最后一次发生交换的位置之后的数据已经有序，下一轮排序只需要比较到这个位置即可。具体实现如下：

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    int k = n - 1;
    for (int i = 0; i < n - 1; i++) {
        int pos = 0;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                pos = j;
            }
        }
        k = pos;
    }
}

2. 选择排序

选择排序的基本思想是在未排序的数据中选出最小的元素放到已排序的数据最后面，具体实现如下：

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

选择排序的时间复杂度也为O(n^2)，可以用与冒泡排序一样的优化方法来提高效率。

（1）使用二元选择排序

二元选择排序是选择排序的一种变体，在每轮循环中选出最大和最小的元素并同时放到已排序的数据的两端，减少比较次数。具体实现如下：

public static void binarySelectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = 0; i < n / 2; i++) {
        int min = i;
        int max = i;
        for (int j = i; j < n - i; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
            if (arr[j] > arr[max]) {
                max = j;
            }
        }
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        if (max != n - i - 1) {
            int temp = arr[n - i - 1];
            arr[n - i - 1] = arr[max];
            arr[max] = temp;
        }
    }
}

（2）堆排序

堆排序是一种树形选择排序，利用了堆的性质。它的时间复杂度为O(nlogn)，略微比快速排序慢一些。具体实现如下：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, i, n);
    }
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, 0, i);
    }
}

private static void heapify(int[] arr, int i, int n) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, largest, n);
    }
}

3. 插入排序

插入排序是一种简单直观的排序算法，它的基本思想是将已排序的数据逐个与待排序的数据进行比较插入。具体实现如下：

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            int temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
    }
}

插入排序的时间复杂度也为O(n^2)，可以优化。优化的方法有两种：

（1）使用二分查找法

将插入操作优化为二分查找的方式插入已排序数据中，可以减少比较次数。具体实现如下：

public static void binaryInsertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int left = 0;
        int right = i - 1;
        int temp = arr[i];
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > temp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }
}

（2）使用希尔排序

希尔排序是插入排序的又一种变体，利用了插入排序的