十大排序C++版本代码，带注释

您所在的位置：网站首页 › double数组排序 › 十大排序C++版本代码，带注释

十大排序C++版本代码，带注释

2023-03-05 23:10| 来源: 网络整理| 查看: 265

冒泡排序（Bubble Sort）

void bubble_sort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { // 外层循环控制排序轮数 bool flag = false; // 标志变量，用于优化排序 for (int j = 0; j < n - i - 1; ++j) { // 内层循环控制每轮比较次数 if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); flag = true; } } if (!flag) { // 如果本轮没有交换任何元素，则数组已有序 break; } } }

选择排序（Selection Sort）

void selection_sort(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]); // 将最小值交换到数组最前面 } }

插入排序（Insertion Sort）

void insertion_sort(int arr[], int n) { for (int i = 1; i < n; ++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; // 将待插入元素插入到正确的位置 } }

希尔排序（Shell Sort）

void shell_sort(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 = i - gap; while (j >= 0 && arr[j] > temp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = temp; } } }

归并排序（Merge Sort）

void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int L[n1], int R[n2]; for (int i = 0; i < n1; ++i) { L[i] = arr[left + i]; } for (int i = 0; i < n2; ++i) { R[i] = arr[mid + 1 + i]; } int i = 0, j = 0, k = left; while (i < n1 && j < n2) { // 归并两个有序子序列 if (L[i] arr[largest]) { largest = right; } if (largest != i) { // 如果最大值不在根节点 std::swap(arr[i], arr[largest]); // 将最大值交换到根节点 heapify(arr, n, largest); // 递归地维护堆 } } void heap_sort(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) { std::swap(arr[0], arr[i]); // 将堆顶元素交换到数组末尾 heapify(arr, i, 0); // 维护堆 } }

计数排序（Counting Sort）

void counting_sort(int arr[], int n) { int max_val = *std::max_element(arr, arr + n); // 找到最大值 int count[max_val + 1] = {}; // 初始化计数数组 for (int i = 0; i < n; ++i) { // 统计每个元素的出现次数 ++count[arr[i]]; } for (int i = 1; i = 0; --i) { // 从后往前遍历原始数组 output[count[arr[i]] - 1] = arr[i]; // 将元素放到正确的位置上 --count[arr[i]]; // 减少计数 } std::copy(output, output + n, arr); // 将临时数组复制回原始数组 }

桶排序（Bucket Sort）

void bucket_sort(float arr[], int n) { std::vector buckets[n]; // 创建 n 个空桶 for (int i = 0; i < n; ++i) { // 将元素放入对应的桶中 int idx = n * arr[i]; buckets[idx].push_back(arr[i]); } for (int i = 0; i < n; ++i) { // 对每个桶内部进行排序 std::sort(buckets[i]..begin(), buckets[i].end()); } int idx = 0; for (int i = 0; i < n; ++i) { // 将所有桶中的元素依次合并 for (float num : buckets[i]) { arr[idx++] = num; } } }

基数排序

void radix_sort(int arr[], int n) { int max_val = *std::max_element(arr, arr + n); // 找到最大值 int exp = 1; // 当前位数 std::vector output(n); // 临时数组 while (max_val / exp > 0) { // 从低位到高位依次处理每一位 std::vector count(10); // 初始化计数数组 for (int i = 0; i < n; ++i) { // 统计当前位数的出现次数 ++count[(arr[i] / exp) % 10]; } for (int i = 1; i < 10; ++i) { // 对计数数组进行前缀和处理 count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; --i) { // 从后往前遍历原始数组 output[count[(arr[i] / exp) % 10] - 1] = arr[i]; // 将元素放到正确的位置上 --count[(arr[i] / exp) % 10]; // 减少计数 } std::copy(output.begin(), output.begin() + n, arr); // 将临时数组复制回原始数组 exp *= 10; // 处理下一位 } }

【本文地址】

十大排序C++版本代码，带注释

十大排序C++版本代码，带注释

今日新闻

推荐新闻