在 C++ 中，常用的排序算法包括：
- 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它通过重复地遍历要排序的数列并比较相邻的两个数来排序。
代码如下：
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]) { | |
int temp = arr[j]; | |
arr[j] = arr[j + 1]; | |
arr[j + 1] = temp; | |
} | |
} | |
} | |
} |
- 选择排序（Selection Sort）
选择排序是一种简单的排序算法，它通过遍历数列来找到最小值并将其放到数列的起始位置，然后再从剩余未排序的数列中继续寻找最小值并放到已排序的数列末尾，以此类推直到所有数列排序完毕。
代码如下：
void selectionSort(int arr[], int n) { | |
for (int i = 0; i < n - 1; i++) { | |
int minIndex = i; | |
for (int j = i + 1; j < n; j++) { | |
if (arr[j] < arr[minIndex]) { | |
minIndex = j; | |
} | |
} | |
int temp = arr[i]; | |
arr[i] = arr[minIndex]; | |
arr[minIndex] = temp; | |
} | |
} |
- 插入排序（Insertion Sort）
插入排序是一种简单的排序算法，它通过将数列分成已排序和未排序两部分，然后从未排序的数列中取出第一个数，并插入到已排序的数列中的适当位置，使得已排序的数列仍然有序。
代码如下：
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; | |
} | |
} |
- 归并排序（Merge Sort）
归并排序是一种分治算法，它通过递归地将数列分成两半，然后将两半分别排序，最后将两半合并起来得到最终的排序结果。
代码如下：
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) { | |
int i = 0, j = 0, k = 0; | |
while (i < leftSize && j < rightSize) { | |
if (left[i] < right[j]) { | |
arr[k++] = left[i++]; | |
} else { | |
arr[k++] = right[j++]; | |
} | |
} | |
while (i < leftSize) { | |
arr[k++] = left[i++]; | |
} | |
while (j < rightSize) { | |
arr[k++] = right[j++]; | |
} | |
} | |
void mergeSort(int arr[], int n) { | |
if (n < 2) return; | |
int mid = n / 2; | |
int left[mid]; | |
int right[n - mid]; | |
for (int i = 0; i < mid; i++) { | |
left[i] = arr[i]; | |
} | |
for (int i = mid; i < n; i++) { | |
right[i - mid] = arr[i]; | |
} | |
mergeSort(left, mid); | |
mergeSort(right, n - mid); | |
merge(arr, left, mid, right, n - mid); | |
} |
- 快速排序（Quick Sort）
快速排序是一种分治算法，它通过选择一个基准元素，将数列分成两部分，使得左边的所有元素都小于基准元素，右边的所有元素都大于基准元素，然后递归地对两部分进行快速排序，最终得到有序的数列。
代码如下：
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++; | |
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; | |
} | |
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); | |
} | |
} |
这些排序算法的时间复杂度各不相同，在不同情况下可能会有所差异。你可以根据自己的需要来选择适合的排序算法。
除了以上几种常用的排序算法之外，还有其他一些不太常用的排序算法，例如：
- 希尔排序（Shell Sort）
希尔排序是一种插入排序的变种，它通过设置一个间隔来将数列划分成若干个小的数列，然后对每个小数列进行插入排序，最终得到有序的数列。
代码如下：
void shellSort(int arr[], int n) { | |
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 && arr[j - gap] > temp; j -= gap) { | |
arr[j] = arr[j - gap]; | |
} | |
arr[j] = temp; | |
} | |
} | |
} |
- 堆排序（Heap Sort）
堆排序是一种选择排序的变种，它通过建立一个堆来选择最大（或最小）的元素并放到数列末尾，然后将剩余的数列重新建堆并继续选择最大（或最小）的元素，以此类推直到所有数列排序完毕。
代码如下：
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); | |
} | |
} |
- 计数排序（Counting Sort）
计数排序是一种非比较排序算法，它通过计算数列中每个数出现的次数来排序。它的时间复杂度为 O (n)，因此在数据范围较小的情况下可以使用计数排序。
代码如下：
void countingSort(int arr[], int n, int maxValue) { | |
int counts[maxValue + 1]; | |
for (int i = 0; i <= maxValue; i++) { | |
counts[i] = 0; | |
} | |
for (int i = 0; i < n; i++) { | |
counts[arr[i]]++; | |
} | |
for (int i = 0, j = 0; i <= maxValue; i++) { | |
while (counts[i]-- > 0) { | |
arr[j++] = i; | |
} | |
} | |
} |
以上是 C++ 中的几种排序算法的代码，希望能帮到你。
