[C语言]排序的大乱炖——喵喵的成长记

这篇具有很好参考价值的文章主要介绍了[C语言]排序的大乱炖——喵喵的成长记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

宝子,你不点个赞吗?不评个论吗?不收个藏吗?

最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!!

喵喵喵,你对我真的很重要。


前言

小喵喵课堂开课来,今天我们学习七个常见的排序,哦哦耶!!!

喵喵今天也要加油哦!

来吧,不乱叫,上导图:

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

目录

前言

八大经典排序的概述

直接插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序(快排)

归并排序

总结


┗|`O′|┛ 嗷~~,怎么能忘了基数排序呢?补上补上:

八大经典排序的概述

八大排序算法是指常见的八种经典排序算法,它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。

  1. 冒泡排序:比较相邻的元素,如果顺序错误就交换它们,重复这个过程直到整个数组有序。
  2. 选择排序:每次从待排序的数组中选择最小(或最大)的元素放在已排序数组的末尾,直到整个数组有序。
  3. 插入排序:遍历数组,将当前元素插入已排好序的子数组中的适当位置,直到整个数组有序。
  4. 希尔排序:通过设置间隔将数组分组,对每个分组进行插入排序,逐渐减小间隔,直到间隔为1时进行最后一次插入排序。
  5. 归并排序:采用分治的思想,将待排序数组划分为较小的子数组,然后递归地对子数组进行排序,并将排好序的子数组合并成更大的有序数组。
  6. 快速排序:选取一个基准元素,将数组划分为左右两部分,左边部分都比基准元素小,右边部分都比基准元素大,在递归地对左右两部分进行快速排序。
  7. 堆排序:将待排序数组构建成一个大顶堆,然后将堆顶元素与最后一个元素交换并重新调整堆,重复这个过程直到整个数组有序。
  8. 基数排序:根据元素的每个位上的值进行排序,先按低位排序,再按高位排序,直到所有位都排序完成。

直接插入排序

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

直接插入的排序规则,如图所示:

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

将end和tmp代入进去思考,一来的3,就算起始点,排好了位置,作为end,然后tmp是44,44>3,tmp>end,所以不交换位置,算排好了,end+1,tmp+1。那么第二次比较,end是44,tmp是38,end>tmp,交换位置,38排在44前面。那么第三次比较,5比44小,比38小,排在38前面。以此类推,循环排好数组。

void InSert(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

希尔排序

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

希尔排序是直接插入排序的升级版,先对数组进行有规律的分组,分成多个组,然后每个小组进行直接插入排序。每个小组排完后,再进行一次直接插入排序,就要轻松地多,能够快速排好,大大提高了排序的效率。

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

分成绿,蓝,红三组,分别进行直接插入排序。

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

void InsertSort(int* a, int n) 
{
	int gap = 3;
	for (j=0;j<gap;j++)
	{
		for (int i = j; i < n-gap; i+=gap)
		{
			int end = i;
			int tmp = a[i+gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
	

}
void InsertSort(int* a, int n) 
{
	int gap = n;

	int j = 0;
	while (gap > 1)
	{
		gap = gap / 2;
		for (j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[i + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}

}

选择排序

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

选择排序,很直观就是要选择,我们先选择3作为有序数组,然后从3后面的数组中选出最小的数,并于3进行比较,谁小谁站在前面。2比3小,2与3交换位置。依次往后推,拍成有序数组。

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

喵,很难评,这是简单版的一个点移动,而我们一般上的是困难版的两个点,喵,不好理解,喵喵,也是搞了好久,才明白滴,喵。那么让我们开始吧!猫猫队,冲冲冲!

两个点的移动(建议结合代码,自己也跟着走一走,感觉不就来了嘛!):

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

//这是两个点的移动
void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[left], &a[mini]);
		// 如果left和maxi重叠,交换后修正一下
		if (left == maxi)
		{
			maxi = mini;
		}

		Swap(&a[right], &a[maxi]);

		++left;
		--right;
	}
}

堆排序

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

就是以层序的方式从下往上,从大到小的排。升序建大堆,降序建小堆。

// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

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

void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建堆 -- O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// 自己先实现 -- O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);

		--end;
	}
}

冒泡排序

冒泡排序,好理解,教学意义重大。简单的来说就是从一端开始,两两交换,把小的换在前面去就OK了!

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}

		if (exchange == false)
		{
			break;
		}
	}
}

快速排序(快排)

快排有很多种方法,比如hoare法,挖坑法,前后指针法:

1.hoare法:

无言,如图所示

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort1(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;
	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;

	return keyi;
}

挖坑法:

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	// 21:10继续
	int key = a[left];
	int hole = left;
	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;

	return hole;
}

前后指针法:

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}

归并排序(递归):

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

总结

疯了,疯了,怎么才能讲清楚啊,白话文一大堆,还是图来说清楚,没看清楚的啾咪,留言喵喵鸭,你的明白,就是我的成长,酸Q喵。


宝子,你不点个赞吗?不评个论吗?不收个藏吗?

最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!!

喵喵喵,你对我真的很重要。

[C语言]排序的大乱炖——喵喵的成长记,喵霸成长记之数据结构篇,【C语言】小猫猫大课堂,排序算法,数据结构,算法,c语言文章来源地址https://www.toymoban.com/news/detail-718054.html

到了这里,关于[C语言]排序的大乱炖——喵喵的成长记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • C语言王国探险记之函数的简单概念

    目录 王国探险记系列 文章目录(5) 前言 一,函数的基本概念 二,调用外部函数和main()函数区别 2.1如果我们将函数的定义放到后面,可不可以呢? 总结 C语言王国探险记,是我们学习C语言,从小白成长为大佬的的探险历程,我们在这章将初步探索函数这两个知识关卡 我们

    2024年02月12日
    浏览(46)
  • 数据结构——C语言实现常见排序(插入排序、希尔排序、选择排序、堆排序、冒泡排序)

    现在是北京时间2023年6月23日13点19分,度过了一个非常愉快的端午节。由于刚从学校回家,一下子伙食强度直升了个两三个档次。这也导致我的肠胃不堪重负,我也准备等会去健身房消耗一下盈余的热量。回到家陪伴爷爷走人生最后的阶段才是我这个暑假最重要的事情。自从

    2024年02月10日
    浏览(53)
  • 【C语言】数据结构——排序三(归并与计数排序)

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了排序,包括直接插入排序,希尔排序,选择排序,堆排序,冒泡排序和快排。 今天我们来讲一讲归并排序和计数排序。 关注博主或是订阅专栏,掌握第一消息。 归并排序的

    2024年01月19日
    浏览(59)
  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时,都是着眼于它在最坏情况下需要多少步。原因很简单,连最坏的情况都做足准备了,其

    2024年02月15日
    浏览(43)
  • 数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)

    目录 插入排序  希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare法 挖坑法 前后指针法 快排特性总结 三数取中优化 小区间优化 快排非递归 归并排序 归并排序非递归 计数排序 总结 OJ测试 1、元素集合越接近有序,直接插入排序算法的时间效率越高 2、时间复杂度:O(N^2

    2023年04月09日
    浏览(87)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(66)
  • 数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

    上次是快排和冒泡:数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意) 今天为大家带来归并排序 归并排序是一种分治算法,它将序列分成两个子序列,分别对 子序列进行排序 ,然后将排序好的子序列 合并起来 。这个过程可以 递归 地进行,

    2024年01月22日
    浏览(67)
  • 【数据结构】—从冒泡排序丝滑过度快速排序(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:靴の花火—ヨルシカ            

    2024年02月08日
    浏览(39)
  • 常见排序集锦-C语言实现数据结构

    目录 排序的概念 常见排序集锦      1.直接插入排序      2.希尔排序      3.选择排序      4.堆排序      5.冒泡排序      6.快速排序             hoare              挖坑法             前后指针法             非递归      7.归并排序             非递归 排序实现

    2024年02月12日
    浏览(49)
  • 数据结构与算法——排序(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年04月09日
    浏览(59)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包