排序算法全景：从基础到高级的Java实现

排序算法是计算机科学中的一个基础概念，它在数据处理和信息检索中扮演着至关重要的角色。本文将通过几个简单的Java程序，带你了解几种常见的排序算法：插入排序、希尔排序、归并排序、快速排序和选择排序，以及一个用于生成和打印测试数据的工具类。

插入排序：理解排序的核心思想

什么是插入排序？

插入排序（Insertion Sort）算法是一种直观且易于理解的排序方法。插入排序的工作原理类似于我们整理扑克牌的方式。想象一下，你手中有一堆未排序的扑克牌，你将它们一张张插入到已经排序好的牌堆中。插入排序算法正是基于这样的思想：它将数组分为已排序和未排序两部分，然后逐个将未排序部分的元素插入到已排序部分的适当位置。

插入排序的Java实现

让我们通过一个Java程序来具体看看插入排序是如何工作的。这个程序定义了一个名为 _01_InsertionSort 的类，其中包含了排序方法和一些辅助函数。

public class _01_InsertionSort {
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素arr[i]合适的插入位置
            for (int j = i; j > 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

在这个类中，sort 方法接受一个可比较的对象数组 arr 作为参数。方法的核心是一个双重循环：外层循环遍历数组的每个元素，内层循环则负责将当前元素与已排序部分的元素进行比较，并在必要时进行交换。

swap 方法是一个辅助函数，用于交换数组中的两个元素。这是在内层循环中，当我们发现需要将一个元素插入到它之前的位置时调用的。

程序的执行

程序的 main 方法首先生成了一个包含20000个随机整数的数组，然后调用 sort 方法对数组进行排序，最后打印出排序后的数组。

public static void main(String[] args) {
    int N = 20000;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
    _01_InsertionSort.sort(arr);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]);
        System.out.print(' ');
    }
}

插入排序的核心思想

插入排序的核心思想是分而治之。它将排序问题分解为更小的部分，然后逐个解决。这种方法在数据量较小或者数据基本有序的情况下非常有效，因为它可以减少不必要的比较和交换操作。

结语

通过这个简单的Java程序，我们不仅学习了插入排序算法的实现，还理解了排序算法的一般思想。虽然插入排序在处理大数据集时可能不是最高效的选择，但它的简单性和直观性使其成为理解排序概念的一个良好起点。随着你对算法的深入学习，你将能够掌握更多高级的排序技术，以应对更复杂的数据处理挑战。

希尔排序：一种高效的改进版插入排序

希尔排序（Shell Sort）是一种对传统插入排序的改进，它通过引入间隔（gap）的概念来提高排序的效率。

希尔排序简介

希尔排序是由Donald Shell在1959年提出的一种排序算法。它基于插入排序，通过将原始数据集分割成若干个子序列来排序，这些子序列的元素间隔逐渐减小，最后合并为一个有序的序列。

Java实现希尔排序

让我们通过一个简单的Java程序来实现希尔排序。

public class _02_ShellSort {
    public static void sort(Comparable[] arr) {
        // 初始化间隔
        int gap = arr.length / 2;
        // 当间隔大于0时，执行排序
        while (gap > 0) {
            // 遍历数组，间隔为gap
            for (int i = gap; i < arr.length; i++) {
                // 临时存储当前元素
                Comparable tmp = arr[i];
                // 对于每个间隔内的元素，进行插入排序
                for (int j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    // 将较大的元素向后移动
                    arr[j] = arr[j - gap];
                }
                // 将当前元素放到正确的位置
                arr[j] = tmp;
            }
            // 缩小间隔，进行下一轮排序
            gap /= 2;
        }
    }
}

在这个实现中，我们首先计算一个初始间隔 gap，然后通过一个循环来逐渐减小这个间隔。在每次循环中，我们对间隔为 gap 的元素进行插入排序。随着间隔的减小，排序的粒度逐渐变细，最终整个数组变得有序。

测试希尔排序

为了测试我们的希尔排序算法，我们在 main 方法中生成了一个包含2000个随机整数的数组，并对其进行排序。

public static void main(String[] args) {
    int N = 2000;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
    _02_ShellSort.sort(arr);
    // 打印排序后的数组
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]);
        System.out.print(' ');
    }
}

希尔排序的核心思想

希尔排序的核心在于分而治之的策略。它不是一次性对整个数组进行排序，而是先对数组的子序列进行排序，然后逐步缩小子序列的范围，直到整个数组有序。这种方法在处理部分有序的数据时特别有效，因为它可以减少不必要的比较和交换操作。

结语

通过这个Java程序，我们不仅学习了希尔排序的实现，还理解了其背后的算法思想。希尔排序是一种简单且高效的排序方法，它在某些情况下比传统的插入排序要快得多。

归并排序：优雅的分而治之艺术

归并排序（Merge Sort）是一种优雅且高效的排序方法。归并排序通过分而治之的策略，将数据集一分为二，然后递归地对这两部分进行排序，最后将它们合并成一个有序的整体。

归并排序的基本概念

归并排序的核心在于“分而治之”。这个策略涉及将一个大问题分解成小问题，解决这些小问题，然后将它们的解决方案合并。在排序的上下文中，这意味着将一个未排序的数组分成两半，分别对这两半进行排序，然后将它们合并成一个有序数组。

Java实现归并排序

让我们通过一个Java程序来实现归并排序。

public class _03_MergeSort {
    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }
    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        sort(arr, 0, n - 1);
    }
}

在这个类中，merge 方法负责合并两个已经排序的子数组。sort 方法是递归的核心，它将数组分成两半，然后递归地调用自身来排序这两半。最后，sort 方法提供了一个公共接口来开始排序过程。

测试归并排序

为了测试归并排序的性能，我们在 main 方法中生成了一个包含1000个随机整数的数组，并对其进行排序。

public static void main(String[] args) {
    int N = 1000;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
    _03_MergeSort.sort(arr);
    SortTestHelper.printArray(arr);
}

归并排序的核心思想

归并排序的核心在于递归和合并。递归地将数组分成更小的部分，直到每个部分只有一个元素（或没有元素），这时数组自然是有序的。然后，通过合并相邻的有序子数组，逐步构建更大的有序数组，最终得到完全有序的原始数组。

结语

归并排序是一种非常优雅的排序算法，它不仅在理论上具有优雅的数学美感，而且在实际应用中也非常高效。它的时间复杂度在最好、最坏和平均情况下都是O(n log n)，这使得它在处理大型数据集时特别有用。尽管归并排序需要额外的存储空间来创建辅助数组，但它的稳定性和效率使其成为许多排序场景下的首选算法。

快速排序：分而治之的高效排序算法

快速排序（Quick Sort）是一种分而治之策略的高效排序方法。快速排序以其平均时间复杂度为O(n log n)而闻名，它在大多数情况下都能提供出色的性能。

快速排序的基本概念

快速排序的核心在于“分而治之”。这个策略涉及将一个大问题分解成小问题，解决这些小问题，然后将它们的解决方案合并。在排序的上下文中，这意味着将一个未排序的数组分成两半，然后递归地对这两半进行排序，最后将它们合并成一个有序的整体。

Java实现快速排序

让我们通过一个Java程序来实现快速排序。

public class _04_QuickSort {
    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...j] < v ; arr[j+1...i) > v
        int j = l;
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                j ++;
                swap(arr, j, i);
            }
        swap(arr, l, j);
        return j;
    }
    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }
    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr, 0, n-1);
    }
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    // 测试 QuickSort
    public static void main(String[] args) {
        // Quick Sort也是一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);
    }
}

在这个类中，partition 方法负责将数组分成两部分，sort 方法是递归排序的核心，它将数组分成两半，然后递归地对这两半进行排序。swap 方法是一个辅助函数，用于交换数组中的两个元素。

快速排序的核心思想

快速排序的核心在于选择一个基准值（pivot），然后将数组分成两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于基准值的元素。这个过程称为分区（partitioning）。分区操作完成后，基准值就处于其最终排序位置。然后，我们递归地对基准值左边和右边的子数组进行同样的操作，直到整个数组变得有序。

快速排序的性能

快速排序的平均时间复杂度为O(n log n)，这使得它在处理大型数据集时非常高效。尽管在最坏情况下，快速排序的时间复杂度会下降到O(n^2)，但通过随机选择基准值，可以大大降低这种最坏情况发生的概率。

结语

通过学习快速排序，我们不仅掌握了一种高效的排序技术，还理解了分而治之这一强大的问题解决策略。这种策略在计算机科学中有着广泛的应用，不仅仅是在排序算法中。快速排序的优雅和效率使其成为了许多排序场景下的首选算法。

选择排序：简单而直观的排序算法入门

选择排序（Selection Sort）算法是一种易于理解和实现的排序方法。选择排序的核心思想是在每一轮迭代中找到最小（或最大）的元素，并将其移动到正确的位置。

选择排序的工作原理

选择排序算法的工作原理可以概括为以下几个步骤：

1. 假设第一个元素已经是排序好的。
2. 在剩余的未排序元素中找到最小（或最大）的元素。
3. 将找到的最小（或最大）元素与当前未排序的第一个元素交换位置。
4. 重复步骤2和3，直到所有元素都被排序。

Java实现选择排序

下面是一个选择排序的Java实现示例：

public class _07_SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 初始化最小值索引为当前位置
            int minIndex = i;
            // 寻找[i, n)区间里的最小值的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换当前位置和找到的最小值位置的元素
            swap(arr, i, minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        _07_SelectionSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

在这个实现中，sort 方法负责执行排序过程。它首先遍历数组，然后在每次迭代中找到最小值的索引，并将其与当前位置的元素交换。swap 方法是一个辅助函数，用于交换数组中的两个元素。

选择排序的特点

选择排序的主要特点是简单。它不需要额外的存储空间（除了临时变量），并且实现起来非常直观。然而，选择排序的效率并不是最高的，它的平均和最坏情况时间复杂度都是O(n^2)，这使得它在处理大型数据集时效率较低。

结语

选择排序虽然在效率上可能不如其他更高级的排序算法，但它的简单性和易于理解的特点使其成为初学者学习排序算法的良好起点。

生成测试数据和输出测试数据的类

//SortTestHelper
public class SortTestHelper {
    // SortTestHelper不允许产生任何实例
    private SortTestHelper(){}
    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
        assert rangeL <= rangeR;
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++)
            arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL));
        return arr;
    }
    // 打印arr数组的所有内容
    public static void printArray(Object arr[]) {
        for (int i = 0; i < arr.length; i++){
            System.out.print( arr[i] );
            System.out.print( ' ' );
        }
        System.out.println();
        return;
    }
}

感谢你的访问，期待与你在技术的道路上相遇！👋🌟🚀

打赏