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

C++ 中常见排序算法(归并、快速、桶、基数排序)

article 2025/1/26 14:10:03

本文讲解排序算法中常见又较复杂的几种排序算法：归并排序、快速排序、桶排序、基数排序.

1. 归并排序

步骤：

  • 递归排序中点左边和中点右边
  • 然后归并
  • 两个指针，各自指向最值，然后对比两边的最小值，最小的放入临时数组中
  • 更新指针，类推
  • 最后剩余的一边直接塞入临时数组的尾部
  • 即完成排序

算法分析：

（1）时间复杂度：O(nlog2n)

（2）空间复杂度：O(n)

优点：

  1. 稳定性： 相同元素的相对顺序保持不变
  2. 可扩展性： 很容易扩展到计算环境中，通过并行归并来提高排序效率

缺点：

  1. 额外空间：需要开辟一个额外的空间来存储合并后的结果
  2. 复杂性：算法实现相对复杂，相比于简单的算法而言

以下是C++归并排序的代码模板

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> temp;   // 定义临时数组

// 输出函数
void merge_print(const vector<int>& v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);       // 递归排序左边
    mergeSort(arr, mid + 1, r);   // 递归排序右边
    int i = l, j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= r) {     // 归并
        if (arr[i] <= arr[j]) {
            temp[cnt++] = arr[i++];
        }
        else {
            temp[cnt++] = arr[j++];
        }
    }
    while (i <= mid) {               // 剩余的一边直接塞入数组
        temp[cnt++] = arr[i++];
    }
    while (j <= r) {
        temp[cnt++] = arr[j++];
    }
    for (int i = 0; i < r - l + 1; i++) {
        arr[i + l] = temp[i];               // 重新赋值回来
    }
}

int main() {

    vector<int> v;
    v.push_back(2);
    v.push_back(5);
    v.push_back(1);
    v.push_back(4);
    v.push_back(6);
    v.push_back(3);

    temp.resize((int)v.size(), 0);

    cout << "排序前：" << endl;
    merge_print(v);

    mergeSort(v, 0, (int)v.size() - 1);

    cout << "归并排序后：" << endl;
    merge_print(v);

    cout << endl;

    system("pause");
    return 0;
}

2. 快速排序

步骤：

设当前的待排序的序列为 R[low,hight] ， 其中 low<=hight。同时选取首元素为基准元素。

  • 步骤一：选取首元素的第一个元素作为基准元素 pivot=R[low] ，i=low ，j=hight。

  • 步骤二：从右向左扫描，找到小于等于 pivot 的数，如果找到，R[i] 和 R[j] 交换 ，i++。

  • 步骤三：从左向右扫描，找到大于 pivot 的数，如果找到，R[i] 和 R[j] 交换，j--。

  • 步骤四：重复 步骤二~步骤三，直到 j 与 i 的指针重合 返回位置 mid=i ，该位置的数正好是 pivot 元素。

算法分析：

（1）时间复杂度：O(nlogn)

（2）空间复杂度：O(lognn)

优点：

  1. 高效性：快速排序在大多数情况下具有较高的排序效率
  2. 适应性：适合各种数据类型的额排序
  3. 原地排序：不需要额外的存储空间

缺点：

  1. 最坏情况下时间复杂度为 O(n^2)
  2. 不稳定性：相同元素的相对顺序可能会改变

以下是 C++快速排序算法的模板

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


int part(vector<int>& nums, int low, int hight) {   // 划分函数
	int i = low, j = hight, pivot = nums[low];      // 以首元素为基准元素
	while (i < j) {
		while (i < j && nums[j] > pivot) {     // 从左向右开始找一个小于等于pivot数的值
			j--;                   
		} 
		if (i < j) {                      // 如果当前元素小于pivot的值，则交换，i向右移一位
			swap(nums[i], nums[j]);
			i++;
		}
		while (i < j && nums[i] <= pivot) {    // 左边和右边相反的操作
			i++;
		}
		if (i < j) {
			swap(nums[i], nums[j]);
			j--;
		}
	}
	return i;         //返回最终划分完成后基准元素所在的位置
}

// 快速排序
void QuickSort(vector<int>& nums, int low, int hight) {
	int mid;
	if (low < hight) {
		mid = part(nums, low, hight);  // 返回基准元素位置
		QuickSort(nums, low, mid - 1); // 左区间递归快速排序
		QuickSort(nums, mid + 1,hight);// 右区间递归快速排序
	}
}

int main() {


	vector<int> nums;

	nums.push_back(30);
	nums.push_back(24);
	nums.push_back(5);
	nums.push_back(58);
	nums.push_back(18);

	cout << "排序前：" << endl;
	for (int i = 0; i < nums.size(); i++) {
		cout << nums[i] << " ";
	}
	cout << endl;

	QuickSort(nums, 0, nums.size()-1);

	cout << "快速排序后：" << endl;
	for (int i = 0; i < nums.size(); i++) {
		cout << nums[i] << " ";
	}
	cout << endl;

	system("pause");

	return 0;
}

3. 桶排序

步骤：

  • 分组
  • 桶内排序
  • 合并

算法分析：

（1）时间复杂度：取决于对桶内选择的排序算法

（2）空间复杂度：O(n)

优点：

  1. 适用于一定范围内的整数或浮点数排序，不需要比较元素之间的大小
  2. 较稳定的一种排序算法

缺点：

  1. 当数据范围较大是，需要的桶数量较多，会消耗较多的内存空间
  2. 桶排序是一种线性排序，不适合大规模数据排序

以下是 C++桶排序算法的模板

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

// 输出函数
void bucket_print(const vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

// 插入排序
void insert_sort(vector<int>& v) {
	for (int i = 1; i < v.size(); i++) {
		int key = v[i];
		int j = i - 1;
		while (j >= 0 && v[j] > key) {
			v[j + 1] = v[j];
			j--;
		}
		v[j + 1] = key;
	}
}

void bucket_sort(vector<int>& v) {
	int i;
	int maxValue = v[0];
	for (i = 1; i < v.size(); i++) {
		if (maxValue < v[i]) {
			maxValue = v[i];
		}
	}

	// 设置10个桶
	vector<int> buckts[10];
	// 桶的大小bucketSize根据数组最大值确定：比如最大值99， 桶大小10
	// 最大值999，桶大小100
	// 根据最高位数字映射到相应的桶，映射函数为 v[i]/bucketSize
	int bucktSize = 1;
	while (maxValue) {
		maxValue /= 10;
		bucktSize *= 10;
	}
	bucktSize /= 10;

	// 放入桶中
	for (int i = 0; i < v.size(); i++) {
		int index = v[i] / bucktSize;        // 映射函数
		buckts[index].push_back(v[i]);
		// 插入排序，对每个桶都排序
		insert_sort(buckts[index]);
	}

	// 顺序访问桶，合并成一个有序序列
	int index = 0;
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < buckts[i].size(); j++) {
			v[index++] = buckts[i][j];
		}
	}


}

int main() {

	vector<int> v;
	v.push_back(6);
	v.push_back(15);
	v.push_back(3);
	v.push_back(422);
	v.push_back(25);

	cout << "排序前：" << endl;
	bucket_print(v);

	// 桶排序
	bucket_sort(v);

	cout << "桶排序后：" << endl;
	bucket_print(v);

	cout << endl;

	system("pause");

	return 0;
}

4. 基数排序

步骤：

  • 步骤一： 申请 10 个队列基数桶，根据每个元素的基数，来映射到对应桶中 0~9
  • 步骤二： 求出数组中最大的元素，并求出他的位数n，作为操作排序的次数
  • 步骤三： 操作 n 次，从个位数开始，取出各个数的位数，根据各个数的位数值放入不同的桶中
  • 步骤四： 顺序访问桶，如果桶中有数据，则取出桶中最底下元素放入到数组中，队列桶出队
  • 步骤五： 操作 n 次以后，不断更新数组和队列桶，n 次时，数组中元素已有序

图示：

 

 

第一轮：

 

 

第二轮

 

 

第三轮

 

 

算法分析：

（1）时间复杂度：O(d(n+r)), d 是数字的位数，n 是待排序元素的数量，r 是基数(radix)

（2）空间复杂度：取决于使用的桶的数量和存储桶的方式

优点：

  1. 不需要进行元素间的比较

缺点：

  1. 需要用额外的空间来存储桶，对于大型数据可能会消耗较多的内存
  2. 对于复杂的数据类型如浮点数或者负数的情况，需要额外的处理来实现基数排序

以下是 C++基数排序算法的代码模板：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

// 输出函数
void radix_print(const vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

// 基数排序
void radix_sort(vector<int>& arr) {
	int n = arr.size();
	vector<queue<int>> bucket(10);
	
	// 取出待排序元素中的最大值，求出它的最大位数，即为判断循环的条件
	int maxElement = *max_element(arr.begin(), arr.end());
	int N = 0;   // 判断待排序次数
	while (maxElement) {
		maxElement /= 10;
		N++;
	}
	int t = 1;       // 取位数
	while (N > 0) {
		// 取出每个数的基数，从个位数开始
		
		for (int i = 0; i < n; i++) {
			int index = (arr[i] / t) % 10;			// 找到对应的基数桶塞入			  
			bucket[index].push(arr[i]);
		}

		int index = 0;          // 重新放回数组中
		for (int i = 0; i < 10; i++) {
			while (!bucket[i].empty()) {               // 如果该桶不为空，再出队
				arr[index++] = bucket[i].front();	   // 则取出队首元素,加入数组中
				bucket[i].pop();
			}
		}
		t *= 10;
		N--;
	}
}

int main() {
    // 待排数据
	vector<int> v;
	v.push_back(6);
	v.push_back(15);
	v.push_back(3);
	v.push_back(422);
	v.push_back(25);

	cout << "排序前：" << endl;
	radix_print(v);

	// 桶排序
	radix_sort(v);

	cout << "桶排序后：" << endl;
	radix_print(v);

	cout << endl;

	system("pause");

	return 0;
}

 


http://www.kler.cn/a/517381.html

相关文章：

  • 【转帖】eclipse-24-09版本后，怎么还原原来版本的搜索功能
  • 虚拟头节点和双指针解决链表问题（合并，与分解操作，力扣题目为例）
  • 7-Zip Mark-of-the-Web绕过漏洞复现(CVE-2025-0411)
  • 第84期 | GPTSecurity周报
  • Leetcode-两数之和
  • 光学设计MTF和艾里斑 像元的关系
  • PADDLE PREDICT
  • Maven修改默认编码格式UTF-8
  • mysql学习笔记-数据库其他调优策略
  • 二分查找 分块查找
  • redis报错如何解决
  • 戴尔电脑设置u盘启动_戴尔电脑设置u盘启动多种方法
  • capter7：全局内存的合理使用
  • C++ 线程安全之互斥锁
  • 《机器学习数学基础》补充资料：超平面
  • 【Unity3D】《跳舞的线》游戏的方块单方向拉伸实现案例
  • 关于hexo-deploy时Spawn-Failed的几种解决方案
  • Mysql面试题----什么是垂直分表、垂直分库、水平分库、水平分表
  • 【华为OD-E卷 - 计算网络信号 100分（python、java、c++、js、c）】
  • 「 机器人 」扑翼飞行器控制方法浅谈
  • Go的垃圾回收(GC)机制
  • 如何在 Spring Boot 中实现自定义属性
  • 计算机视觉算法实战——驾驶员安全带检测
  • 2022年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题8）
  • 深入理解 HTML DOM：文档对象模型详解
  • windows系统改变vscode的插件位置