1.快速排序

思想：分治法 + 递归

  • 选取基准元素（pivot）

  • 将数组分为两部分：小于基准的放左边，大于基准的放右边

  • 递归地对左右子数组进行相同操作

void quick_sort(vector<int> &nums, int left, int right)
{
	if (left + 1 >= right)
	{
		return;
	}
	
	int first = left, last = right - 1, key = nums[first];
	while (first < last)
	{
		while (first < last && nums[last] >= key)
		{
			--last;
		}
		nums[first] = nums[last];
		while (first < last && nums[first] <= key)
		{
			++first;
		}
		nums[last] = nums[first];
	}
	nums[first] = key;
	quick_sort(nums, left, first);
	quick_sort(nums, first + 1, right);
}

2.插入排序

思想：构建有序序列

  • 从第一个元素开始，视为已排序

  • 取下一个元素，在已排序序列中从后向前扫描

  • 找到合适位置插入，重复直到所有元素有序

 特点：对小规模数据高效，适合基本有序的数据

void insert_sort(vector<int>& nums, int n)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j)
		{
			swap(nums[j], nums[j - 1]);
		}
	}
}

3.合并排序

思想：分治法 + 合并有序数组

  • 递归地将数组二分为子数组直到单个元素

  • 合并相邻子数组：比较两个数组头部元素，取较小者放入新数组

  • 重复合并直到整个数组有序

 优势：稳定排序，时间复杂度稳定O(nlogn)

void merge_sort(vector<int>& nums, int l, int r, vector<int> & temp)
{
	if (l + 1 >= r)
	{
		return;
	}

	int m = l + (r - l) / 2;
	merge_sort(nums, l, m, temp);
	merge_sort(nums, m, r, temp);

	int p = l, q = m, i = l;
	while (p < m || q < r)
	{
		if (q >= r || (p < m && nums[p] <= nums[q]))
		{
			temp[i++] = nums[p++];
		}
		else {
			temp[i++] = nums[q++];
		}
	}
	for (int i = l; i < r; ++i)
	{
		nums[i] = temp[i];
	}
}

4.冒泡排序

思想：重复交换相邻逆序元素

  • 从数组起始位置开始

  • 比较相邻元素，若逆序则交换

  • 每轮将最大元素"冒泡"到末尾

  • 重复n-1轮

优化：设置标志位检测提前完成  

void bubble_sort(vector<int>& nums, int n)
{
	bool flag;
	for (int i = 1; i < n; ++i)
	{
		flag = false;
		for (int j = 1; j < n - i - 1; ++j)
		{
			if (nums[j] < nums[j - 1])
			{
				swap(nums[j], nums[j - 1]);
				flag = true;
			}
		}
		if (!flag)
		{
			break;
		}
	}
}

5.选择排序

思想：每次选择最小元素

  • 在未排序序列中找到最小元素

  • 将其与未排序序列的首元素交换

  • 重复直到所有元素有序

特点：交换次数少（O(n)），但比较次数多 

void selection_sort(vector<int>& nums, int n)
{
	int mid;
	for (int i = 0; i < n - 1; ++i)
	{
		mid = i;
		for (int j = i + 1; j < n; ++j)
		{
			if (nums[j] < nums[mid])
			{
				mid = j;
			}
		}
		swap(nums[mid], nums[i]);
	}
}

6.桶排序

思想：分散-收集 + 子排序

  • 设置固定数量的空桶

  • 将元素分配到对应的桶中（映射函数）

  • 对每个非空桶进行排序（通常用插入排序）

  • 按顺序合并所有桶

适用：均匀分布的数据 

void bucketSort(vector<int>& nums) {
	if (nums.empty()) return;

	// Step 1: 找最大最小值，确定桶的数量
	int min_val = *min_element(nums.begin(), nums.end());
	int max_val = *max_element(nums.begin(), nums.end());

	// Step 2: 确定每个桶的范围和数量
	int bucket_size = 5;  // 可调参数，控制每个桶能装多少个数
	int bucket_count = (max_val - min_val) / bucket_size + 1;
	vector<vector<int>> buckets(bucket_count);

	// Step 3: 将数据放入对应的桶中
	for (int num : nums) {
		int index = (num - min_val) / bucket_size;
		buckets[index].push_back(num);
	}

	// Step 4: 每个桶内部排序，并合并到原数组
	int idx = 0;
	for (auto& bucket : buckets) {
		sort(bucket.begin(), bucket.end());  // 可换成插入排序等
		for (int num : bucket) {
			nums[idx++] = num;
		}
	}
}

7.希尔排序

思想：改进的插入排序

  • 定义增量序列（如n/2, n/4,...1）

  • 按当前增量分组，对每组进行插入排序

  • 增量逐步缩小，最后增量=1时整体排序

优势：突破O(n²)限制 

void shellSortCore(vector<int>& nums, int gap, int i) {
	int inserted = nums[i];
	int j;
    //  插入的时候按组进行插入
	for (j = i - gap; j >= 0 && inserted < nums[j]; j -= gap) {
		nums[j + gap] = nums[j];
	}
	nums[j + gap] = inserted;
}

void shellSort(vector<int>& nums) {
	int len = nums.size();
    //进行分组，最开始的时候，gap为数组长度一半
	for (int gap = len / 2; gap > 0; gap /= 2) {
        //对各个分组进行插入分组
		for (int i = gap; i < len; ++i) {
            //将nums[i]插入到所在分组正确的位置上
			shellSortCore(nums,gap,i);
		}
	}

	for (auto a : nums) {
		cout << a << "";
	}

}

8.堆排序

思想：利用堆数据结构

  • 构建最大堆（父节点 > 子节点）

  • 将堆顶元素（最大值）与末尾元素交换

  • 减少堆大小，重新调整堆

  • 重复直到堆大小为1

特点：原地排序，O(1)空间 

void heapify(vector<int>& nums, int n, int i)//对有一定顺序的堆，
//当前第i个结点取根左右的最大值（这个操作称heapfiy）
{
	int l = i * 2 + 1, r = i * 2 + 2;
	int max = i;
	if (l<n && nums[l]>nums[max])
		max = l;
	if (r<n && nums[r]>nums[max])
		max = r;
	if (max != i)
	{
		swap(nums[max], nums[i]);
		heapify(nums, n, max);
	}
}
void heapify_build(vector<int>& nums, int n)//建立大根堆，从树的倒数第二层第一个结点开始，
//对每个结点进行heapify操作，然后向上走
{
	int temp = (n - 2) / 2;
	for (int i = temp; i >= 0; i--)
		heapify(nums, n, i);

	for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}
void heapify_sort(vector<int>& nums, int n)//建立大根堆之后，每次交换最后一个结点和根节点（最大值），
//对交换后的根节点继续进行heapify（此时堆的最后一位是最大值，因此不用管他，n变为n-1）
{
	heapify_build(nums, n);
	for (int i = 0; i < n; i++)
	{
		swap(nums.front(), nums[n - i - 1]);
		heapify(nums, n - i - 1, 0);
	}
}

9.计数排序

思想：统计元素频次

  • 找出数组中最大最小值

  • 创建计数数组，统计每个元素出现次数

  • 累加计数数组（得到元素位置信息）

  • 反向填充目标数组

要求：整数排序，数据范围不大 

// 计数排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
	// 确保待排序容器非空
	if (vecRaw.size() == 0)
		return;

	// 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
	int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
	vector<int> vecCount(vecCountLength, 0);

	// 统计每个键值出现的次数
	for (int i = 0; i < vecRaw.size(); i++)
		vecCount[vecRaw[i]]++;
	
	// 后面的键值出现的位置为前面所有键值出现的次数之和
	for (int i = 1; i < vecCountLength; i++)
		vecCount[i] += vecCount[i - 1];

	// 将键值放到目标位置
	for (int i = vecRaw.size(); i > 0; i--)	// 此处逆序是为了保持相同键值的稳定性
		vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

10.基数排序

思想：按位分配收集

  • 从最低位到最高位（LSD）或反之（MSD）

  • 按当前位值分配到0-9的桶中

  • 按桶顺序收集元素

  • 重复直到所有位处理完毕

 适用：整数或字符串排序

// 辅助函数：求最大位数
int maxBit(const vector<int>& nums) {
    int maxNum = nums[0];
    for (int num : nums) {
        if (num > maxNum)
            maxNum = num;
    }

    int d = 0;
    while (maxNum > 0) {
        maxNum /= 10;
        ++d;
    }
    return d;
}

// 基数排序（LSD - 低位优先）
void radixSort(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return;

    int d = maxBit(nums);        // 获取最大位数
    vector<int> tmp(n);          // 临时数组
    vector<int> count(10);       // 计数器，0~9 的桶
    int radix = 1;               // 当前位权值（1, 10, 100...）

    // 对每一位进行排序
    for (int i = 0; i < d; ++i) {
        // 1. 初始化计数器
        fill(count.begin(), count.end(), 0);

        // 2. 统计每个桶中的元素个数
        for (int num : nums) {
            int k = (num / radix) % 10;
            count[k]++;
        }

        // 3. 将 count 转换为前缀和，表示每个桶的结束位置
        for (int j = 1; j < 10; ++j) {
            count[j] += count[j - 1];
        }

        // 4. 从后往前放入 tmp（保持稳定性）
        for (int j = n - 1; j >= 0; --j) {
            int k = (nums[j] / radix) % 10;
            tmp[count[k] - 1] = nums[j];
            count[k]--;
        }

        // 5. 将排序后的 tmp 拷贝回 nums
        nums = tmp;

        // 下一位
        radix *= 10;
    }
}

11.测试方法 

数组各数值可自行改变： 

int main()
{
	int n;
	vector<int> vec = { 14, 1, 5, 18, 9, 26, 18 };
	n = vec.size();
	vector<int> temp(n, 0);

	
#if 0
	vector<int> vec = { 170, 45, 75, 90, 802, 24, 2, 66 };
	int n = vec.size();
	vector<int> temp(n, 0);
	

	//手动输入vec
	vector<int> num;
	int n;
	cout << "input n";
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int p;
		cin >> p;
		num.push_back(p);
	}
	Print(num);

	//桶排序
	bucket_sort(vec);
	Print(vec);
	
	//sort(快排)
	sort(vec.begin(), vec.end());
	Print(vec);

	//quick_sort
	quick_sort(vec, 0, n);
	Print(vec);

	//merge_sort
	vector<int> temp(vec.size());
	merge_sort(vec, 0, n, temp);
	Print(vec);

	//insert_sort
	insert_sort(vec, n);
	Print(vec);

	//bubble_sort
	bubble_sort(vec, n);
	Print(vec);

	//selections_sort
	selection_sort(vec, n);
	Print(vec);

	//radix_sort
	radix_sort(vec, n);
	Print(vec);

	//count_sort
	count_sort(vec, temp, n);
	Print(temp);

	//堆排序
	heap_sort(vec, n);
	Print(vec);

#endif

	return 0;
}

12.算法特性对比表 

排序算法 平均时间复杂度 空间复杂度 稳定性 适用场景
快速排序 O(n log n) O(log n) 不稳定 通用排序，大规模数据
插入排序 O(n²) O(1) 稳定 小规模或基本有序数据
归并排序 O(n log n) O(n) 稳定 链表排序，外部排序
冒泡排序 O(n²) O(1) 稳定 教学用途，小规模数据
选择排序 O(n²) O(1) 不稳定 交换成本高的场景
桶排序 O(n + k) O(n + k) 稳定 均匀分布的浮点数
希尔排序 O(n log n) O(1) 不稳定 中等规模数据
堆排序 O(n log n) O(1) 不稳定 需要原地排序且O(1)空间
计数排序 O(n + k) O(k) 稳定 整数排序，范围小
基数排序 O(d(n + k)) O(n + k) 稳定 多位数排序，字符串字典序排序

注：

  • k: 桶的数量或计数范围

  • d: 数字的最大位数

  • 稳定性：相等元素排序后相对位置不变

  • 实际应用中快速排序、归并排序、堆排序最常用

# 算法 # 排序算法 # 数据结构 # c++
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

avatar AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

avatar AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError

avatar AI Agent技术社区