深入解析经典排序算法：原理、实现与优化

深入浅出：Java 中的经典排序算法详解与实现

6. 堆排序（Heap Sort）

原理

堆排序算法是一种高效的排序方法，其核心在于利用了堆的数据结构特性。堆是一种特殊的完全二叉树，可以分为最大堆和最小堆两种形式。在最大堆中，每个父节点的值总是大于或等于其两个子节点的值；而在最小堆中，每个父节点的值总是小于或等于其两个子节点的值。这种性质使得堆的根节点总是整个堆中的最大值或最小值。

堆排序算法的过程主要分为两个阶段：

1. 构建初始堆：首先将待排序的无序序列构建成一个最大堆（假设升序排列），此时堆顶元素即为序列中的最大值。
2. 排序处理：将堆顶元素与序列最后一个元素交换位置，然后将剩余的序列重新调整为最大堆，重复这一过程，直到所有元素都被排序。

Java 实现

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 开始排序
        for (int i = n - 1; i > 0; i--) {
            // 移动当前根节点至数组末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余未排序的元素重新构建最大堆
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 比较左子节点是否大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 比较右子节点是否大于当前最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 若最大值不是根节点，则交换它们的位置，并继续向下调整
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }
}

7. 希尔排序（Shell Sort）

原理

希尔排序是对直接插入排序的优化，它通过将原始列表分割成多个子列表，每个子列表分别进行插入排序，这样做的目的是为了减少数据项之间的移动次数，从而提高排序效率。希尔排序的关键在于选择合适的间隔序列，间隔序列的选择直接影响到排序的性能。

Java 实现

public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        int gap = n / 2;

        // 控制间隔序列
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 插入排序的核心部分，使用间隔进行比较和交换
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            // 减小间隔
            gap /= 2;
        }
    }
}

8. 计数排序（Counting Sort）

原理

计数排序是一种线性时间复杂度的非比较型排序算法，特别适合用于数据范围已知且较小的情况。它的工作原理是创建一个额外的计数数组来记录输入数组中每个元素出现的次数，然后根据计数数组重构出排序后的数组。

Java 实现

public class CountingSort {
    public static void sort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        // 寻找最大值和最小值
        for (int num : arr) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 创建计数数组并初始化
        int range = max - min + 1;
        int[] count = new int[range];

        // 计算每个元素出现的次数
        for (int num : arr) {
            count[num - min]++;
        }

        // 重构排序后的数组
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min;
                count[i]--;
            }
        }
    }
}

9. 基数排序（Radix Sort）

原理

基数排序是一种非比较型的排序算法，主要用于整数排序。它通过对整数的每一位数字进行独立的排序来实现整体排序的目的。基数排序有两种主要的方式：最高有效位（MSD）和最低有效位（LSD）。LSD 方法通常更常用，因为它可以通过简单的计数排序或桶排序来实现。

基数排序的基本步骤包括：

1. 确定排序的最大位数：找到数组中的最大值，以确定需要排序的位数。
2. 按位排序：从最低位开始，对每一位上的数字进行排序，通常使用计数排序作为子过程。
3. 合并结果：经过多次按位排序后，数组已经是有序状态。

Java 实现

public class RadixSort {
    public static void sort(int[] arr) {
        int max = getMax(arr); // 获取数组中最大的数

        // 对每个位数进行排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }

    private static void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组

        // 计算每个位数上的数字出现次数
        for (int i = 0; i < n; i++) {
            int index = (arr[i] / exp) % 10;
            count[index]++;
        }

        // 修改 count 数组，使其包含实际位置信息
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            int index = (arr[i] / exp) % 10;
            output[count[index] - 1] = arr[i];
            count[index]--;
        }

        // 将输出数组复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
}

这些排序算法各有特点，适用于不同场景下的排序需求。在选择排序算法时，应考虑数据的具体特征、大小以及性能要求等因素。