探究排序算法的奥秘（下）：快速排序、归并排序、堆排序

        在上一篇博客中，我们详细探讨了冒泡排序、选择排序和插入排序这三种基础的排序算法。它们虽然简单易懂，但在处理大规模数据时效率较低。本文将介绍三种更高效的排序算法：快速排序、归并排序和堆排序。这些算法在实际应用中被广泛使用，因为它们能够在较短时间内对大量数据进行排序。我们将从算法思想、原理、代码实现（C语言、Python、Java）、性能分析以及使用场景等方面进行深入探讨。

目录

一、快速排序

（一）算法思想

（二）算法原理

（三）代码实现

（四）性能分析

（五）使用场景

二、归并排序

（一）算法思想

（二）算法原理

（三）代码实现

（四）性能分析

（五）使用场景

三、堆排序

（一）算法思想

（二）算法原理

（三）代码实现

（四）性能分析

（五）使用场景

四、总结

---

 

一、快速排序

（一）算法思想

        快速排序是一种高效的排序算法，采用分治法的思想。它的基本思想是：通过一个划分操作，将数组分为两部分，其中一部分的所有元素都比另一部分的所有元素小，然后递归地对这两部分进行排序，最终整个数组有序。

（二）算法原理

1. 选择一个元素作为“基准”（pivot）。

2. 重新排列数组，所有比基准小的元素移到基准的左边，所有比基准大的元素移到基准的右边。这个过程称为分区操作（partition）。

3. 递归地对基准左边和右边的子数组进行快速排序。

4. 当子数组的大小为1时，排序完成。

（三）代码实现

C语言实现

#include <stdio.h>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); // 递归排序右子数组}
}int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp; // 交换元素}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp; // 将基准放到中间位置return i + 1;
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

Python实现

def quick_sort(arr):def partition(arr, low, high):pivot = arr[high]  # 选择最后一个元素作为基准i = low - 1for j in range(low, high):if arr[j] <= pivot:i += 1arr[i], arr[j] = arr[j], arr[i]  # 交换元素arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 将基准放到中间位置return i + 1def quick_sort_recursive(arr, low, high):if low < high:pivot_index = partition(arr, low, high)  # 分区操作quick_sort_recursive(arr, low, pivot_index - 1)  # 递归排序左子数组quick_sort_recursive(arr, pivot_index + 1, high)  # 递归排序右子数组quick_sort_recursive(arr, 0, len(arr) - 1)arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr)
print("Sorted array:", arr)

Java实现

public class QuickSort { // 定义一个名为 QuickSort 的类public static void quickSort(int[] arr, int low, int high) { // 快速排序的主函数if (low < high) { // 如果数组的起始索引小于结束索引，说明还有元素需要排序int pivotIndex = partition(arr, low, high); // 调用 partition 方法进行分区操作，返回基准元素的索引quickSort(arr, low, pivotIndex - 1); // 递归地对基准左侧的子数组进行快速排序quickSort(arr, pivotIndex + 1, high); // 递归地对基准右侧的子数组进行快速排序}}public static int partition(int[] arr, int low, int high) { // 分区操作的函数int pivot = arr[high]; // 选择数组的最后一个元素作为基准值int i = low - 1; // 初始化一个指针 i，指向小于基准值的元素的最后一个位置（初始时指向 low 的前一个位置）for (int j = low; j < high; j++) { // 遍历数组，从 low 到 high - 1if (arr[j] <= pivot) { // 如果当前元素小于等于基准值i++; // 将 i 指针向右移动一位int temp = arr[i]; // 交换 arr[i] 和 arr[j]，将小于等于基准值的元素放到左侧arr[i] = arr[j];arr[j] = temp; // 交换元素}}int temp = arr[i + 1]; // 将基准值放到中间位置，即 i + 1 的位置arr[i + 1] = arr[high];arr[high] = temp; // 交换基准值和 arr[i + 1]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("Sorted array:"); // 输出排序后的数组for (int i : arr) { // 遍历数组并打印每个元素System.out.print(i + " ");}}
}

（四）性能分析

• 时间复杂度：快速排序的平均时间复杂度为O(n log n)。在最坏的情况下（数组已经有序或完全逆序），时间复杂度为O(n^2)。通过随机选择基准或使用三数取中法等优化方法，可以有效减少最坏情况的发生。

• 空间复杂度：快速排序的空间复杂度为O(log n)，主要用于递归调用的栈空间。

• 稳定性：快速排序是一种不稳定的排序算法，因为相等元素的相对位置可能会改变。

（五）使用场景

        快速排序适用于大规模数据的排序，尤其是当数据随机分布时。由于其高效的平均性能，快速排序在实际应用中非常广泛，例如在数据库管理系统、文件系统等场景中。

---

 

二、归并排序

（一）算法思想

        归并排序是一种高效的排序算法，采用分治法的思想。它的基本思想是：将数组分为两部分，分别对这两部分进行排序，然后将排序后的两部分合并成一个有序数组。

（二）算法原理

1. 将数组分为两部分，直到每个部分只有一个元素。

2. 对每个部分进行排序。

3. 将排序后的两个部分合并成一个有序数组。

4. 递归地重复上述步骤，直到整个数组有序。

（三）代码实现

C语言实现

#include <stdio.h>
#include <stdlib.h>void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];for (int i = 0; i < n1; i++) {L[i] = arr[left + i];}for (int j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid); // 递归排序左半部分mergeSort(arr, mid + 1, right); // 递归排序右半部分merge(arr, left, mid, right); // 合并两个有序部分}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

Python实现

def merge_sort(arr):def merge(left, mid, right):n1 = mid - left + 1n2 = right - midL = arr[left:mid + 1]R = arr[mid + 1:right + 1]i = j = 0k = leftwhile i < n1 and j < n2:if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < n1:arr[k] = L[i]i += 1k += 1while j < n2:arr[k] = R[j]j += 1k += 1def merge_sort_recursive(left, right):if left < right:mid = (left + right) // 2merge_sort_recursive(left, mid)  # 递归排序左半部分merge_sort_recursive(mid + 1, right)  # 递归排序右半部分merge(left, mid, right)  # 合并两个有序部分merge_sort_recursive(0, len(arr) - 1)arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array:", arr)

Java实现

public class MergeSort { // 定义一个名为 MergeSort 的类public static void mergeSort(int[] arr, int left, int right) { // 归并排序的主函数if (left < right) { // 如果左边界小于右边界，说明还有元素需要排序int mid = left + (right - left) / 2; // 计算中间索引，用于将数组分为两部分mergeSort(arr, left, mid); // 递归地对左半部分进行归并排序mergeSort(arr, mid + 1, right); // 递归地对右半部分进行归并排序merge(arr, left, mid, right); // 合并两个已排序的子数组}}public static void merge(int[] arr, int left, int mid, int right) { // 合并两个有序子数组的函数int n1 = mid - left + 1; // 左半部分的长度int n2 = right - mid; // 右半部分的长度int[] L = new int[n1]; // 创建一个数组来存储左半部分int[] R = new int[n2]; // 创建一个数组来存储右半部分for (int i = 0; i < n1; i++) { // 将左半部分的元素复制到临时数组 L 中L[i] = arr[left + i];}for (int j = 0; j < n2; j++) { // 将右半部分的元素复制到临时数组 R 中R[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left; // 初始化索引变量while (i < n1 && j < n2) { // 合并两个有序数组if (L[i] <= R[j]) { // 如果左半部分的当前元素小于等于右半部分的当前元素arr[k] = L[i]; // 将左半部分的元素放到原数组中i++; // 左半部分的索引向后移动} else {arr[k] = R[j]; // 否则，将右半部分的元素放到原数组中j++; // 右半部分的索引向后移动}k++; // 原数组的索引向后移动}while (i < n1) { // 如果左半部分还有剩余元素，直接复制到原数组中arr[k] = L[i];i++;k++;}while (j < n2) { // 如果右半部分还有剩余元素，直接复制到原数组中arr[k] = R[j];j++;k++;}}public static void main(String[] args) { // 主函数，用于测试归并排序int[] arr = {12, 11, 13, 5, 6, 7}; // 定义一个待排序的数组mergeSort(arr, 0, arr.length - 1); // 调用归并排序函数，对整个数组进行排序System.out.println("Sorted array:"); // 输出排序后的数组for (int i : arr) { // 遍历数组并打印每个元素System.out.print(i + " ");}}
}

（四）性能分析

• 时间复杂度：归并排序的时间复杂度为O(n log n)，无论数组是否已经有序。

• 空间复杂度：归并排序的空间复杂度为O(n)，主要用于临时数组的存储。

• 稳定性：归并排序是一种稳定的排序算法，因为相等元素的相对位置不会改变。

（五）使用场景

        归并排序适用于大规模数据的排序，尤其是在数据量较大且对稳定性要求较高的场景中。由于其稳定的性能和线性对数时间复杂度，归并排序在实际应用中非常广泛，例如在外部排序、链表排序等场景中。

---

 

三、堆排序

（一）算法思想

        堆排序是一种基于二叉堆数据结构的排序算法。它的基本思想是：将数组构建成一个大根堆（或小根堆），然后通过不断调整堆的结构，将堆顶元素（最大值或最小值）与堆的最后一个元素交换，从而实现排序。

（二）算法原理

1. 构建大根堆：从最后一个非叶子节点开始，自底向上调整堆，使每个父节点的值都大于或等于其子节点的值。

2. 排序：将堆顶元素（最大值）与堆的最后一个元素交换，然后缩小堆的范围，重新调整堆，重复上述过程，直到整个数组有序。

（三）代码实现

C语言实现

#include <stdio.h>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 temp = arr[i];arr[i] = arr[largest];arr[largest] = temp; // 交换元素heapify(arr, n, largest); // 递归调整子树}
}void heapSort(int arr[], int n) {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); // 调整剩余的堆}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

Python实现

def heap_sort(arr):def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]  # 交换元素heapify(arr, n, largest)  # 递归调整子树n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)  # 构建大根堆for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 将堆顶元素与最后一个元素交换heapify(arr, i, 0)  # 调整剩余的堆arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)

Java实现

public class HeapSort { // 定义一个名为 HeapSort 的类public static void heapSort(int[] arr) { // 堆排序的主函数int n = arr.length; // 获取数组的长度// 构建大根堆for (int i = n / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始向上调整堆heapify(arr, n, i); // 调整以 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 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 temp = arr[i]; // 交换当前节点和最大值节点arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest); // 递归调整子树，确保子树仍然满足大根堆的性质}}public static void main(String[] args) { // 主函数，用于测试堆排序int[] arr = {12, 11, 13, 5, 6, 7}; // 定义一个待排序的数组heapSort(arr); // 调用堆排序函数，对数组进行排序System.out.println("Sorted array:"); // 输出排序后的数组for (int i : arr) { // 遍历数组并打印每个元素System.out.print(i + " ");}}
}

（四）性能分析

• 时间复杂度：堆排序的时间复杂度为O(n log n)，无论数组是否已经有序。

• 空间复杂度：堆排序的空间复杂度为O(1)，因为它是原地排序算法，不需要额外的存储空间。

• 稳定性：堆排序是一种不稳定的排序算法，因为相等元素的相对位置可能会改变。

（五）使用场景

        堆排序适用于大规模数据的排序，尤其是在内存空间有限的情况下。由于其稳定的性能和较低的空间复杂度，堆排序在实际应用中非常广泛，例如在优先队列、任务调度等场景中。

---

 

四、总结

排序算法	算法思想	时间复杂度	空间复杂度	稳定性	使用场景
快速排序	分治法，通过分区操作将数组分为两部分	O(n log n)（平均）<br>O(n^2)（最坏）	O(log n)	不稳定	大规模数据排序，数据随机分布
归并排序	分治法，将数组分为两部分并合并	O(n log n)	O(n)	稳定	大规模数据排序，对稳定性要求高
堆排序	基于二叉堆数据结构	O(n log n)	O(1)	不稳定	大规模数据排序，内存空间有限

        这三种排序算法在实际应用中各有优势。快速排序因其高效的平均性能而被广泛应用；归并排序因其稳定性和线性对数时间复杂度而适用于对稳定性要求较高的场景；堆排序则因其较低的空间复杂度而适用于内存受限的场景。

---

希望本文对您理解这些高效的排序算法有所帮助。在实际应用中，选择合适的排序算法需要综合考虑数据规模、数据特性、内存限制和稳定性要求等因素。