1. Toy模板网首页
  2. > Toy博客

排序八卦炉之冒泡、快排【完整版】

9月前 作者：阿猿收手吧！ 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了排序八卦炉之冒泡、快排【完整版】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

1.冒泡排序

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

1.1代码实现

//插入排序  O(N)~O(N^2)
//冒泡排序  O(N)~O(N^2)
//当数据有序 二者均为O(N)
//当数据接近有序或局部有序 插排更优
void BubbleSort(int* a, int n)
{
	assert(a);
	int flag = 1;
	for (int i = 0; flag && i < n - 1; ++i)
	{
		flag = 0;
		for (int j = 0; j < n - 1 - i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j + 1], &a[j]);
				flag = 1;
			}
		}
	}
}

1.2复杂度

  1. 最坏：
    比较n-1轮
    每一轮比较次数：n n-1 n-2 n-3 … 1 ≈ N^2
  2. 最优：
    比较n-1轮
    数据有序–每一轮只判断不比较 – N

2.快速排序

2.1人物及思想介绍【源于百度】

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法
排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法
排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.2hoare【霍尔】版本

1.初识代码

//霍尔版本
int PartSort1(int* a, int begin, int end)
{

	int left = begin, right = end, x = left;
	while (left < right)
	{
		//右找小
		while (left < right && a[right] >= a[x])
			--right;

		//左找大
		while (left < right && a[left] <= a[x])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[x], &a[left]);
	x = left;

	return x;
}
void QuickSort(int* a, int begin, int end)    
{
	//begin：左区间左边界下标 
	//end  ：右区间右边界下标
	//begin==end:数据量=1 无需排序 直接返回
	//begin>end :无效区间 无需排序 直接返回
	if (begin >= end)
		return;

	int x = PartSort1(a, begin, end);

	// [begin, x - 1] x [x + 1, end]
	QuickSort(a, begin, x - 1);
	QuickSort(a, x+1, end);
}

2.代码分析

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

3.思其因果

Q：为什么a[x]【作为基准值key】置于左侧 – 右边先移动？
A：目的是为了保证相遇位置的值<=key 从而把key与相遇值交换 不打乱“左放小，右放大”的思想
排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.3挖坑版本

1.初始代码

//挖坑版本
int PartSort2(int* a, int begin, int end)
{
	int x = begin, key = a[begin];

    while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;
		a[x] = a[end];
		x = end;


		while (begin < end && a[begin] <= key)
			++begin;
		a[x] = a[begin];
		x = begin;
	}

	a[x] = key;
	return x;
}
void QuickSort(int* a, int begin, int end)    
{
	//begin：左区间左边界下标 
	//end  ：右区间右边界下标
	//begin==end:数据量=1 无需排序 直接返回
	//begin>end :无效区间 无需排序 直接返回
	if (begin >= end)
		return;

	int x = PartSort1(a, begin, end);

	// [begin, x - 1] x [x + 1, end]
	QuickSort(a, begin, x - 1);
	QuickSort(a, x+1, end);
}

2.代码分析

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

3.思想比较

霍尔版本：右找小 左找打 大小交换 依次递归
挖坑版本：记录key值 x位–置空 右找小入坑 坑位更新 左找大入坑 坑位更新 依次递归

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.4指针版本

1.初识代码

int PartSort3(int* a, int begin, int end)
{   //prv：previous  cp：current pointer
	
	int prv = begin, cp = begin + 1, x = begin;

	while (cp <= end)
	{
		if (a[cp] < a[x] && ++prv != cp)
			Swap(&a[prv], &a[cp]);

		++cp;
	}
	Swap(&a[prv], &a[x]);
	x = prv;
	
	return x;
}
void QuickSort(int* a, int begin, int end)    
{
	//begin：左区间左边界下标 
	//end  ：右区间右边界下标
	//begin==end:数据量=1 无需排序 直接返回
	//begin>end :无效区间 无需排序 直接返回
	if (begin >= end)
		return;

	int x = PartSort3(a, begin, end);

	// [begin, x - 1] x [x + 1, end]
	QuickSort(a, begin, x - 1);
	QuickSort(a, x+1, end);
}

2.代码分析

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

3.问题探讨

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.5集体优化

//快速排序   O(N * logN)
//对任意区间三值取中位数
int GetMid_X(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] < a[end])
			return end;
		else
			return begin;
	}
	else //a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
//霍尔版本
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end, x = left;

	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);

	while (left < right)
	{
		//右找小
		while (left < right && a[right] >= a[x])
			--right;

		//左找大
		while (left < right && a[left] <= a[x])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[x], &a[left]);
	x = left;

	return x;
}
//挖坑版本
int PartSort2(int* a, int begin, int end)
{
	int x = begin;
	
	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]); 
	int key = a[x];
    
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;
		a[x] = a[end];
		x = end;


		while (begin < end && a[begin] <= key)
			++begin;
		a[x] = a[begin];
		x = begin;
	}

	a[x] = key;
	return x;
}  
//指针版本
int PartSort3(int* a, int begin, int end)
{   //prv：previous  cp：current pointer
	
	int prv = begin, cp = begin + 1, x = begin;
	
	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);

	while (cp <= end)
	{
		if (a[cp] < a[x] && ++prv != cp)
			Swap(&a[prv], &a[cp]);

		++cp;
	}
	Swap(&a[prv], &a[x]);
	x = prv;
	
	return x;
}
void QuickSort(int* a, int begin, int end)    
{
	//begin：左区间左边界下标 
	//end  ：右区间右边界下标
	//begin==end:数据量=1 无需排序 直接返回
	//begin>end :无效区间 无需排序 直接返回
	if (begin >= end)
		return;

	int x = PartSort2(a, begin, end);

	// [begin, x - 1] x [x + 1, end]
	QuickSort(a, begin, x - 1);
	QuickSort(a, x+1, end);
}

2.6极致优化

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.7非递归版本

递归版本存在的问题：若递归层次太深 导致栈溢出问题
递归改非递归的方法：

  1. 直接改循环 – 斐波那契数列、归并排序等
  2. 数据结构的栈（Stack）模拟递归【Stack的空间是从堆申请的 堆内存比栈内存大】

1.初识代码

int PartSort3(int* a, int begin, int end)
{   //prv：previous  cp：current pointer
	int prv = begin, cp = begin + 1, x = begin;
	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);
	while (cp <= end)
	{
		if (a[cp] < a[x] && ++prv != cp)
			Swap(&a[prv], &a[cp]);
		++cp;
	}
	Swap(&a[prv], &a[x]);
	x = prv;
	return x;
}
void QuickSort_NonRecursion(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);

	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int x = PartSort3(a, left, right);
		 
		if (x + 1 < right)
		{
			StackPush(&st, x + 1);
			StackPush(&st, right);
		}
		// [left, x-1] x [x+1, right]
		if (left < x - 1)
		{
			StackPush(&st, left);
			StackPush(&st, x - 1);
		}
	}
	StackDestroy(&st);
}

2.代码分析

排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法
排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法
排序八卦炉之冒泡、快排【完整版】,深度学习数据结构,c语言,数据结构,排序算法,算法

2.8相关博客及完整代码

点击 [qsort与bubble之间不为人知的关系](htt p://t.csdn.cn/filuW) 查看博主之前关于分析这两个排序的博客。文章来源地址https://www.toymoban.com/news/detail-625588.html

//快速排序   O(N * logN)
int count = 0;  //测试递归次数
//对任意区间三值取中位数
int GetMid_X(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] < a[end])
			return end;
		else
			return begin;
	}
	else //a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
//霍尔版本
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end, x = left;

	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);

	while (left < right)
	{
		//右找小
		while (left < right && a[right] >= a[x])
			--right;

		//左找大
		while (left < right && a[left] <= a[x])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[x], &a[left]);
	x = left;

	return x;
}
//挖坑版本
int PartSort2(int* a, int begin, int end)
{
	int x = begin;
	
	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]); 
	int key = a[x];
    
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;
		a[x] = a[end];
		x = end;


		while (begin < end && a[begin] <= key)
			++begin;
		a[x] = a[begin];
		x = begin;
	}

	a[x] = key;
	return x;
}  
//指针版本
int PartSort3(int* a, int begin, int end)
{   //prv：previous  cp：current pointer
	int prv = begin, cp = begin + 1, x = begin;
	//确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);
	while (cp <= end)
	{
		if (a[cp] < a[x] && ++prv != cp)
			Swap(&a[prv], &a[cp]);
		++cp;
	}
	Swap(&a[prv], &a[x]);
	x = prv;
	return x;
}

void QuickSort(int* a, int begin, int end)
{
	count++;
	//begin：左区间左边界下标 
	//end  ：右区间右边界下标
	//begin==end:数据量=1 无需排序 直接返回
	//begin>end :无效区间 无需排序 直接返回
	if (begin >= end)
		return;

	int x = PartSort3(a, begin, end);

	// [begin, x - 1] x [x + 1, end]
	QuickSort(a, begin, x - 1);
	QuickSort(a, x+1, end);
}

/*
void QuickSort(int* a, int begin, int end)
{
	count++;
	if (begin >= end)
		return;
	
	if (end - begin > 10)
	{
		int x = PartSort3(a, begin, end);
		
		// [begin, x-1] x [x+1, end]
		QuickSort(a, begin, x - 1);
		QuickSort(a, x + 1, end);
	}
	else 
		InsertSort(a + begin, end - begin + 1);
}
*/
//非递归版本
void QuickSort_NonRecursion(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);

	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);

		int x = PartSort3(a, begin, end);
		 
		if (x + 1 < end)
		{
			StackPush(&st, x + 1);
			StackPush(&st, end);
		}
		// [begin, x-1] x [x+1, end]
		if (begin < x - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, x - 1);
		}
	}
	StackDestroy(&st);
}

到了这里，关于排序八卦炉之冒泡、快排【完整版】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 排序 | 冒泡插入希尔选择堆快排归并计数排序

    排序 | 冒泡插入希尔选择堆快排归并计数排序

    排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。 接下来我们就要实现排序~~ 我们需要实现的一些功能： 冒泡排序是一种基本的排序算法，其核心思想是通过多次交换相邻元素的位置，使得每一轮循环都将

    2024年02月04日
    浏览(49)
  • 排序 | 冒泡 插入 希尔 选择 堆 快排 归并 非递归 计数 基数 排序

    排序 | 冒泡 插入 希尔 选择 堆 快排 归并 非递归 计数 基数 排序

    排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。 接下来我们就要实现排序~~ 我们需要实现的一些功能： 冒泡排序是一种基本的排序算法，其核心思想是通过多次交换相邻元素的位置，使得每一轮循环都将

    2024年02月04日
    浏览(54)
  • 【C语言】冒泡排序的快排模拟

    【C语言】冒泡排序的快排模拟

    说到排序，必然绕不开两个排序， 冒泡排序 与 快速排序 冒泡排序是大多数人的启蒙排序，因为他的 算法简单。但效率不高 ，便于新手理解； 而快速排序是集大成之作， 效率最高 ，使用最为广泛。 今天这篇文章带来如何使用 qsort （quick sort，快速排序），和如何使用冒泡

    2024年02月09日
    浏览(33)
  • 数据结构与算法-选择&冒泡&快排&计数

    数据结构与算法-选择&冒泡&快排&计数

        一：选择排序     场景：找出一个班上身高最高的人你会怎么找？A B C D A B 选择排序的思路和插入排序非常相似，也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。但是不像插入排序会移动数组 选择排序会每次

    2024年02月09日
    浏览(43)
  • 十大排序算法（冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序）

    十大排序算法（冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序）

    目录 一、冒泡排序： 二、插入排序： 三、选择排序： 四、希尔排序： 五、堆排序： 六、快速排序： 6.1挖坑法： 6.2左右指针法 6.3前后指针法： 七、归并排序： 八、桶排序： 九、计数排序： 9.1绝对映射： 9.2现对映射： 十、基数排序：  1、思路： 通过对待排序序列从前

    2024年03月11日
    浏览(56)
  • 【基础算法】八大排序算法：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序(快排)，归并排序，计数排序

    【基础算法】八大排序算法：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序(快排)，归并排序，计数排序

      🧑‍🎓 个人主页：简 料   🏆 所属专栏：C++   🏆 个人社区：越努力越幸运社区   🏆 简       介： 简料简料，简单有料~在校大学生一枚，专注C/C++/GO的干货分享，立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年02月01日
    浏览(47)

  • 深度学习的历史与八卦

    有这么一个说法，每多一个数学公式，读者就减少一半。深度学习想来也无法免俗，毕竟技术文章不免艰涩，而要完全绕过公式讲好深度学习与大模型，以臣妾微薄的实力实在是做不到啊。 因此，本文先歪歪楼，讲讲深度学习与大模型的历史与八卦，一方面是让大家稍微了解

    2024年02月10日
    浏览(39)
  • 【数据结构与算法】排序算法：冒泡排序，冒泡排序优化，选择排序、选择排序优化

    【数据结构与算法】排序算法：冒泡排序，冒泡排序优化，选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现： 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现： 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大（或最小）的元素移到右边（或左边

    2024年01月19日
    浏览(50)
  • 数据结构——排序之冒泡排序

    数据结构——排序之冒泡排序

    hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页：大耳朵土土垚的博客 💥 所属专栏：数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写

    2024年04月12日
    浏览(34)
  • 【数据结构】排序(2)—冒泡排序 & 快速排序

    【数据结构】排序(2)—冒泡排序 & 快速排序

                                      目录 一. 冒泡排序 基本思想 代码实现 时间和空间复杂度 稳定性 二. 快速排序 基本思想 代码实现 hoare法 挖坑法 前后指针法 时间和空间复杂度 稳定性            冒泡排序是一种交换排序。两两比较数组元素，如果是逆序(即排列顺序

    2024年02月08日
    浏览(80)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包