C++常用排序算法研究

在编程领域，排序算法是计算机科学中的核心概念，它涉及到数据结构和算法分析。C++作为一门强大且灵活的编程语言，提供了丰富的工具和库来实现各种排序算法。本研究主要探讨C++中的一些常见排序算法，包括它们的工作原理、性能特点以及如何用C++实现这些算法。 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单直观的排序算法，通过不断交换相邻的错误顺序元素来逐步完成排序。其时间复杂度在最坏情况下为O(n^2)，但在最佳情况下（已排序序列）可以达到O(n)。C++实现冒泡排序的关键在于嵌套循环和条件判断。 ```cpp void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } ``` 2. 插入排序（Insertion Sort） 插入排序的工作方式类似于我们手动排序一副扑克牌：将每个未排序的元素插入到已排序部分的正确位置。在C++中，可以使用一个循环来遍历未排序部分，然后逐个插入到已排序部分。插入排序在最好、最坏和平均情况下的时间复杂度都是O(n^2)。 ```cpp void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } ``` 3. 选择排序（Selection Sort） 选择排序每次从未排序的部分中找到最小（或最大）的元素，放到已排序部分的末尾。C++实现选择排序主要通过两个循环来实现，外层循环控制未排序部分，内层循环用于找到当前未排序部分的最小值。 ```cpp void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[min_idx]) { min_idx = j; } } std::swap(arr[i], arr[min_idx]); } } ``` 4. 快速排序（Quick Sort） 快速排序是由C.A.R. Hoare提出的，采用分治策略。它选取一个“基准”元素，然后将数组分为两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于基准。对这两部分再进行快速排序。C++实现快速排序需要递归调用。 ```cpp int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return (i + 1); } 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); } } ``` 5. 归并排序（Merge Sort） 归并排序也是基于分治策略，将大问题分解为小问题来解决。它将数组分成两半，分别对每半进行排序，然后合并两个已排序的子数组。C++实现归并排序需要用到额外的存储空间。 ```cpp void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; 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 l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } ``` 以上就是C++中常见的五种排序算法。每种算法都有其特定的应用场景和优缺点，如快速排序和归并排序在平均情况下的时间复杂度为O(n log n)，而冒泡排序和插入排序则为O(n^2)。在实际开发中，我们需要根据数据特性、内存限制和性能需求选择合适的排序算法。