Java 【数据结构】常见排序算法实用详解（下） 冒泡排序/快速排序/归并排序/非基于比较排序【贤者的庇护】

在Java编程中，排序算法是数据结构中非常重要的一部分。排序算法的主要目的是将一组无序的数据按照特定的顺序进行排列。本文将分块讲解几种常见的排序算法，包括冒泡排序、快速排序、归并排序和非基于比较的排序算法。

冒泡排序

冒泡排序是一种简单的排序算法，重复地遍历要排序的数列，比较相邻的元素并交换顺序不正确的元素。每一次遍历将当前未排序部分的最大值“冒泡”到已排序部分的末尾。

代码示例：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            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 class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1); // 排序左侧
            quickSort(arr, pivotIndex + 1, high); // 排序右侧
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素为基准
        int i = low - 1; // 小于基准元素的索引
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 交换基准元素到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1; // 返回基准元素的位置
    }
}

归并排序

归并排序也是一种分治法的排序算法，它首先将数组分成两半，分别进行排序，然后再将两个已排序部分合并成一个完整的排序数组。

代码示例：

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid); // 排序左半部分
            mergeSort(arr, mid + 1, right); // 排序右半部分
            merge(arr, left, mid, right); // 合并
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

非基于比较的排序

非基于比较的排序算法如计数排序、桶排序和基数排序等，通过将数据映射到特定的桶或计数器以实现排序。

计数排序示例：

public class CountingSort {
    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];

        for (int num : arr) count[num]++;

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i; // 放回原数组
                count[i]--;
            }
        }
    }
}

总结

在选择排序算法时，需要考虑算法的时间复杂度、空间复杂度以及稳定性等因素。对于小规模数据，冒泡排序和插入排序等简单算法容易实现且效率较高，而对于大规模数据，快速排序和归并排序等高效算法则更为合适。非基于比较的排序算法适用于特定情况，可以在特定条件下实现高效排序。通过理解这些基本排序算法，程序员能够更好地处理数据排序问题。