投稿
  1. 首页
  2. C

八大排序算法（C++实现）

code • 2022-5-16 • C • 阅读 26

八大排序算法（C++实现）,第1张

九大class="superseo">排序算法
  • 1.前言
  • 2.内容
    • 1. 5.15
    • 2. 5.16
  • 3.总结
  • 4.更新日志

1.前言

总结整理了之前学的排序算法的实现
语言：C++
（计数排序太水了，没有整理，基数排序自认为学的不太扎实，后续可能会补）
在后续又补上了 计数排序 与 基数排序，23333…

包含如下：
时间复杂度为0（N2）： 冒泡排序、选择排序、插入排序
0（NlogN）：归并排序、快速排序、堆排序
0（N）： 基数排序
以及打酱油的*： 计数排序
单击链接查看排序算法详解

（蒟蒻，轻喷，欢迎指正）

2.内容 1. 5.15 
#define _CRT_SECURE_NO_WARNINGS 1

#include 
using namespace std;
#include 
#include 
#include   //随机初始化
#include  

void BubbleSort(vector<int>&b, int n)    //用&来修改数组 //从小到大排序
{
	1.从前向后冒泡
	//for (int i = 0; i < n - 1; i++)  //趟数n-1
	//{
	//	for (int j = 0; j < n - i - 1; j++)
	//		if (b[j] > b[j + 1])
	//			swap(b[j], b[j + 1]);
	//}

	2.将i条件倒序，更易理解
	//for (int i = n - 1; i > 0; i--)
	//{
	//	for (int j = 0; j < i; j++)
	//		if (b[j] > b[j + 1])
	//			swap(b[j], b[j + 1]);
	//}


	从后向前呢  //不可！！
	//for (int i = 0; i < n - 1; i++)
	//{
	//	for (int j = n-i-1; j > 0; j--)
	//	{
	//		if (b[j-1] > b[j])
	//			swap(b[j-1], b[j]);
	//	}
	//}
}

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

void InsertSort(vector <int>& b, int n)   //将待插入的元素插入已排好序的序列中，其余元素后移
{
	//小细节：先判断j>0,否则b[j-1]越界访问！！

	1.先找到合适的插入位置，再插入
	//for (int i = 1; i < n; i++)  //待插入元素下标
	//{
	//	int temp = b[i];
	//	int j = i;
	//	while (j > 0 && temp < b[j-1])  //不越界，并且符合后移条件
	//	{
	//		b[j] = b[j-1];  //后移
	//		j--;
	//	}
	//	b[j] = temp; //插入
	//}

	1.1改成for循环
	//for (int i = 1; i < n; i++)
	//{
	//	int temp = b[i];
	//	int j = i;
	//	for (j = i;j > 0&&b[j - 1] > temp; j--)
	//		b[j] = b[j - 1];
	//	b[j] = temp;    
	//}

	2.边插入边遍历
	//for (int i = 1; i < n; i++)
	//{
	//	int j = i;
	//	while (j > 0 && b[j] < b[j - 1])
	//	{
	//		swap(b[j], b[j - 1]);
	//		j--;
	//	}
	//}
	2.1改成for循环   //简洁
	//for (int i = 1; i < n; i++)
	//{
	//	for (int j = i; j > 0 && b[j - 1] > b[j];j--)
	//		swap(b[j - 1], b[j]);
	//}
}

void Partition(vector <int>& c, int L, int M, int R)   //归并排序的合并过程
{
	//开辟一个额外数组，存储排序后的数组
	vector <int> ex(R - L + 1);   
	//左右指针
	int l = L;     
	int r = M + 1;
	int k = 0;    //额外数组
	//进行比较，并放入额外数组中
	while (l <= M && r <= R)   //左右指针不越界
	{
		ex[k++] = c[l] <= c[r] ? c[l++] : c[r++];    //先拷贝小的(若相等，先拷贝左边的)
	}
	//拷贝剩下的元素
	while (l <= M)
	{
		ex[k++] = c[l++];
	}
	while (r <= R)
	{
		ex[k++] = c[r++];
	}
	//重新放进原数组中
	int i = 0;
	for (const auto& e : ex)
		c[L + i++] = e;
}
void Guibingdg(vector <int>& b, int L, int R)  //递归版本
{
	if (L >= R)
		return;
	else
	{
		int M = L + ((R-L) >> 1);   //中间位置
		Guibingdg(b, L, M);   //左有序
		Guibingdg(b, M + 1, R); //右有序
		Partition(b, L, M, R);   //合并
	}
}

void Guibingfdg(vector<int>& b,int n)  //非递归版本(迭代  分而治之)
{
	vector <int> c(n);    //申请额外空间
	
	for (int segment = 1; segment < n; segment *= 2)   //划分部分表示每一步的步长（注意不要多加;）
	{
		for (int begin = 0; begin < n; begin +=segment* 2)
		{
			int L = begin, M = min(begin + segment, n), R = min(begin + segment * 2, n);   //定义L  M  R，划分范围
			int k = L;
			int p1 = L, end1 = M;
			int p2 = M, end2 = R;
			while (p1 < end1 && p2 < end2)   //不越界  (不加等号是因为后面的分治会考虑进去)
			{                                //同时符合最后一步 ==len时
				c[k++] = b[p1] < b[p2] ? b[p1++] : b[p2++];   //将小的先拷贝
			}
			//拷贝剩余元素
			while (p1 < end1)
				c[k++] = b[p1++];
			while (p2 < end2)
				c[k++] = b[p2++];
		}
		//将排序好的c中元素重新拷贝回b中
		for (int i = 0; i < n; i++)
			b[i] = c[i];
	}
}

void heapify(vector <int>& c, int i, int heapsize)
{
	int left = 2 * i + 1;
	while (left < heapsize)
	{
		//找到左右孩子中最大的
		int largest = left + 1 < heapsize && c[left + 1] > c[left] ? left + 1 : left;
		//再与父亲比较
		largest = c[i] > c[largest] ? i : largest;
		//如果父节点已经最大，则不用下沉
		if (largest == i)
			break;
		//否则，先下沉，再继续
		swap(c[largest], c[i]);
		i = largest;
		left = 2 * i + 1;
	}
}
void Duipai(vector <int>& b, int n)
{
	//if (n < 1)
	//	return;
	if (n >= 1)
	{
		//令数组变为大根堆
		for (int i = n - 1; i >= 0; i--)
			heapify(b, i, n);
		int heapsize = n;
		//交换之后，尾节点为最大值
		swap(b[0], b[--heapsize]);
		//重复此过程
		while (heapsize > 0)
		{
			//前面已经保证整个数组为大根堆，之后只需保证0~heapisize为大根堆即可
			heapify(b, 0, heapsize);

			swap(b[0], b[--heapsize]);
		}
	}
}

vector <int> part(vector <int>& c, int L, int R)
{
	//设置左右指针
	int l = L - 1;
	int r = R;
	//index从L开始,直至遇到右指针
	int index = L; 
	while (index<r)
	{
		//小于则，左边界扩张，并且index后移
		if (c[index] < c[R])
			swap(c[++l], c[index++]);
		//大于则，右边界扩张，但index不后移，因为不确定交换过去的数字与c[R]的关系，需要在下一次的循环中判断
		else if (c[index] > c[R])
			swap(c[--r], c[index]);
		//相等则，先跳过
		else
			index++;
	}
	//将大于区的第一个和c[R]交换
	swap(c[r], c[R]);
	//将==区域的左边界和右边界传回去
	vector <int> d(2);
	d[0] = l + 1;
	d[1] = r;
	return d;
}
void QuickSortdg(vector <int>& b, int L, int R)
{
	if (L < R)
	{
		//在L..R上随机选择一个数，作为划分值
		int ret = L + rand() % (R - L + 1);
		swap(b[ret], b[R]);
		//part函数进行分层
		vector <int> d = part(b, L, R);
		//利用传回来的边界，继续递归(==区域的数字不用再排序了)
		QuickSortdg(b, L, d[0] - 1);   // < 区域
		QuickSortdg(b, d[1] + 1, R);   // > 区域
	}
}

int main()
{
	srand((unsigned int)time(0));
	int n;
	n=rand()%10+5; //数组大小在 5~14
	vector<int>a(n);    //创建动态数组对象a
	for (int i = 0; i < n; i++)
		a[i] = rand()%10000-5000;       //随机-5000~4999
	for (const auto& e : a)   //排序前先输出，做对比
		cout << e << " ";
	cout << endl;
//	BubbleSort(a, n);  
//	SelectSort(a, n);
//	InsertSort(a, n);
//	Guibingdg(a, 0, n - 1);   //递归版本的归并排序
//	Guibingfdg(a, n);        //迭代版本的
//	Duipai(a,n);
//	QuickSortdg(a, 0, n - 1);
//	QuickSortfdg();
	for (const auto& e : a)   //范围for语句，遍历输出
		cout << e << " ";
	return 0;
}
//5.15完美的一天~~
2. 5.16 
#include 
using namespace std;
#include 
#include 
#include   //随机初始化
#include  
const int RADIX = 10;   //十进制（基数排序用）

void BubbleSort(vector<int>&b, int n)    //用&来修改数组 //从小到大排序
{
	1.从前向后冒泡
	//for (int i = 0; i < n - 1; i++)  //趟数n-1
	//{
	//	for (int j = 0; j < n - i - 1; j++)
	//		if (b[j] > b[j + 1])
	//			swap(b[j], b[j + 1]);
	//}

	2.将i条件倒序，更易理解
	//for (int i = n - 1; i > 0; i--)
	//{
	//	for (int j = 0; j < i; j++)
	//		if (b[j] > b[j + 1])
	//			swap(b[j], b[j + 1]);
	//}


	从后向前呢  //不可！！
	//for (int i = 0; i < n - 1; i++)
	//{
	//	for (int j = n-i-1; j > 0; j--)
	//	{
	//		if (b[j-1] > b[j])
	//			swap(b[j-1], b[j]);
	//	}
	//}
}

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

void InsertSort(vector <int>& b, int n)   //将待插入的元素插入已排好序的序列中，其余元素后移
{
	//小细节：先判断j>0,否则b[j-1]越界访问！！

	1.先找到合适的插入位置，再插入
	//for (int i = 1; i < n; i++)  //待插入元素下标
	//{
	//	int temp = b[i];
	//	int j = i;
	//	while (j > 0 && temp < b[j-1])  //不越界，并且符合后移条件
	//	{
	//		b[j] = b[j-1];  //后移
	//		j--;
	//	}
	//	b[j] = temp; //插入
	//}

	1.1改成for循环
	//for (int i = 1; i < n; i++)
	//{
	//	int temp = b[i];
	//	int j = i;
	//	for (j = i;j > 0&&b[j - 1] > temp; j--)
	//		b[j] = b[j - 1];
	//	b[j] = temp;    
	//}

	2.边插入边遍历
	//for (int i = 1; i < n; i++)
	//{
	//	int j = i;
	//	while (j > 0 && b[j] < b[j - 1])
	//	{
	//		swap(b[j], b[j - 1]);
	//		j--;
	//	}
	//}
	2.1改成for循环   //简洁
	//for (int i = 1; i < n; i++)
	//{
	//	for (int j = i; j > 0 && b[j - 1] > b[j];j--)
	//		swap(b[j - 1], b[j]);
	//}
}

void Partition(vector <int>& c, int L, int M, int R)   //归并排序的合并过程
{
	//开辟一个额外数组，存储排序后的数组
	vector <int> ex(R - L + 1);   
	//左右指针
	int l = L;     
	int r = M + 1;
	int k = 0;    //额外数组
	//进行比较，并放入额外数组中
	while (l <= M && r <= R)   //左右指针不越界
	{
		ex[k++] = c[l] <= c[r] ? c[l++] : c[r++];    //先拷贝小的(若相等，先拷贝左边的)
	}
	//拷贝剩下的元素
	while (l <= M)
	{
		ex[k++] = c[l++];
	}
	while (r <= R)
	{
		ex[k++] = c[r++];
	}
	//重新放进原数组中
	int i = 0;
	for (const auto& e : ex)
		c[L + i++] = e;
}
void Guibingdg(vector <int>& b, int L, int R)  //递归版本
{
	if (L >= R)
		return;
	else
	{
		int M = L + ((R-L) >> 1);   //中间位置
		Guibingdg(b, L, M);   //左有序
		Guibingdg(b, M + 1, R); //右有序
		Partition(b, L, M, R);   //合并
	}
}

void Guibingfdg(vector<int>& b,int n)  //非递归版本(迭代  分而治之)
{
	vector <int> c(n);    //申请额外空间
	
	for (int segment = 1; segment < n; segment *= 2)   //划分部分表示每一步的步长（注意不要多加;）
	{
		for (int begin = 0; begin < n; begin +=segment* 2)
		{
			int L = begin, M = min(begin + segment, n), R = min(begin + segment * 2, n);   //定义L  M  R，划分范围
			int k = L;
			int p1 = L, end1 = M;
			int p2 = M, end2 = R;
			while (p1 < end1 && p2 < end2)   //不越界  (不加等号是因为后面的分治会考虑进去)
			{                                //同时符合最后一步 ==len时
				c[k++] = b[p1] < b[p2] ? b[p1++] : b[p2++];   //将小的先拷贝
			}
			//拷贝剩余元素
			while (p1 < end1)
				c[k++] = b[p1++];
			while (p2 < end2)
				c[k++] = b[p2++];
		}
		//将排序好的c中元素重新拷贝回b中
		for (int i = 0; i < n; i++)
			b[i] = c[i];
	}
}

void heapify(vector <int>& c, int i, int heapsize)
{
	int left = 2 * i + 1;
	while (left < heapsize)
	{
		//找到左右孩子中最大的
		int largest = left + 1 < heapsize && c[left + 1] > c[left] ? left + 1 : left;
		//再与父亲比较
		largest = c[i] > c[largest] ? i : largest;
		//如果父节点已经最大，则不用下沉
		if (largest == i)
			break;
		//否则，先下沉，再继续
		swap(c[largest], c[i]);
		i = largest;
		left = 2 * i + 1;
	}
}
void Duipai(vector <int>& b, int n)
{
	//if (n < 1)
	//	return;
	if (n >= 1)
	{
		//令数组变为大根堆
		for (int i = n - 1; i >= 0; i--)
			heapify(b, i, n);
		int heapsize = n;
		//交换之后，尾节点为最大值
		swap(b[0], b[--heapsize]);
		//重复此过程
		while (heapsize > 0)
		{
			//前面已经保证整个数组为大根堆，之后只需保证0~heapisize为大根堆即可
			heapify(b, 0, heapsize);

			swap(b[0], b[--heapsize]);
		}
	}
}

vector <int> part(vector <int>& c, int L, int R)
{
	//设置左右指针
	int l = L - 1;
	int r = R;
	//index从L开始,直至遇到右指针
	int index = L; 
	while (index<r)
	{
		//小于则，左边界扩张，并且index后移
		if (c[index] < c[R])
			swap(c[++l], c[index++]);
		//大于则，右边界扩张，但index不后移，因为不确定交换过去的数字与c[R]的关系，需要在下一次的循环中判断
		else if (c[index] > c[R])
			swap(c[--r], c[index]);
		//相等则，先跳过
		else
			index++;
	}
	//将大于区的第一个和c[R]交换
	swap(c[r], c[R]);
	//将==区域的左边界和右边界传回去
	vector <int> d(2);
	d[0] = l + 1;
	d[1] = r;
	return d;
}
void QuickSortdg(vector <int>& b, int L, int R)
{
	if (L < R)
	{
		//在L..R上随机选择一个数，作为划分值
		int ret = L + rand() % (R - L + 1);
		swap(b[ret], b[R]);
		//part函数进行分层
		vector <int> d = part(b, L, R);
		//利用传回来的边界，继续递归(==区域的数字不用再排序了)
		QuickSortdg(b, L, d[0] - 1);   // < 区域
		QuickSortdg(b, d[1] + 1, R);   // > 区域
	}
}

int Maxdigits(const vector <int>&b, int n)   //求出a数组中最多有多少位
{
	int MAX = 0;
	for (int i = 0; i < n; i++)
		if (b[i] > MAX)
			MAX = b[i];
	int dig = 0;
	while (MAX)
	{
		MAX /= 10;
		dig++;
	}
	return dig;
}
int dig(int x,int s)     //拿到指定位上的数字
{
	return x / int(pow(10, s)) % 10;
}
void BaseSort(vector <int>& c, int L, int R,int bits)  //基数排序
{
	//存放每次根据某一位排序后的数字
	vector <int> bucket(R - L + 1); 
	//分别根据 个、十、百、....位进行排序
	for (int d = 0; d < bits; d++)
	{
		//存放某一位上数字的个数
		vector <int> cnt(RADIX);
		//计数
		for (int i = L; i <= R; i++)
		{
			//找到某一位上的数字(0~9)
			int j = dig(c[i], d);
			cnt[j]++;
		}
		//累加（为了后面在出桶时，保持后进先出的顺序）
		for (int i = 1; i < RADIX; i++)
			cnt[i] += cnt[i - 1];
		//进桶
		for (int i = R; i >= L; i--)
		{
			int j = dig(c[i], d);
			//某一位上计数的数字减一即为c[i]应存放的位置
			bucket[--cnt[j]] = c[i];
		}
		//出桶
		for (int i = L; i <= R; i++)
			c[i] = bucket[i];
	}
}

void CountSort(vector <int>& b, int n)      //计数排序
{
	//找出最大的数字
	int MAX = 0;
	for (int i = 0; i < n; i++)
		MAX = max(MAX, b[i]);
	//创建一个比最大数字还大1的数组
	vector <int>c(MAX + 1);
	//依次遍历 计数
	for (int i = 0; i < n; i++)
	{
		c[b[i]]++;
	}
	//输出
	for (int i=0;i<MAX+1;i++)
		if (c[i])
			cout <<i<< " ";
}

int main()
{
	srand((unsigned int)time(0));
	int n;
	n=rand()%10+5; //数组大小在 5~14
	vector<int>a(n);    //创建动态数组对象a
	for (int i = 0; i < n; i++)
//		a[i] = rand()%10000-5000;       //随机-5000~4999
		a[i] = rand() % 10000 + 1;      //计数排序用下面这个
	for (const auto& e : a)   //排序前先输出，做对比
		cout << e << " ";
	cout << endl;

//	BubbleSort(a, n);  
//	SelectSort(a, n);
//	InsertSort(a, n);
//	Guibingdg(a, 0, n - 1);   //递归版本的归并排序
//	Guibingfdg(a, n);        //迭代版本的
//	Duipai(a,n);
//	QuickSortdg(a, 0, n - 1);
//	QuickSortfdg();
//	BaseSort(a, 0, n - 1, Maxdigits(a, n));   //基数排序（针对十进制正数）[利用桶排序的思想]
	
	//for (const auto& e : a)   //范围for语句，遍历输出 [上面的排序需用到]
	//	cout << e << " ";

//	CountSort(a, n);      //计数排序（暴力遍历计数，单独写）

	return 0;
}
//完美的n天~~
3.总结

感谢耐心看到最后，噶油~
*最重要的是理解它们的思想 *

4.更新日志

2022.5.15 整理上传
2022.5.16 补充计数排序、基数排序

欢迎催更~
欢迎评论留言、指正~~

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/920969.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表（0条）

保存