排序算法

排序算法是程序设计中基础而又重要的部分，各种场景都离不开对数组或列表的排序操作。掌握不同的排序算法及其实现细节不仅可以帮助提高代码性能，也为理解底层原理提供工具。

目录

1. 排序算法简介
2. 排序算法分类
3. 比较排序
   • 冒泡排序 (Bubble Sort)
   • 选择排序 (Selection Sort)
   • 插入排序 (Insertion Sort)
   • 归并排序 (Merge Sort)
   • 快速排序 (Quick Sort)
   • 堆排序 (Heap Sort)
4. 非比较排序
   • 计数排序 (Counting Sort)
   • 基数排序 (Radix Sort)
5. 复杂度分析与对比
6. 排序算法的选择
7. 总结

---

1. 排序算法简介

排序算法的目标是将无序数据序列按照特定规则（如升序或降序）重新排列。它们是算法与数据结构的基础之一，也是许多复杂算法的子部分。

---

2. 排序算法分类

排序算法可以分成两大类：

1. 比较排序：基于比较元素之间大小关系进行排序，时间复杂度下限为 (O(n \log n))（例：快速排序、归并排序等）。
2. 非比较排序：不通过比较进行排序，通常依赖数据的某些属性，时间复杂度可低至 (O(n))（例：计数排序、基数排序等）。

---

3. 比较排序

3.1 冒泡排序 (Bubble Sort)

原理

• 每次比较相邻两个元素并进行交换，将大元素逐个“冒泡”到序列末端。
• 特点是简单易实现，但效率相对较低。

特点分析

• 时间复杂度：最好 (O(n))（已排序情况），最坏 (O(n^2))
• 空间复杂度：(O(1))，原地排序
• 稳定性：稳定

Java 实现

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; 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 static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

---

3.2 选择排序 (Selection Sort)

原理

• 每次从待排序部分中找到最小的元素，将其放到已排序部分的末尾。

特点分析

• 时间复杂度：(O(n^2))（无论数据是否有序都需两层循环遍历）
• 空间复杂度：(O(1))，原地排序
• 稳定性：不稳定（因为选择过程中会破坏相邻位置关系）

Java 实现

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // 交换安排位置
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 4, 3};
        selectionSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

---

3.3 插入排序 (Insertion Sort)

原理

• 将待排序元素逐个插入到已排序部分的正确位置。

特点分析

• 时间复杂度：最好 (O(n))，最坏 (O(n^2))
• 空间复杂度：(O(1))，原地排序
• 稳定性：稳定

Java 实现

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将比 key 大的数字右移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

---

3.4 快速排序 (Quick Sort)

原理

• 选择一个基准值 (Pivot)，将数组划分为小于基准和大于基准的两部分，递归处理。
• 是常用排序算法之一，性能优秀。

特点分析

• 时间复杂度：平均 (O(n \log n))，最坏 (O(n^2))
• 空间复杂度：(O(\log n))（递归栈空间）
• 稳定性：不稳定

Java 实现

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

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选取最后一个元素为基准
        int i = low - 1;        // i 指向比 pivot 小的最后位置
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 把 pivot 放到中间位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

---

4. 非比较排序

以下是常见的非比较排序算法：

• 计数排序：适用于范围相对较小的整数数组。
• 基数排序：通过逐位比较实现排序，适用于一定范围内的数值数据。

---

5. 复杂度分析与排序对比

排序算法	时间复杂度（最好）	时间复杂度（最坏）	空间复杂度	稳定性
冒泡排序 (Bubble Sort)	(O(n))	(O(n^2))	(O(1))	稳定
插入排序 (Insertion Sort)	(O(n))	(O(n^2))	(O(1))	稳定
快速排序 (Quick Sort)	(O(n \log n))	(O(n^2))	(O(\log n))	不稳定
选择排序 (Selection Sort)	(O(n^2))	(O(n^2))	(O(1))	不稳定

---

6. 排序算法的选择

• 小规模数据：
  • 插入排序 或 选择排序。
• 大规模无序数据：
  • 快速排序 或 归并排序。
• 有序程度较高的数组：
  • 冒泡排序 或 插入排序。
• 对稳定性要求：
  • 归并排序 或 插入排序。

---

7. 总结

排序算法是程序设计的核心部分，基于场景的需求选择合适的排序算法，能显著提升代码执行效率。通过深入理解各种排序的时间复杂度、空间复杂度以及实现，能够更加高效地解决实际问题。