1. 快速排序（Quick Sort）

2. 归并排序（Merge Sort）

3. 堆排序（Heap Sort）

4. 冒泡排序（Bubble Sort）

5. 插入排序（Insertion Sort）

1. 快速排序（Quick Sort）

核心思想：

分治法 + 递归。通过选定基准值（pivot）将数组分为两部分，左边小于基准，右边大于基准，递归处理子数组。

步骤：

1. 分区（Partition）：

   • 选择基准（通常为首元素或随机元素）。

   • 双指针 i（左→右找 > pivot）、j（右→左找 < pivot），交换不符合条件的元素。

   • 最终将基准放到正确位置。

2. 递归：对左右子数组重复上述过程。

示例数组：[10, 80, 30, 90, 40, 50, 70]
基准选择：第一个元素（10）
分区过程：

1. 初始：[10, 80, 30, 90, 40, 50, 70]

   • i 从左找 >10 的数（停在 80），j 从右找 <10 的数（未找到，与 i 相遇）。

   • 无交换，10 已在正确位置。

2. 递归右子数组 [80, 30, 90, 40, 50, 70]（基准 80）：

   • j 找到 70 < 80，i 找到 90 > 80 → 交换 90 和 70 → [80, 30, 70, 40, 50, 90]

   • j 继续左移找到 50 < 80，i 右移与 j 相遇 → 交换 80 和 50 → [50, 30, 70, 40, 80, 90]

3. 递归左子数组 [50, 30, 70, 40]（基准 50）：

   • 最终分区结果：[30, 40, 50, 70]

4. 排序完成：[10, 30, 40, 50, 70, 80, 90]

代码实现（Java）：

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        swap(arr, i, j);
    }
    swap(arr, left, i);
    return i;
}

特点：

• 优化：随机选基准或三数取中法避免最坏情况。

• 应用：Java Arrays.sort() 对基本类型使用快速排序。

---

2. 归并排序（Merge Sort）

核心思想：

分治法 + 合并有序数组。将数组递归拆分为最小单元，再逐层合并。

步骤：

1. 拆分：将数组均分为两半，递归拆分直到子数组长度为1。

2. 合并：比较两个有序子数组的元素，依次放入新数组。

示例数组：[38, 27, 43, 3, 9, 82, 10]
分治过程：

1. 拆分：

   • 第一次拆分：[38,27,43,3] 和 [9,82,10]

   • 第二次拆分：[38,27], [43,3], [9,82], [10]

   • 拆至最小单元：[38], [27], [43], [3], [9], [82], [10]

2. 合并：

   • 合并 [27, 38] 和 [3, 43] → [3, 27, 38, 43]

   • 合并 [9, 82] 和 [10] → [9, 10, 82]

   • 最终合并：[3, 9, 10, 27, 38, 43, 82]

代码实现（Java）：

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

特点：

• 稳定性：合并时保留相等元素的原始顺序。

• 应用：外部排序（大数据文件）、链表排序。

---

3. 堆排序（Heap Sort）

核心思想：

利用最大堆/最小堆的性质，通过反复调整堆结构实现排序。

步骤：

1. 建堆：将数组调整为最大堆（父节点 ≥ 子节点）。

2. 排序：交换堆顶（最大值）与末尾元素，缩小堆范围并重新调整。

示例数组：[4, 10, 3, 5, 1]
建堆（最大堆）过程：

1. 初始完全二叉树：

       4
      / \
     10  3
    / \
   5   1

2. 调整非叶子节点（从 10 开始）：

   • 10 > 5 和 1，无需调整。

   • 4 < 10 → 交换 4 和 10：

         10
        / \
       4   3
      / \
     5   1

   3、`4` < `5` → 交换 `4` 和 `5`：
   
           10
          /  \
         5    3
        / \
       4   1
   

3. 排序：

   • 交换堆顶 10 和末尾 1 → [1, 5, 3, 4, 10]（10 已排序）

   • 重新调整堆 [1,5,3,4] → 最大堆 [5,4,3,1]

   • 重复交换和调整，最终得到 [1, 3, 4, 5, 10]。

代码实现（Java）：

void heapSort(int[] arr) {
    // 建堆（从最后一个非叶子节点开始）
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, arr.length, i);
    }
    // 排序
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i, left = 2 * i + 1, 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) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

特点：

• 原地排序：空间复杂度 O(1)。

• 应用：实时系统（如嵌入式设备内存受限时）。

---

4. 冒泡排序（Bubble Sort）

核心思想：

重复比较相邻元素，将较大值逐步“冒泡”到数组末端。

步骤：

1. 每轮遍历比较相邻元素，若逆序则交换。

2. 每轮结束后，最大值已置于末尾，缩小遍历范围。

示例数组：[5, 1, 4, 2, 8]
每轮遍历：

1. 第一轮：

   • 比较 5 和 1 → 交换 → [1, 5, 4, 2, 8]

   • 比较 5 和 4 → 交换 → [1, 4, 5, 2, 8]

   • 比较 5 和 2 → 交换 → [1, 4, 2, 5, 8]

   • 5 和 8 不交换 → 结束，8 已就位。

2. 第二轮：

   • 比较 1 和 4 → 不交换

   • 比较 4 和 2 → 交换 → [1, 2, 4, 5, 8]

   • 4 和 5 不交换 → 5 已就位。

3. 第三轮：无交换，提前终止。
   最终结果：[1, 2, 4, 5, 8]

代码实现（Java）：

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前终止（已有序）
    }
}

特点：

• 优化：通过 swapped 标志位提前终止。

• 应用：教学示例或小规模数据（实际工程中较少使用）。

---

5. 插入排序（Insertion Sort）

核心思想：

将数组分为已排序和未排序两部分，逐个将未排序元素插入到正确位置。

示例数组：[12, 11, 13, 5, 6]
逐步插入：

1. 初始：[12]（已排序），[11, 13, 5, 6]（未排序）

   • 插入 11：11 < 12 → [11, 12]

2. 插入 13：13 > 12 → [11, 12, 13]

3. 插入 5：

   • 5 < 13 → 右移 13 → [11, 12, 13, 13]

   • 5 < 12 → 右移 12 → [11, 12, 12, 13]

   • 5 < 11 → 右移 11 → [11, 11, 12, 13]

   • 放入 5 → [5, 11, 12, 13]

4. 插入 6：

   • 类似过程 → 最终 [5, 6, 11, 12, 13]

代码实现（Java）：

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

特点：

• 稳定性：插入时不影响相等元素的顺序。

• 应用：小规模数据或近乎有序的数组（如 TimSort 的子过程）。

---

综合对比表

算法	关键操作	稳定性	最佳场景	最差场景
快速排序	分区 + 递归	不稳定	大规模无序数据	已有序或逆序数组
归并排序	分治 + 合并	稳定	外部排序、链表排序	所有情况稳定 O(n log n)
堆排序	建堆 + 交换堆顶	不稳定	空间受限的实时系统	数据量极大时缓存不友好
冒泡排序	相邻比较交换	稳定	教学或小规模有序数据	大规模无序数据
插入排序	逐个插入已排序区	稳定	小规模或近乎有序数据	大规模逆序数据

---

如何选择排序算法？

1. 通用排序：快速排序（默认选择，但需避免最坏情况）。

2. 需要稳定性：归并排序或插入排序。

3. 空间受限：堆排序。

4. 小规模数据：插入排序或冒泡排序。