三百行代码实现常用的六大排序算法

• 1.前言
• 2.内容
• 3.总结
• 4.更新日志

2022.5.15 总结整理了之前学的排序算法的实现
语言选择的是C++
（计数排序太水了，没有整理，基数排序自认为学的不太扎实，后续可能会补）
（蒟蒻，轻喷，欢迎指正）

#define _CRT_SECURE_NO_WARNINGS 1

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

void BubbleSort(vector&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 & 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 & 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 & c, int L, int M, int R)   //归并排序的合并过程
{
	//开辟一个额外数组，存储排序后的数组
	vector  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 & 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& b,int n)  //非递归版本(迭代  分而治之)
{
	vector  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 & 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 & 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  part(vector & c, int L, int R)
{
	//设置左右指针
	int l = L - 1;
	int r = R;
	//index从L开始,直至遇到右指针
	int index = L; 
	while (index
		//小于则，左边界扩张，并且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  d(2);
	d[0] = l + 1;
	d[1] = r;
	return d;
}
void QuickSortdg(vector & b, int L, int R)
{
	if (L < R)
	{
		//在L..R上随机选择一个数，作为划分值
		int ret = L + rand() % (R - L + 1);
		swap(b[ret], b[R]);
		//part函数进行分层
		vector  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
	vectora(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完美的一天~~

最重要的是理解它们的思想

2022.5.15 整理上传

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