优化常见的java排序算法

优化常见的Java排序算法

排序算法是计算机科学中最基础、也是最常用的算法之一。Java提供了多种排序算法的实现，如冒泡排序、插入排序、选择排序、快速排序、归并排序等。但是，这些算法的标准实现在某些情况下可能效率比较低，需要进行优化。

一、冒泡排序

冒泡排序是一种交换排序，基本思想是将相邻的元素两两比较，如果前面的元素大于后面的元素，则交换它们的位置，直到没有相邻元素需要比较为止。冒泡排序时间复杂度为O(n^2)。

优化方案：

1. 设置标志位，在每次交换元素时标记一下。如果没有元素需要交换，跳出循环。这样可以减少不必要的比较，提高算法效率。

public static void bubbleSortImproved(int[] arr) {
    int n = arr.length;
    boolean swapped = true;
    for (int i = 0; i < n - 1 && swapped; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}

1. 每次排序保存最后一次交换位置，下一轮排序时只需要比较到这个位置，后面的元素已经排序好了。这样可以减少比较次数，提高算法效率。

public static void bubbleSortImproved(int[] arr) {
    int n = arr.length;
    int lastSwappedIndex = n - 2;
    for (int i = 0; i < n - 1; i++) {
        int currSwappedIndex = -1;
        for (int j = 0; j <= lastSwappedIndex; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                currSwappedIndex = j;
            }
        }
        lastSwappedIndex = currSwappedIndex;
        if (lastSwappedIndex == -1) {
            break;
        }
    }
}

二、快速排序

快速排序是一种常见的分治排序算法，基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序的目的。快速排序时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)。

优化方案：

1. 优化基准值的选择。可以使用三数取中法来选择基准值，即从左、右、中间三个元素中选择中间值作为基准值。这样可以避免极端情况下基准值选择不当导致的效率问题。

private static void quickSortImproved(int[] arr, int left, int right) {
    if (right - left < 2) {
        return;
    }
    int midIndex = getMidIndex(arr, left, right);
    int pivot = arr[midIndex];
    swap(arr, midIndex, right - 1);

    int i = left;
    int j = right - 1;
    while (true) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
        if (i < j) {
            swap(arr, i, j);
        } else {
            break;
        }
    }
    swap(arr, i, right - 1);
    quickSortImproved(arr, left, i - 1);
    quickSortImproved(arr, i + 1, right);
}
private static int getMidIndex(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    if (arr[left] > arr[mid]) {
        swap(arr, left, mid);
    }
    if (arr[left] > arr[right - 1]) {
        swap(arr, left, right - 1);
    }
    if (arr[mid] > arr[right - 1]) {
        swap(arr, mid, right - 1);
    }
    return mid;
}

1. 优化小数组的排序。当子序列长度小于一定值时，可以使用插入排序来代替快速排序，这样可以减少递归调用带来的额外开销。

private static void quickSortImproved(int[] arr, int left, int right) {
    if (right - left < 2) {
        return;
    }
    if (right - left < 10) {
        insertionSort(arr, left, right);
        return;
    }

    int midIndex = getMidIndex(arr, left, right);
    int pivot = arr[midIndex];
    swap(arr, midIndex, right - 1);

    int i = left;
    int j = right - 1;
    while (true) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
        if (i < j) {
            swap(arr, i, j);
        } else {
            break;
        }
    }
    swap(arr, i, right - 1);
    quickSortImproved(arr, left, i - 1);
    quickSortImproved(arr, i + 1, right);
}
private static void insertionSort(int[] arr, int left, int right) {
    for (int i = left + 1; i < right; i++) {
        int temp = arr[i];
        int j;
        for (j = i; j > left && temp < arr[j - 1]; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

两条示例说明：

int[] arr1 = {5, 3, 4, 2, 1};
BubbleSort.bubbleSortImproved(arr1);
System.out.println(Arrays.toString(arr1));  // [1, 2, 3, 4, 5]

int[] arr2 = {5, 3, 4, 2, 1};
QuickSort.quickSortImproved(arr2);
System.out.println(Arrays.toString(arr2));  // [1, 2, 3, 4, 5]

以上是优化常见的Java排序算法的攻略，通过实现这些优化方案，可以有效提高排序算法的效率，应用到实际项目中可以更好地满足用户需求。