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

【杂乱算法】七种常见的排序

news 来源：原创 2024/9/19 8:55:23

文章目录

- - - 1、选择排序 O(n^2)
    - 2、插入排序 O(n^2)
    - 3、希尔排序 O(n log n)
    - 4、冒泡排序 O(n^2)
    - 5、快速排序 O(n log n)
    - 6、归并排序 O(n log n)
    - 7、基数排序 O(d(n+k))

1、选择排序 O(n^2)

每次从未排序部分选择最小元素放到已排序部分的末尾。

#include <iostream>
#include <vector>
#include <algorithm>void selection_sort(std::vector<int>& arr, int l, int r) {for (int i = l; i < r - 1; i++) {int ind = i;for (int j = i + 1; j < r; j++) {if (arr[j] < arr[ind]) ind = j;}std::swap(arr[i], arr[ind]);}
}// 打印向量的辅助函数
void printVector(const std::vector<int>& vec) {for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr = {64, 25, 12, 22, 11, 35};std::cout << "原始数组: ";printVector(arr);selection_sort(arr, 0, arr.size());std::cout << "排序后数组: ";printVector(arr);return 0;
}

选择排序的特点:

时间复杂度: O(n^2),无论输入如何都是这个复杂度
空间复杂度: O(1),原地排序
不稳定排序: 相等元素的相对顺序可能会改变
交换次数少: 每次外循环最多交换一次

2、插入排序 O(n^2)

从第二个元素开始, 将每个元素插入到已排序的前面部分的合适位置, 通过不断交换相邻元素实现插入.（找到第一个小于它的数。）

#include <iostream>
#include <vector>void insert_sort(std::vector<int>& arr, int l, int r) {for (int i = l + 1; i < r; i++) {int j = i;while (j > l && arr[j] < arr[j - 1]) {swap(arr[j], arr[j - 1]);j -= 1;}}
}// 打印数组的辅助函数
void printArray(const std::vector<int>& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};std::cout << "原始数组: ";printArray(arr);insert_sort(arr, 0, arr.size());std::cout << "排序后数组: ";printArray(arr);return 0;
}

插入排序的特点：

时间复杂度：平均和最坏情况下为O(n^2)，最好情况（已排序）为O(n)
空间复杂度：O(1)，原地排序
稳定排序：相等元素的相对顺序不会改变
对于小型数组或基本有序的数组，插入排序可能比其他更复杂的排序算法表现更好

3、希尔排序 O(n log n)

#include <iostream>
#include <vector>// 对子序列进行插入排序
void unguarded_insert_sort(vector<int>&arr, int l, int r, int step) {int ind = l;//确定最小值的边界for (int i = l + step; i < r; i += step) {if (arr[i] < arr[ind]) ind = i;}//挨个移动，确保稳定性while (ind > l) {swap(arr[ind], arr[ind - step]);ind -= step;}for (int i = l + 2 * step; i < r; i += step) {int j = i;while (arr[j] < arr[j - step]) {swap(arr[j], arr[j - step]);j -= step;}}return ;
}// 希尔排序实现
void shell_sort(std::vector<int>& arr, int l, int r) {int k = 2, n = (r - l + 1), step;do {step = n / k == 0 ? 1 : n / k;for (int i = l, I = l + step; i < I; i++) {//大范围内分组进行插入排序unguarded_insert_sort(arr, i, r, step);}k *= 2;} while (step != 1);
}// 打印数组
void printArray(const std::vector<int>& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};std::cout << "原始数组: ";printArray(arr);shell_sort(arr, 0, arr.size() - 1);std::cout << "排序后数组: ";printArray(arr);return 0;
}

希尔排序的优点：

性能优于简单插入排序，尤其是对于大规模的乱序数组。
不需要额外的存储空间，是原地排序算法。
对于部分有序的数组，效率较高。

缺点：

增量序列的选择对算法的性能影响较大，不同的增量序列可能导致不同的时间复杂度。
不稳定排序：相同键值的记录可能会在排序后改变其相对位置。

时间复杂度：

最坏情况：O(n^2)
平均情况：依赖于增量序列的选择，通常在O(n^1.3)到O(n2)之间
最好情况：O(n log n)

空间复杂度：O(1)

4、冒泡排序 O(n^2)

/* 冒泡排序 */
void bubbleSort(vector<int> &nums) {// 外循环：未排序区间为 [0, i]for (int i = nums.size() - 1; i > 0; i--) {// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j = 0; j < i; j++) {if (nums[j] > nums[j + 1]) {// 交换 nums[j] 与 nums[j + 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j + 1]);}}}
}

性能特征：
- 时间复杂度：最坏情况和平均情况都是 O(n^2)，最好情况（已经排好序）是 O(n)
- 空间复杂度：O(1)，只需要一个临时变量来交换元素
- 稳定性：稳定排序算法
优缺点：

优点：
- 实现简单，容易理解
- 不需要额外的存储空间
- 对于小规模数据或基本有序的数据效率较高
缺点：
- 对于大规模数据效率低下
- 平均时间复杂度较高，为 O(n^2)

5、快速排序 O(n log n)

选择一个基准元素，将数组分为小于和大于基准的两个部分，递归地对这两个部分进行排序，从而实现整体有序。

void quick_sort(int *arr, int l, int r) {if (r - l <= 2) {if (r - l <= 1) return ;if (arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);return ;}// partitionint x = l, y = r - 1, z = arr[l];while (x < y) {while (x < y && z <= arr[y]) --y;if (x < y) arr[x++] = arr[y];while (x < y && arr[x] <= z) ++x;if (x < y) arr[y--] = arr[x];}arr[x] = z;quick_sort(arr, l, x);quick_sort(arr, x + 1, r);return ;
}

时间复杂度：
- 最佳情况：O(n log n)
- 平均情况：O(n log n)
- 最坏情况：O(n^2)（当数组已经排序或近乎排序时）
空间复杂度：
- 平均情况：O(log n)
- 最坏情况：O(n)（递归调用栈的深度）
优点：
- 原地排序，不需要额外的存储空间
- 平均情况下效率高
- 缓存友好
缺点：
- 不稳定排序（相等元素的相对位置可能改变）
- 对于小数组，可能不如插入排序等简单算法效率高
- 在最坏情况下性能较差

6、归并排序 O(n log n)

std::vector<int> buff;void merge_sort(std::vector<int>& arr, int l, int r) {if (r - l <= 1) return;int mid = (l + r) / 2;merge_sort(arr, l, mid);merge_sort(arr, mid, r);// mergeint p1 = l, p2 = mid, k = 0;while (p1 < mid || p2 < r) {if (p2 == r || (p1 < mid && arr[p1] <= arr[p2])) {buff[k++] = arr[p1++];} else {buff[k++] = arr[p2++];}}for (int i = l; i < r; i++) arr[i] = buff[i - l];
}

基本思想：
- 将待排序的数列递归地分成两半，分别对两半进行排序。
- 然后将已排序的两半合并成一个有序序列。
工作流程： a. 分割：将数组递归地分成两半，直到每个子数组只包含一个元素。 b. 合并：将两个有序子数组合并成一个更大的有序数组。
时间复杂度：
- 最佳情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
空间复杂度：
- O(n)，因为合并过程中需要额外的空间
稳定性：
- 归并排序是稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
优点：
- 效率高且稳定
- 适用于外部排序（当数据量很大，无法全部装入内存时）
缺点：
- 需要额外的存储空间
- 对于小规模数据，可能不如插入排序等简单算法效率高

7、基数排序 O(d(n+k))

基数排序是一种非比较型整数排序算法，通过从最低有效位到最高有效位的顺序，对整数的每一位进行分配和收集，最终实现对整数序列的排序。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>void radixSort(std::vector<int>& arr) {// 假定arr[0] 是最大数// 1. 通过遍历arr, 找到数组中真正最大值int max = arr[0];for (size_t i = 1; i < arr.size(); i++) {if (arr[i] > max) {max = arr[i];}}// 计算最大数字是几位数int maxLength = std::to_string(max).length();// 定义一个二维数组， 就是10个桶std::vector<std::vector<int>> bucket(10);// 根据最大长度的数决定比较的次数for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {// 把每一个数字分别计算本轮循环的位数的值std::vector<int> bucketElementCounts(10, 0);for (size_t j = 0; j < arr.size(); j++) {// 计算int digitOfElement = (arr[j] / n) % 10;// 把当前遍历的数据放入指定的数组中bucket[digitOfElement].push_back(arr[j]);// 记录数量bucketElementCounts[digitOfElement]++;}// 记录取的元素需要放的位置size_t index = 0;// 把各个桶中(10个桶)存放的数字取出来, 放入到arr中for (size_t k = 0; k < bucketElementCounts.size(); k++) {// 如果这个桶中，有数据才取，没有数据就不取了if (bucketElementCounts[k] != 0) {// 循环取出元素for (size_t l = 0; l < bucket[k].size(); l++) {// 取出元素arr[index++] = bucket[k][l];}// 清空桶bucket[k].clear();}}}
}int main() {std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);// 输出排序结果for (int num : arr) {std::cout << num << " ";}return 0;
}