C++实现常见内排序算法

"这篇资源主要介绍了常用的内排序算法，并提供了C++实现代码，包括插入排序、希尔排序、冒泡排序和快速排序。" 在计算机科学中，内排序（In-place sorting）是指在排序过程中只使用固定数量的额外空间的排序算法。这些算法在内存管理上非常高效，特别适用于内存资源有限的情况。以下是这四种排序算法的详细说明： 1. **插入排序（Insertion Sort）**： 插入排序是一种简单的排序方法，它的工作原理类似于人们整理扑克牌的过程。算法通过将每个元素插入到已排序部分的正确位置来逐步构建最终的有序序列。插入排序的时间复杂度在最好情况下（已排序）为O(n)，最坏情况下（逆序）为O(n^2)。 ```cpp void insert_sort(int arr[], int size) { for (int i = 1; i < size; i++) { int temp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } ``` 2. **希尔排序（Shell Sort）**： 希尔排序是插入排序的一种优化版本，通过将待排序数组分组，然后对每组进行插入排序，逐渐减小组间隔，直至间隔为1。这种方法减少了元素的移动次数，提高了效率。希尔排序的时间复杂度取决于所选的排序增量序列，通常为O(n^1.3)到O(n^1.5)。 ```cpp void shell_sort(int arr[], int size) { for (int gap = size / 2; gap > 0; gap /= 2) { for (int i = gap; i < size; 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; } } } ``` 3. **冒泡排序（Bubble Sort）**： 冒泡排序通过重复遍历数组，每次比较相邻元素并交换（如果需要），使得较大的元素逐渐“浮”到数组末尾。冒泡排序的时间复杂度在最坏和平均情况下均为O(n^2)，但在最好情况下（已排序）可以达到O(n)。 ```cpp void bubble_sort(int arr[], int size) { for (int i = 0; i < size - 1; i++) for (int j = 0; j < size - i - 1; j++) if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } ``` 4. **快速排序（Quick Sort）**： 快速排序是一种高效的分治算法，选取一个“基准”元素，将数组分为两部分，一部分的元素都小于基准，另一部分都大于基准，然后递归地对这两部分进行快速排序。快速排序在平均情况下的时间复杂度为O(n log n)，最坏情况下为O(n^2)。 ```cpp void quick_sort(int arr[], int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quick_sort(arr, low, pivot - 1); quick_sort(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 - 1; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } ``` 此外，还提到了二分插入排序（Binary Insertion Sort），这是一种改进的插入排序，它利用了二分查找来确定插入位置，降低了比较次数，但并没有改变时间复杂度的基本性质。 这些排序算法的选择通常取决于具体的应用场景，如数据规模、数据分布以及对稳定性的需求。在实际编程中，还可以考虑使用现代库（如C++标准库中的`std::sort`）提供的内置排序函数，它们通常采用更高效的算法实现，如归并排序或堆排序。