Java实现常见排序算法的优化攻略

本文将介绍如何使用Java实现几种常见的排序算法并对其进行优化，提高算法效率。

常见排序算法的分类

常见的排序算法分为两类：

比较类排序： 直接通过比较元素大小来确定元素间的相对次序，如冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序等。这类算法时间复杂度下限为Ω(nlogn)，也是大多数排序算法的时间复杂度上限。
非比较类排序： 不直接比较元素的大小，而根据具体问题的特定要求，通过非比较的方法确定元素间的相对次序，如计数排序、桶排序、基数排序等。这类算法时间复杂度可以达到O(n)。

常见排序算法的实现与优化

冒泡排序

冒泡排序是一种简单的交换排序算法，时间复杂度为O(n^2)。其基本思想是将相邻的元素两两比较，如果前面的元素大于后面的元素则交换这两个元素的位置，直到没有任何一对数字需要比较。

普通实现：

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

优化1： 增加一个标志位，如果在一次排序中没有进行任何交换，则说明序列已具有有序性，排序提前结束。

public static void bubbleSort1(int[] arr) {
    boolean flag;
    for (int i = 0; i < arr.length - 1; i++) {
        flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

优化2： 记录最后一次交换的位置，该位置以下的数据已经有序，无需再进行比较。

public static void bubbleSort2(int[] arr) {
    boolean flag;
    int lastExchangeIndex = 0;
    int sortBorder = arr.length - 1;
    for (int i = 0; i < arr.length - 1; i++) {
        flag = false;
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (!flag) {
            break;
        }
    }
}

快速排序

快速排序是一种基于分治思想的排序算法，时间复杂度为O(nlogn)。其基本思想是选取一个数（一般为第一个数）作为基准，将小于基准的数放到其左边，大于基准的数放到其右边，然后再依次对左右两部分进行递归排序。

普通实现：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left;
    int j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    return i;
}

优化1： 选取基准点的方法可以优化，在序列的开头、结尾和中间位置各选取一个元素，取这三个数的中位数作为基准。

private static int median3(int[] arr, int left, int right) {
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) {
        int temp = arr[left];
        arr[left] = arr[mid];
        arr[mid] = temp;
    }
    if (arr[left] > arr[right]) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    if (arr[mid] > arr[right]) {
        int temp = arr[mid];
        arr[mid] = arr[right];
        arr[right] = temp;
    }
    int pivot = arr[mid];
    arr[mid] = arr[left];
    arr[left] = pivot;
    return pivot;
}

public static void quickSort1(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition1(arr, left, right);
        quickSort1(arr, left, partitionIndex - 1);
        quickSort1(arr, partitionIndex + 1, right);
    }
}

private static int partition1(int[] arr, int left, int right) {
    int pivot = median3(arr, left, right);
    int i = left;
    int j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    return i;
}

优化2： 对于小规模的子序列，使用插入排序。

public static void quickSort2(int[] arr, int left, int right) {
    if (left < right) {
        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, left, right);
        } else {
            int partitionIndex = partition1(arr, left, right);
            quickSort2(arr, left, partitionIndex - 1);
            quickSort2(arr, partitionIndex + 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 = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

示例说明

示例1——冒泡排序

public static void main(String[] args) {
    int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    System.out.println("排序前：" + Arrays.toString(arr));
    bubbleSort2(arr);
    System.out.println("排序后：" + Arrays.toString(arr));
}

输出结果：

排序前：[9, 8, 7, 6, 5, 4, 3, 2, 1]
排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]

示例2——快速排序

public static void main(String[] args) {
    int[] arr = {45, 99, 12, 19, 33, 78, 53, 46, 28, 89, 67, 56};
    System.out.println("排序前：" + Arrays.toString(arr));
    quickSort2(arr, 0, arr.length - 1);
    System.out.println("排序后：" + Arrays.toString(arr));
}

输出结果：

排序前：[45, 99, 12, 19, 33, 78, 53, 46, 28, 89, 67, 56]
排序后：[12, 19, 28, 33, 45, 46, 53, 56, 67, 78, 89, 99]

总结

通过对常见排序算法的优化，可以大大提高算法效率。在实际开发中要根据具体的需求和数据规模来选择合适的排序算法并进行优化。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java实现常见排序算法的优化 - Python技术站

Java实现常见排序算法的优化