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

七大排序思想

article 2025/2/8 0:58:54

目录

七大排序的时间复杂度和稳定性

排序

插入排序

简单插入排序

希尔排序

选择排序

简单选择排序

堆排序

交换排序

冒泡排序

快速排序

快排的递归实现 

hoare版本的快排

 挖坑法的快排

双指针法的快排

快排的非递归

归并排序

归并的递归实现

归并的非递归实现

补充

快排的三路划分

七大排序的时间复杂度和稳定性

排序时间的复杂度和稳定性-CSDN博客关于七大排序的时间复杂度和稳定性的总结，帮助读者迅速掌握各各排序的优劣，在不同情况下如何选择。 https://blog.csdn.net/2401_87944878/article/details/145404375

排序

排序就是将一组数据按照递增或递减的方式将其排列。

排序包含两种；

内部排序：数据元素全部放在内存中的排序。

外部排序：数据太多不能同时放在内存中，根据排序的过程不能在内外存之间移动的排序。外部排序要对文件进行操作。

排序包含有四大实现：插入排序，选择排序，交换排序，归并排序。根据这四个实现又可以分支出一共7个排序思想：简单插入排序，希尔排序；选择排序，堆排序；冒泡排序，快速排序；归并排序。下面我们对这七种排序进行讲解。

插入排序

插入排序包含两种：简单插入排序，希尔排序。

简单插入排序

如图，简单插入怕排序就是遍历原数组，将每一个元素放在其指定位置。先拿出一个元素，向前找看，比它大的先后移，直到找到比它小的。

//简单插入排序
void InsertSort(int* a, int n)
{
	//插入排序，向前找到元素的指定位置
	for (int i = 1; i < n; i++)
	{
		int end = i;
		int cur = a[end];
		while(end>0)
		{
			if (a[end - 1] > cur)
			{
				a[end] = a[end - 1];
				end--;
			}
			else
				break;
		}
		a[end] = cur;
	}
}

希尔排序

 希尔排序实际上是对简单插入排序的一种优化。简单插入排序每次与其相邻的元素进行比较，而希尔排序是将一个数组分成多个组，将每个组进行简单插入排序，这样可以让大的数迅速到前面去，小的数迅速到后面去。

可以看到第一次gap是5时，将下标0和5比较，1和6比较，2和7比较....这样可以迅速将大的数移到前面去，将小的数移到后面去，这样就使的数组更加趋于有序的状态。

通过gap从大到小的变化，使得当gap较小的时候可以快速向前找到它的位置，更快的让每次循环break掉，让效率更快。

//希尔排序
void ShellSort(int* a, int n)
{
	//希尔排序与插入排序的区别在于，其先进行预排序
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < gap; i++)
		{
			for (int m = i + gap; m < n; m += gap)
			{
				int end = m;
				int cur = a[end];
				while (end > 0)
				{
					if (a[end - 1] > cur)
					{
						a[end] = a[end - 1];
						end--;
					}
					else
						break;
				}
				a[end] = cur;
			}
		}

	}
}

选择排序

选择排序包含两种简单选择排序和堆排序；

简单选择排序

简单选择排序就是遍历原数组，直接找到最大值或最小值将其放在尾和首，可以一次只找出一个最值，也可以将最大值和最小值同时找到。

以上是遍历未排序的数组每次找出最下的元素交换，下面演示遍历未排序的数组每次找打最小和最大的元素。 

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//简单选择排序
void SelectSort(int* a, int n)
{
	//一次遍历，选出最大值和最小值
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int min = left;
		int max = left;
		for (int i = left; i <= right; i++)
		{
			if (a[min] > a[i])
				min = i;
			if (a[max] < a[i])
				max = i;
		}
		//交换
		Swap(&a[left], &a[min]);
		//注意此处，如果left对应的值就是最大值的时候，
		//将min和left交换后，max就在min的位置了
		if (left == max)
			Swap(&a[right], &a[min]);
		else
			Swap(&a[right], &a[max]);
		left++, right--;
	}
}

堆排序

堆排序就是利用二叉树的性质，通过建大堆或小堆，将最大的数据或最小的数据放在指定位置。在二叉树中已经详细讲过堆了，这里就直接贴代码。

二叉树（C语言）-CSDN博客文章浏览阅读1.3k次，点赞19次，收藏18次。帮助读者快速掌握树这一数据结构，了解堆的功能，能够实现堆排序，以及如何再大量数据中快速找到前K个最大元素，如何处理普通二叉树，普通二叉树的遍历等知识。https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931

//向下调整
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;

	while (child < n)
	{
		if (child+1<n&&a[child] < a[child + 1])
			child++;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}


//堆排序
void HeapSort(int* a, int n)
{
	//先建大堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		//向下调整
		AdjustDown(a, n, i);
	}
	//将堆顶的最大值和堆低交换
	int sz = n - 1;
	Swap(&a[0], &a[sz]);
	sz--;
	while (sz > 0)
	{
		AdjustDown(a, sz + 1, 0);
		Swap(&a[0], &a[sz]);
		sz--;
	}
}

交换排序

交换排序分为冒泡排序和快速排序。

冒泡排序

冒泡排序简单，没有实际作用，这里直接贴代码。

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int m = 0; m < n - 1 - i; m++)
		{
			if (a[m] > a[m + 1])
				Swap(&a[m], &a[m + 1]);
		}
	}
}

快速排序

快速排序是将一个元素key作为基准，先找到这个key的准确位置，将小于key的放在key的左边，将大于key的放在右边。

快排的递归实现 

hoare版本的快排

 如图：将数组首元素作为key，通过左右指针，让R指针先走找到小于key的值停，L指针再走大于key的时候停，将L位置和R位置交换，直到L和R相遇时停止，这个位置就是key排序后的位置。

思考：为什么要让R指针想走？能否让L指针想走？ 

关于key的选择有三种方法：选择最左边的，随机选择，比较数组左右中间这三个值，选出次小的值。此处选择三数取中最好，可以尽量避免只出现一个递归函数。

//快排：Hoare版本
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;

	//快排就是将key放在正确位置上去。
	//三数取中
	int mid = Mid(begin, end);
	Swap(&a[begin], &a[mid]);
	int keyi = begin;
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
			right--;

		while (left < right && a[left] <= a[keyi])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}
 挖坑法的快排

利用挖坑法可以直接不用思考数组那一边的指针先走的问题。

挖坑法就是将keyi的位置值保留，R指针找比key小的将其填在keyi的位置，R指针处变为坑，直到L指针和R指针相遇，将其位置的key填入坑。

//快排：挖坑法
void HoleSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = Mid(begin, end);
	Swap(&a[mid], &a[begin]);

	int hole = begin;
	int left = begin;
	int right = end;
	int key = a[hole];

	while (left < right)
	{
		while (left < right && a[right] >= key)
			right--;
		a[hole] = a[right];
		hole = right;
		
		while (left < right && a[left] <= key)
			left++;
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	int keyi = hole;

	HoleSort(a, 0, keyi - 1);
	HoleSort(a, keyi+1, end);
}
双指针法的快排

分别利用两个指针，一个向前面走如果cur对用的值比key小就交换，两个指针都向前移动；如果cur对应的值大就不交换，cur向前移动。

//快排：双指针法
void DPoint(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = Mid(begin, end);
	Swap(&a[begin], &a[mid]);

	int keyi = begin;
	int cur = begin;
	int pre = begin;
	while (cur <= end)
	{
		if (a[cur] <= a[keyi])
		{
			if (cur != pre)
				Swap(&a[cur], &a[pre]);
			cur++;
			pre++;
		}
		else
		{
			cur++;
		}
	}
	Swap(&a[keyi], &a[pre - 1]);
	keyi = pre - 1;

	DPoint(a, begin, keyi - 1);
	DPoint(a, keyi+1, end);
}

快排的非递归

快排的非递归就是利用栈将其begin和end的值储存起来，再利用栈的“后入先出”的性质，每一次拿出一个范围再放入子范围，直到栈的空间为空时停止。

此处以Hoare的非递归为例。

typedef struct Stack
{
	int* a;
	int size;
	int capacity;
}Stack;

//栈的初始化
void StackInit(Stack* sp)
{
	sp->capacity = 4;
	sp->a = (int*)malloc(sizeof(int) * (sp->capacity));
	if (sp->a == NULL)
		perror("malloc failed");

	sp->size = 0;
}

//入栈
void StackPush(Stack* sp, int x)
{
	//检查空间够不够
	if (sp->size == sp->capacity)
	{
		sp->capacity *= 2;
		int* tmp = (int*)realloc(sp->a, sizeof(int) * (sp->capacity));
		if (tmp == NULL)
			perror("realloc failed");
		sp->a = tmp;
	}
	sp->a[sp->size] = x;
	sp->size++;
}

//出栈
void StackPop(Stack* sp)
{
	sp->size--;
}

//返回栈顶元素
int StackTop(Stack* sp)
{
	return sp->a[sp->size - 1];
}

//检查栈空间是否为空
bool IsStackEmpty(Stack* sp)
{
	if (sp->size == 0)
		return true;
	else
		return false;
}
//快排：非递归
void QuickNon(int* a, int begin, int end)
{
	//快排的非递归就是将快排的左右间距存储在栈中
	Stack s;
	StackInit(&s);
	StackPush(&s, end);
	StackPush(&s, begin);

	while (!IsStackEmpty(&s))
	{
		int begin = StackTop(&s);
		StackPop(&s);
		int end = StackTop(&s);
		StackPop(&s);
		int left = begin;
		int keyi = left;
		int right = end;

		while (left < right)
		{
			while (left < right && a[right] >= a[keyi])
				right--;
			while (left < right && a[left] <= a[keyi])
				left++;

			Swap(&a[left], &a[right]);
		}
		Swap(&a[left], &a[keyi]);
		keyi = left;
		
		if (begin < keyi - 1)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, begin);
		}
		if (keyi + 1 < end)
		{
			StackPush(&s, end);
			StackPush(&s, keyi + 1);
		}
	}
}

归并排序

归并排序的实现就是：先对小范围排序，再对大范围排序。如图：相对两个元素进行排序，再对4个元素进行排序，依次依次*2向后排序。

归并的递归实现

//归并排序
void Merge(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	
	int mid = (begin + end) / 2;
	Merge(a, begin, mid);
	Merge(a, mid + 1, end);

	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
	int j = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[j++] = a[begin1++];
		}
		else
			tmp[j++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[j++] = a[begin1++];
	while (begin2 <= end2)
		tmp[j++] = a[begin2++];

	memcpy(a + begin, tmp, sizeof(int) * (end - begin + 1));
	free(tmp);
}

归并的非递归实现

归并的非递归实现就不能用栈来存储18首尾的范围了，可以直接从2个元素排序开始，依次*2直到排完为止。

//归并的非递归实现
void MergeNon(int* a, int begin, int end)
{
	int gap = 1;
	while (gap < end)
	{
		for (int i = 0; i <= end; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (begin2 > end)
			{
				break;
			}
			if (end2 > end)
				end2 = end;

			int* tmp = (int*)malloc(sizeof(int) * (end2 - begin1 + 1));
			int j = 0;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
			memcpy(a + i, tmp, sizeof(int) * (end2-i+1));
			free(tmp);
		}
		gap *= 2;
	}
}

补充

关于快排，当有大量重复的数据出现的时候，快排的key的位置可能就是最左边，导致向下递归后还是只有一组，当大量出现这种情况的时候就会导致快排变成简单选择排序，时间复杂度大大增加，导致效率降低。此处可以采用三路划分的快排解决。

快排的三路划分

三路划分与普通快排的区别：普通快排将数组分成两个部分，大于key和小于key的；而三路划分将快排分成三个部分，大于key，小于key和等于key的。

分为左右两个指针以及一个遍历数组的指针，将大于key的调到右边，将小于key的调到左边，将等于key的放在中间。

//快排的三路划分
void TQuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = Mid(begin, end);
	Swap(&a[begin], &a[mid]);

	int keyi = begin;
	int key = a[begin];
	int left = begin;
	int cur = begin;
	int right = end;

	while (cur <= right)
	{
		if (a[cur] < key)
		{
			if (cur != left)
				Swap(&a[left], &a[cur]);
			left++, cur++;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
		else
			cur++;
	}
	keyi = left;

	TQuickSort(a, begin, keyi - 1);
	TQuickSort(a, keyi + 1, end);
}


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

相关文章：

  • 【苍穹外卖 Day1】前后端搭建 Swagger导入接口文档
  • 凝思60重置密码
  • 6 加密技术与认证技术
  • WebSocket 实时通信详解：原理、应用与实践
  • 【C++】STL——stack的底层实现
  • 嵌入式工程师必学（143）：模拟信号链基础
  • 深入理解linux中的文件（下）
  • Git登录并解决 CAPTCHA
  • 面向 Workload 级别的灵活可配置 Serverless 弹性解决方案
  • 深入浅出DeepSeek LLM 以长远主义拓展开源语言模型
  • AI对话网站一键生成系统源码
  • Android 约束布局ConstraintLayout整体链式打包居中显示
  • 我们究竟畏惧AI什么？
  • 鸿蒙UI（ArkUI-方舟UI框架）- 使用文本
  • Git仓库托管基本使用02——生成公钥
  • 第八天 继续学习ArkTS，掌握基础语法和组件创建
  • 【蓝桥杯—单片机】第十届省赛真题代码题解题笔记 | 省赛 | 真题 | 代码题 | 刷题 | 笔记
  • React 设计模式：实用指南
  • GPU — 8 卡 GPU 服务器与 NVLink/NVSwitch 互联技术
  • 【AI】DeepSeek来了！！！
  • tolua[一]框架搭建，运行example
  • 【Day33 LeetCode】动态规划DP Ⅵ 背包问题
  • SQL Server的安装和简单使用
  • SQL精度丢失：CAST(ce.fund / 100 AS DECIMAL(10, 2)) 得到 99999999.99
  • 【Uniapp-Vue3】z-paging插件组件实现触底和下拉加载数据
  • 【Elasticsearch】random_sampler聚合