当前位置: 首页 > news >正文

经典排序算法深度解析 - 实践

经典排序算法深度解析 - 实践

1. 冒泡排序(Bubble Sort)

底层思路

冒泡排序是一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

算法详解

  1. 从数组的第一个元素开始,比较相邻的两个元素。
  2. 如果第一个个元素比第二个元素大,则交换它们的位置。
  3. 继续比较下一对相邻元素,直到数组的末尾。
  4. 重复以上步骤,除了已经排好序的最后一个元素。
  5. 直到没有任何一对元素需要交换,排序完成。

模板代码

#include 
#include 
// 冒泡排序函数
// 参数:待排序的vector容器的引用
void bubbleSort(std::vector& arr) {int n = arr.size();  // 获取数组长度bool swapped;       // 标记是否发生交换// 外层循环控制需要进行多少轮比较for (int i = 0; i < n - 1; i++) {swapped = false;// 内层循环进行每一轮的比较和交换// 每轮结束后,最大的元素会"浮"到数组的末尾// 所以每轮可以少比较一个元素for (int j = 0; j < n - i - 1; j++) {// 如果当前元素大于下一个元素,则交换它们if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;  // 标记发生了交换}}// 如果在这一轮中没有发生交换,说明数组已经有序// 可以提前退出循环,优化性能if (!swapped) {break;}}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {64, 34, 25, 12, 22, 11, 90};std::cout << "冒泡排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用冒泡排序函数bubbleSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

冒泡排序示例:
排序前的数组: 64 34 25 12 22 11 90
排序后的数组: 11 12 22 25 34 64 90

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n)(当数组已经有序时)
    • 平均情况:O (n²)
    • 最坏情况:O (n²)
  • 空间复杂度:O (1)(只需要一个临时变量用于交换)

2. 选择排序(Selection Sort)

底层思路

选择排序的基本思想是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法详解

  1. 初始状态:整个数组为未排序状态。
  2. 从无序区中找到最小元素,与无序区的第一个元素交换位置。
  3. 此时无序区的第一个元素成为有序区的最后一个元素。
  4. 缩小无序区范围(去掉已排序的元素),重复步骤 2 和 3,直到无序区为空。

模板代码

#include 
#include 
// 选择排序函数
// 参数:待排序的vector容器的引用
void selectionSort(std::vector& arr) {int n = arr.size();  // 获取数组长度// 外层循环控制已排序区域的边界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;}}// 将找到的最小元素与未排序部分的第一个元素交换std::swap(arr[i], arr[minIndex]);}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {64, 25, 12, 22, 11};std::cout << "选择排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用选择排序函数selectionSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

选择排序示例:
排序前的数组: 64 25 12 22 11
排序后的数组: 11 12 22 25 64

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n²)
    • 平均情况:O (n²)
    • 最坏情况:O (n²)
  • 空间复杂度:O (1)(只需要一个临时变量用于交换)

3. 插入排序(Insertion Sort)

底层思路

插入排序的基本思想是:将待排序的元素按其值的大小插入到已经排序的部分的适当位置,直到所有元素都插入完毕。

算法详解

  1. 从数组的第二个元素开始,将其视为待插入的元素。
  2. 取出该元素,与前面已排序的元素依次比较。
  3. 如果前面的元素大于待插入元素,则将前面的元素后移一位。
  4. 找到合适的插入位置,将待插入元素放入该位置。
  5. 继续处理下一个未排序的元素,重复步骤 2-4,直到所有元素都插入完毕。

模板代码

#include 
#include 
// 插入排序函数
// 参数:待排序的vector容器的引用
void insertionSort(std::vector& arr) {int n = arr.size();  // 获取数组长度// 从第二个元素开始,因为第一个元素可以视为已排序for (int i = 1; i < n; i++) {int key = arr[i];  // 保存当前要插入的元素int j = i - 1;     // 从已排序部分的最后一个元素开始比较// 将大于key的元素向后移动一位while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 将key插入到正确的位置arr[j + 1] = key;}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {12, 11, 13, 5, 6};std::cout << "插入排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用插入排序函数insertionSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

插入排序示例:
排序前的数组: 12 11 13 5 6
排序后的数组: 5 6 11 12 13

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n)(当数组已经有序时)
    • 平均情况:O (n²)
    • 最坏情况:O (n²)
  • 空间复杂度:O (1)(只需要一个临时变量存储待插入元素)

4. 希尔排序(Shell Sort)

底层思路

希尔排序是插入排序的一种更高效的改进版本。它的基本思想是:先将整个待排序的数组分割成若干个子序列分别进行插入排序,待整个数组中的元素 "基本有序" 时,再对全体元素进行一次插入排序。

算法详解

  1. 选择一个增量序列(通常是 n/2, n/4, ..., 1)。
  2. 对于每个增量,按增量将数组分成若干个子序列。
  3. 对每个子序列进行插入排序。
  4. 减小增量,重复步骤 2 和 3,直到增量为 1。
  5. 当增量为 1 时,进行最后一次插入排序,此时整个数组已经基本有序,排序效率很高。

模板代码

#include 
#include 
// 希尔排序函数
// 参数:待排序的vector容器的引用
void shellSort(std::vector& arr) {int n = arr.size();  // 获取数组长度// 初始增量为数组长度的一半,之后每次减半for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];  // 保存当前要插入的元素// 找到temp在子序列中的正确位置int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];  // 元素后移}arr[j] = temp;  // 插入元素}}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {12, 34, 54, 2, 3};std::cout << "希尔排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用希尔排序函数shellSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

希尔排序示例:
排序前的数组: 12 34 54 2 3
排序后的数组: 2 3 12 34 54

复杂度分析

  • 时间复杂度:
    • 取决于增量序列的选择,通常在 O (n log n) 到 O (n²) 之间
    • 常用的 Hibbard 增量序列时间复杂度为 O (n^(3/2))
  • 空间复杂度:O (1)(只需要一个临时变量存储待插入元素)

5. 归并排序(Merge Sort)

底层思路

归并排序是建立在归并操作上的一种有效的排序算法,采用分治法(Divide and Conquer)的思想。它的基本思路是:将待排序序列分成两部分,对每部分递归地应用归并排序,然后将排序好的两部分合并成一个有序序列。

算法详解

  1. 分解:将输入的数组分成两个规模大致相等的子数组。
  2. 解决:递归地对两个子数组进行归并排序,如果子数组的长度为 1,则它已经是有序的。
  3. 合并:将两个已排序的子数组合并成一个单一的有序数组。

归并操作是归并排序的核心,它的步骤是:

  1. 创建一个临时数组来存放合并结果。
  2. 同时遍历两个子数组,比较当前元素,将较小的元素放入临时数组。
  3. 将剩余元素复制到临时数组。
  4. 将临时数组的内容复制回原数组。

模板代码

#include 
#include 
// 合并两个已排序的子数组
// 参数:arr-原数组, left-左子数组起始索引, mid-中间索引, right-右子数组结束索引
void merge(std::vector& arr, int left, int mid, int right) {int n1 = mid - left + 1;  // 左子数组的大小int n2 = right - mid;     // 右子数组的大小// 创建临时数组std::vector 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;    // 左子数组的起始索引int j = 0;    // 右子数组的起始索引int 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++;}
}
// 归并排序的递归函数
// 参数:arr-待排序数组, left-起始索引, right-结束索引
void mergeSort(std::vector& 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);}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {12, 11, 13, 5, 6, 7};std::cout << "归并排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用归并排序函数mergeSort(arr, 0, arr.size() - 1);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

归并排序示例:
排序前的数组: 12 11 13 5 6 7
排序后的数组: 5 6 7 11 12 13

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n log n)
    • 平均情况:O (n log n)
    • 最坏情况:O (n log n)
  • 空间复杂度:O (n)(需要额外的数组空间来存储合并结果)

6. 快速排序(Quick Sort)

底层思路

快速排序也是一种分治法排序算法,它的基本思想是:选择一个 "基准" 元素,将数组分为两部分,所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准后面,然后递归地对这两部分进行排序。

算法详解

  1. 选择一个元素作为 "基准"(pivot),通常选择第一个元素、最后一个元素或中间元素。
  2. 分区(partition):重新排列数组,所有比基准值小的元素移到基准前面,所有比基准值大的元素移到基准后面。
  3. 递归地将小于基准值的子数组和大于基准值的子数组进行快速排序。

分区操作的步骤:

  1. 选择最右边的元素作为基准。
  2. 初始化一个索引 i,表示小于基准的元素的边界。
  3. 遍历数组,对于每个元素,如果它小于或等于基准,则与 i 位置的元素交换,并将 i 加 1。
  4. 最后将基准元素与 i 位置的元素交换,这样基准元素就位于正确的位置。

模板代码

#include 
#include 
// 分区操作,返回基准元素的最终位置
// 参数:arr-待分区数组, low-起始索引, high-结束索引
int partition(std::vector& 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);  // 返回基准元素的索引
}
// 快速排序的递归函数
// 参数:arr-待排序数组, low-起始索引, high-结束索引
void quickSort(std::vector& arr, int low, int high) {if (low < high) {// pi是分区后的基准元素索引int pi = partition(arr, low, high);// 递归排序基准元素左边的子数组quickSort(arr, low, pi - 1);// 递归排序基准元素右边的子数组quickSort(arr, pi + 1, high);}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {10, 7, 8, 9, 1, 5};std::cout << "快速排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用快速排序函数quickSort(arr, 0, arr.size() - 1);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

快速排序示例:
排序前的数组: 10 7 8 9 1 5
排序后的数组: 1 5 7 8 9 10

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n log n)
    • 平均情况:O (n log n)
    • 最坏情况:O (n²)(当数组已经有序或逆序时)
  • 空间复杂度:O (log n)(递归调用栈的深度)

7. 堆排序(Heap Sort)

底层思路

堆排序是利用堆这种数据结构设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序的基本思想是:将待排序的数组构建成一个大顶堆,然后将堆顶元素与最后一个元素交换,再将剩余元素重新构建成一个大顶堆,重复这个过程直到整个数组有序。

算法详解

  1. 构建大顶堆:将数组转换为大顶堆(父节点大于子节点)。
  2. 堆排序:
    • 将堆顶元素(最大值)与数组末尾元素交换。
    • 缩小堆的范围(不包括已排序的末尾元素)。
    • 对剩余元素重新构建大顶堆。
    • 重复上述步骤,直到整个数组排序完成。

堆调整(heapify)操作是堆排序的核心,它的作用是将一个节点及其子树调整为满足堆的性质。

模板代码

#include 
#include 
// 堆调整函数,确保以root为根的子树满足大顶堆的性质
// 参数:arr-待调整的数组, n-堆的大小, root-要调整的节点索引
void heapify(std::vector& arr, int n, int root) {int largest = root;       // 初始化最大值为根节点int left = 2 * root + 1;  // 左子节点索引 = 2*root + 1int right = 2 * root + 2; // 右子节点索引 = 2*root + 2// 如果左子节点大于根节点,则更新最大值索引if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点大于当前最大值,则更新最大值索引if (right < n && arr[right] > arr[largest])largest = right;// 如果最大值不是根节点,则交换它们并递归调整受影响的子树if (largest != root) {std::swap(arr[root], arr[largest]);// 递归调整受影响的子树heapify(arr, n, largest);}
}
// 堆排序函数
// 参数:arr-待排序的数组
void heapSort(std::vector& arr) {int n = arr.size();// 构建大顶堆// 从最后一个非叶子节点开始向上调整for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 从堆中提取元素并排序for (int i = n - 1; i > 0; i--) {// 将当前堆顶元素(最大值)与堆的最后一个元素交换std::swap(arr[0], arr[i]);// 对剩余的元素重新构建大顶堆heapify(arr, i, 0);}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {12, 11, 13, 5, 6, 7};std::cout << "堆排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用堆排序函数heapSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

堆排序示例:
排序前的数组: 12 11 13 5 6 7
排序后的数组: 5 6 7 11 12 13

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n log n)
    • 平均情况:O (n log n)
    • 最坏情况:O (n log n)
  • 空间复杂度:O (1)(只需要一个临时变量用于交换)

8. 计数排序(Counting Sort)

底层思路

计数排序是一种非比较型整数排序算法,它的基本思想是:确定待排序数组中每个元素在排序后数组中的位置,通过计数每个元素出现的次数,然后计算出每个元素的正确位置。

算法详解

  1. 找出待排序数组中的最大值和最小值,确定计数范围。
  2. 创建一个计数数组,用于记录每个元素出现的次数。
  3. 遍历待排序数组,统计每个元素的出现次数,存储在计数数组中。
  4. 计算计数数组的前缀和,确定每个元素在输出数组中的起始位置。
  5. 反向遍历待排序数组,将每个元素放到输出数组的正确位置,并更新计数数组。
  6. 将输出数组复制回原数组。

模板代码

#include 
#include 
#include   // 用于std::max_element和std::min_element
// 计数排序函数
// 参数:arr-待排序的数组
void countingSort(std::vector& arr) {if (arr.empty()) return;  // 空数组直接返回// 找到数组中的最大值和最小值int max_val = *std::max_element(arr.begin(), arr.end());int min_val = *std::min_element(arr.begin(), arr.end());int range = max_val - min_val + 1;  // 计算数据范围int n = arr.size();std::vector output(n);         // 存储排序结果std::vector count(range, 0);   // 计数数组,初始化为0// 统计每个元素出现的次数for (int i = 0; i < n; i++) {count[arr[i] - min_val]++;}// 计算计数数组的前缀和,确定每个元素在输出数组中的起始位置for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 反向遍历原数组,将元素放到输出数组的正确位置// 反向遍历是为了保持排序的稳定性for (int i = n - 1; i >= 0; i--) {output[count[arr[i] - min_val] - 1] = arr[i];count[arr[i] - min_val]--;}// 将排序结果复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {4, 2, 2, 8, 3, 3, 1};std::cout << "计数排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用计数排序函数countingSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

计数排序示例:
排序前的数组: 4 2 2 8 3 3 1
排序后的数组: 1 2 2 3 3 4 8

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n + k),其中 n 是数组长度,k 是数据范围(max - min + 1)
    • 平均情况:O (n + k)
    • 最坏情况:O (n + k)
  • 空间复杂度:O (n + k)(需要额外的数组存储计数和输出结果)

9. 桶排序(Bucket Sort)

底层思路

桶排序是一种分布式排序算法,它的基本思想是:将待排序的数组分到有限数量的桶中,每个桶再分别进行排序(可以使用其他排序算法或递归地使用桶排序),最后将所有桶中的元素按顺序合并起来。

算法详解

  1. 确定桶的数量和范围,通常根据数据的分布情况来确定。
  2. 创建空桶,并将数组中的元素分配到相应的桶中。
  3. 对每个非空桶中的元素进行排序(可以使用其他排序算法)。
  4. 将所有已排序的桶中的元素依次合并,得到最终的排序结果。

模板代码

#include 
#include 
#include   // 用于std::sort和std::max_element
// 桶排序函数(假设数据是均匀分布的浮点数)
// 参数:arr-待排序的数组
void bucketSort(std::vector& arr) {if (arr.empty()) return;  // 空数组直接返回int n = arr.size();// 创建n个空桶std::vector> buckets(n);// 将数组元素分配到不同的桶中// 假设输入数据在[0, 1)范围内for (int i = 0; i < n; i++) {int bucketIndex = n * arr[i];  // 确定元素应该放入哪个桶buckets[bucketIndex].push_back(arr[i]);}// 对每个桶中的元素进行排序for (int i = 0; i < n; i++) {std::sort(buckets[i].begin(), buckets[i].end());}// 将所有桶中的元素合并回原数组int index = 0;for (int i = 0; i < n; i++) {for (float num : buckets[i]) {arr[index++] = num;}}
}
// 整数版本的桶排序
void bucketSortInt(std::vector& arr) {if (arr.empty()) return;  // 空数组直接返回int n = arr.size();int max_val = *std::max_element(arr.begin(), arr.end());// 创建适当数量的桶int bucketCount = max_val / n + 1;std::vector> buckets(bucketCount);// 将数组元素分配到不同的桶中for (int num : arr) {int bucketIndex = num / n;  // 确定元素应该放入哪个桶buckets[bucketIndex].push_back(num);}// 对每个桶中的元素进行排序for (int i = 0; i < bucketCount; i++) {std::sort(buckets[i].begin(), buckets[i].end());}// 将所有桶中的元素合并回原数组int index = 0;for (int i = 0; i < bucketCount; i++) {for (int num : buckets[i]) {arr[index++] = num;}}
}
// 打印数组元素的函数
template 
void printArray(const std::vector& arr) {for (const T& num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 浮点数示例std::vector floatArr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};std::cout << "桶排序(浮点数)示例:" << std::endl;std::cout << "排序前的数组: ";printArray(floatArr);bucketSort(floatArr);std::cout << "排序后的数组: ";printArray(floatArr);// 整数示例std::vector intArr = {12, 34, 54, 2, 3};std::cout << "\n桶排序(整数)示例:" << std::endl;std::cout << "排序前的数组: ";printArray(intArr);bucketSortInt(intArr);std::cout << "排序后的数组: ";printArray(intArr);return 0;
}

输入输出示例

桶排序(浮点数)示例:
排序前的数组: 0.897 0.565 0.656 0.1234 0.665 0.3434
排序后的数组: 0.1234 0.3434 0.565 0.656 0.665 0.897
桶排序(整数)示例:
排序前的数组: 12 34 54 2 3
排序后的数组: 2 3 12 34 54

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (n + k),其中 n 是数组长度,k 是桶的数量
    • 平均情况:O (n + k)
    • 最坏情况:O (n²)(当所有元素都放入同一个桶中时)
  • 空间复杂度:O (n + k)(需要额外的空间存储桶和桶中的元素)

10. 基数排序(Radix Sort)

底层思路

基数排序是一种非比较型整数排序算法,它的基本思想是:按照数字的位数从低到高(或从高到低)依次对数据进行排序。基数排序可以看作是多轮的桶排序,每一轮根据当前位的值将元素分配到不同的桶中,然后再按桶的顺序将元素收集起来。

算法详解

  1. 确定待排序数组中最大元素的位数,这决定了需要进行多少轮排序。
  2. 从最低位开始,对每一位进行排序:
    • 创建 10 个桶(0-9),对应数字的 0-9。
    • 将数组中的元素根据当前位的值分配到相应的桶中。
    • 按桶的顺序(0-9)将元素收集起来,形成新的数组。
  3. 对下一位重复步骤 2,直到所有位都处理完毕。

模板代码

#include 
#include 
#include   // 用于std::max_element
// 获取数字num的第d位数字(从0开始计数,0表示个位)
int getDigit(int num, int d) {// 计算10^dint power = 1;for (int i = 0; i < d; i++) {power *= 10;}// 返回第d位数字return (num / power) % 10;
}
// 基数排序函数
// 参数:arr-待排序的数组
void radixSort(std::vector& arr) {if (arr.empty()) return;  // 空数组直接返回// 找到数组中的最大值int max_val = *std::max_element(arr.begin(), arr.end());// 计算最大值的位数,确定需要进行多少轮排序int max_digits = 0;while (max_val > 0) {max_val /= 10;max_digits++;}int n = arr.size();// 对每一位进行排序for (int d = 0; d < max_digits; d++) {// 创建10个桶(0-9)std::vector> buckets(10);// 将元素分配到相应的桶中for (int num : arr) {int digit = getDigit(num, d);buckets[digit].push_back(num);}// 按桶的顺序将元素收集起来int index = 0;for (int i = 0; i < 10; i++) {for (int num : buckets[i]) {arr[index++] = num;}}}
}
// 打印数组元素的函数
void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}
int main() {// 示例输入std::vector arr = {170, 45, 75, 90, 802, 24, 2, 66};std::cout << "基数排序示例:" << std::endl;std::cout << "排序前的数组: ";printArray(arr);// 调用基数排序函数radixSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

输入输出示例

基数排序示例:
排序前的数组: 170 45 75 90 802 24 2 66
排序后的数组: 2 24 45 66 75 90 170 802

复杂度分析

  • 时间复杂度:
    • 最佳情况:O (d*(n + b)),其中 d 是位数,n 是数组长度,b 是基数(这里是 10)
    • 平均情况:O (d*(n + b))
    • 最坏情况:O (d*(n + b))
  • 空间复杂度:O (n + b)(需要额外的空间存储桶和桶中的元素)

总结

以上介绍了 C++ 中常用的十种排序算法,它们各有特点和适用场景:

  1. 冒泡排序:简单但效率低,适用于小规模数据或几乎有序的数据。
  2. 选择排序:简单直观,交换次数少,但时间复杂度高。
  3. 插入排序:对小规模数据或几乎有序的数据效率较高。
  4. 希尔排序:插入排序的改进版,通过分组减少数据移动。
  5. 归并排序:稳定的 O (n log n) 排序算法,需要额外空间。
  6. 快速排序:实际应用中最快的排序算法之一,平均性能好。
  7. 堆排序:不需要额外空间的 O (n log n) 排序算法。
  8. 计数排序:适用于整数且范围不大的情况,非比较排序。
  9. 桶排序:适用于均匀分布的数据,可用于整数和浮点数。
  10. 基数排序:适用于整数或可以表示为固定位数的字符串。

在实际应用中,应根据数据的特点(大小、分布、类型等)选择合适的排序算法,以获得最佳的性能。

http://www.hskmm.com/?act=detail&tid=19012

相关文章:

  • Java网络编程(七):NIO实战构建高性能Socket服务器 - 实践
  • Unigine整合Myra UI Library全纪录(3):整合与优化
  • Tita 项目经营一体化建筑业企业解决方案
  • CD78.【C++ Dev】以AVL任务的bug讲讲调试技巧
  • 实用指南:AI 时代的安全防线:国产大模型的数据风险与治理路径
  • 写给自己的年终复盘以及未来计划
  • 最近难得的一点思考
  • np.random.rand
  • Nexpose 8.22.0 for Linux Windows - 漏洞扫描
  • 冯延巳-风乍起,吹皱一池春水。
  • 大唐名相张九龄-海上生明月,天涯共此时
  • 王昌龄的态度
  • 开发知识点-Python-virtualenv
  • 白居易-那个寒冷的夜晚,思念像潮水般袭来。想得家中夜深坐,还应说着远行人。
  • 2025年移动厕所厂家口碑排行榜:环保移动厕所,泡沫封堵移动厕所,市区公园露营地移动厕所,装配式移动厕所,公共移动厕所定制安装公司选择指南!
  • Metasploit Framework 6.4.90 (macOS, Linux, Windows) - 开源渗透测试框架
  • VSCode+Window+Chrome常用快捷键
  • 那些诗词那些花|君不见此玫瑰于晚秋的夜色中凄然绽放,别具一格。
  • Linux环境下VSCode快速安装终极指南:debian/ubuntu/linux平台通用
  • 醉后不知天在水,满船清梦压星河
  • Apache Doris性能优化全解析:慢查询定位与引擎深度调优 - 教程
  • 【诗词解读】跨越千年的文脉传承:月与酒是中国人的永恒浪漫
  • 秋风中的窘境,一代诗圣的安居梦
  • 辛弃疾:明月团团高树影,十里水沉烟冷
  • 坐观垂钓者,徒有羡鱼情:孟浩然与当代人的无能为力之痛
  • Go与C# 谁才更能节省内存? - 详解
  • SQL子查询(Subquery)优化
  • 【诗词解读】王维的温柔都藏在他的诗句里:吾谋适不用,勿谓知音稀。
  • shiro反序列化及规避检测
  • 2台Linux 服务器文件夹同步,使用rsync工具