Java 数据结构与算法系列精讲之排序算法

Java 数据结构与算法系列精讲之排序算法攻略

1. 序言

排序算法是计算机程序设计中常见的一类算法，主要用于将一组数据按照一定的顺序重新排列。在实际工作和面试中，排序算法是计算机程序员必须掌握的基本算法之一。本文将重点讲解 Java 数据结构与算法系列中的排序算法，其中包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。

2. 冒泡排序

冒泡排序是一种较为简单的排序方式，其基本思想是从头到尾比较相邻两元素的大小，并交换位置。在一次完整的冒泡过程中，将会把数字序列中最大的数“冒泡”到最后面。最好情况下时间复杂度为 O(n)，最坏情况和平均情况时间复杂度均为 O(n²)。

示例：

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

3. 选择排序

选择排序和冒泡排序一样，都是简单的排序算法。它的基本思想是从未排序的序列中选择一个最小的元素存放到已排序序列的末尾，然后再从未排序序列中选择最小元素。最好情况、最坏情况和平均情况下时间复杂度均为 O(n²)。

示例：

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

4. 插入排序

插入排序方面，插入排序的基本思想是将一个记录插入到有序的序列中，从而得到一个新的序列。在插入排序过程中，记录从前往后依次插入，未排序的序列每次从前面取出一个元素，并插入到有序序列的相应位置中。最好情况时间复杂度为 O(n)，最坏情况和平均情况时间复杂度均为 O(n²)。

示例：

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

5. 希尔排序

希尔排序是插入排序的一种优化版本。它通过缩小增量（增量序列的选择也有影响）来改变待排序序列中各元素的相对位置，从而达到排序的目的。希尔排序是非稳定排序，它的时间复杂度依据所选取的增量序列不同而不同，通常情况下它的时间复杂度都是 O(n log n) 级别的。

示例：

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

6. 归并排序

归并排序采用先拆分再合并的递归方法，将序列分成若干个长度为1的子序列，然后再将它们两两合并，直接合并完成为止。归并排序是稳定排序，在排序过程中需要开辟一个与原数组大小相等的数组来辅助排序。时间复杂度是 O(n log n)。

示例：

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int[] temp = new int[arr.length];
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= m) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    for (int x = l; x <= r; x++) {
        arr[x] = temp[x];
    }
}

7. 快速排序

快速排序是一种快速的排序方法，采用分而治之的思想，利用递归实现。它的基本思想就是选择一个基准元素，然后将序列分成两部分，分别对这两部分再进行快速排序，直到整个序列有序为止。快速排序是不稳定的排序方法，其时间复杂度平均情况下为 O(n log n)。

示例：

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

8. 堆排序

堆排序是一种树形选择排序方法，其基本思想是将待排序的序列构建成一个大根堆或小根堆，依次取出最大或最小元素放到根节点中，再对剩余的元素重新构造堆，直到整个序列有序为止。堆排序是一种不稳定的排序方法，其平均时间复杂度为 O(n log n)，空间复杂度为 O(1)。

示例：

public static void heapSort(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);
    }
}

public static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

9. 总结

通过本文对 Java 数据结构与算法系列中的排序算法的讲解，我们可以了解到不同的排序算法的原理、时间复杂度和空间复杂度等方面的知识。其中包括了冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序等七种基本排序算法，希望这篇文章能为你理解和掌握排序算法提供帮助。