【探索排序算法的奥秘】一文初步详解八大排序

这篇具有很好参考价值的文章主要介绍了【探索排序算法的奥秘】一文初步详解八大排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


😏专栏导读

👻作者简介:M malloc,致力于成为嵌入式大牛的男人
👻专栏简介:本文收录于 初阶数据结构,本专栏主要内容讲述了初阶的数据结构,如顺序表,链表,栈,队列等等,专为小白打造的文章专栏。
👻相关专栏推荐:LeetCode刷题集,C语言每日一题。


【探索排序算法的奥秘】一文初步详解八大排序,初阶数据结构,排序算法,算法,热门,数据结构

🤖文章导读

本章我将详细的讲解关于八大排序的知识点
【探索排序算法的奥秘】一文初步详解八大排序,初阶数据结构,排序算法,算法,热门,数据结构

先导知识

在本篇文章中,我们将讨论将元素的数组排序的问题,为了方便理解,本篇文章的数组只包含整数。

我们对内部排序的考查将指出

  1. 存在几种容易的算法以 O(N²)排序,如插入排序。
  2. 有一种算法叫做希尔排序(ShellSort),它编程十分的简单,以O(N²)运行,并在实践中有效
  3. 有一些稍微复杂些的O(N*LogN)的排序算法
  4. 任何通用的排序算法均需要O(N*LogN)次比较

本章的其余部分将描述和分析各种排序算法。这些算法包含一些有趣的和重要的代码优化和算法设计思想,可以对排序做出精确的分析。预先说明,在适当的时候,我们将尽可能地多做一些分析。

🙀插入排序

最简单的排序算法之一是插入排序(insertion sort)。插人排序由N-1趟(pass)排序组成对于 i=1趟到 i=N - 1趟,插入排序保证从位置0 到位置i上的元素为已排序状态插入排序利用了这样的事实:位置0到位置 i-1上的元素是已排过序的。下图显示一个简单的数组在每一趟插人排序后的情况。

【探索排序算法的奥秘】一文初步详解八大排序,初阶数据结构,排序算法,算法,热门,数据结构

全部的思路就是以上的思路啦,就是我们需要从i位置进行比较,然后把大的数依次的往后移动,把小的数依次往前移动。这样排序排的就是升序下面是代码实现


代码实现

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

【探索排序算法的奥秘】一文初步详解八大排序,初阶数据结构,排序算法,算法,热门,数据结构

直接插入排序的特性总结

  1. 元素集合越接近有序,直接插入排序算法的时间效率更高
  2. 时间复杂度:O(N²)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

😳希尔排序(缩小增量排序)

没想到吧,其实希尔排序也属于插入排序类的方法,但在时间效率上较上一种排序方法有较大的改进。

从对直接插入排序的分析得知,其算法时间复杂度为O(n²),但是,若待排序记录序列为正序时,其时间复杂度可提高至O(N)。


思想讲解

先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序。

代码实现

void ShellSort(int* a, int n)
{
	//1、gap > 1 预排序
	//2、gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就
    会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的
    希尔排序的时间复杂度都不固定:

😳冒泡排序

冒泡排序就是一个老生常谈的话题了,这里就不细讲啦,因为我相信大家在学校里,老师基本上都会教这个算法,因为它是最容易上手滴,也是最容易理解的。其实冒泡排序还叫起泡排序。

时间复杂度:O(N²)

代码实现

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])
			{
				int tmp = a[i];
				a[i] = a[i - 1];
				a[i - 1] = tmp;

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

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

😳选择排序

基本思想

每一趟在n-i-1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单且为人们所熟悉的时简单选择排序。

代码实现

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		// 如果maxi和begin重叠,修正一下即可  
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

直接选择排序的特性总结:

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

😳堆排序

只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。

代码实现

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;
		}
	}
	
}

//排升序 N * logN 
void HeapSort(int* a, int n)
{
	//建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

直接选择排序的特性总结:

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

😳快速排序

快速排序是对起泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一个部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

代码实现(hoare版本)

int partSort(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (right > left && a[right] >= a[keyi])
		{
			--right;
		}
		//左边找大
		while (right > left && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);
	return left;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = partSort(a, begin, end);
	//[begin, keyi - 1] keyi [keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

快速排序的特性总结:

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

😳归并排序

归并排序是又一类不同的排序方法。"归并"的含义是将两个或两个以上的有序的有序表组合成一个新的有序表。它的实现方法早已为大家所熟悉,无论是顺序存储结构还是链表存储结构,都可在O(m+n)的时间量级上实现。利用归并的思想容易实现排序。

代码实现

void _mergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin == end)
		return;
	//小区间优化
	if (end - begin + 1 < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int mid = (begin + end) / 2;
	//[begin, mid][mid+1, end] 
	_mergeSort(a, begin, mid, tmp);
	_mergeSort(a, mid + 1, end, tmp);

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

void mergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	
	_mergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

😳计数排序

计数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

代码实现

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	
	int range = max - min + 1;
	int* CountA = (int*)malloc(sizeof(int) * range);
	memset(CountA, 0, sizeof(int) * range);
	//统计次数
	for (int i = 0; i < n; i++)
	{
		CountA[a[i] - min]++;
	}

	//排序
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (CountA[j]--)
		{
			a[k++] = j + min;
		}
	}
}

计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(范围)
    比特就业课
  4. 稳定性:稳定

总结

以上就是八大排序的详解以及代码的实现啦!我们下期再见啦!文章来源地址https://www.toymoban.com/news/detail-621177.html

到了这里,关于【探索排序算法的奥秘】一文初步详解八大排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 详解八大排序算法-附动图和源码(插入,希尔,选择,堆排序,冒泡,快速,归并,计数)

    目录 🍏一.排序的概念及应用🍏  1.排序的概念  2.排序的应用  3.常用的排序算法 🍎二.排序算法的实现🍎 1.插入排序 1.1直接插入排序 1.2希尔排序(缩小增量排序) 2.选择排序 2.1直接选择排序 2.2堆排序 3.比较排序 3.1冒泡排序 3.2快速排序  递归版本 快速排序递归优化 快速

    2024年02月01日
    浏览(58)
  • 【初阶算法4】——归并排序的详解,及其归并排序的扩展

    目录 前言 学习目标: 学习内容: 一、介绍归并排序 1.1 归并排序的思路 1.2 归并排序的代码 1.2.1 mergesort函数部分  1.2.2 process函数部分  1.2.3 merge函数部分  二、AC两道经典的OJ题目 题目一:逆序对问题 题目二:小和问题  三、练习一道LeetCode的题目 四、总结在什么情况下使

    2024年02月08日
    浏览(39)
  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(51)
  • 八大排序算法----堆排序

    堆排序的基本步骤:(以从大到小的顺序排序为例) 1.构建大顶堆( 每个结点的值都大于或等于其左右孩子结点的值 ) 2.排序:每次堆顶的元素取出来( 整个堆中值最大 ),与最后一个节点做交换, 使末尾元素最大 3.交换完之后,需要重新维护堆中剩下的其他节点,保证

    2024年02月09日
    浏览(39)
  • 【八大经典排序算法】快速排序

    说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代,计算机科学家们开始研究如何对数据进行排序,以提高计算机程序的效率。当时,常用的排序算法包括冒泡排序、插入排序和选择排序等。 然而,这些算法的效率都相对较低,特别是在处理大量数据时。于是,

    2024年02月07日
    浏览(48)
  • 八大排序算法之插入排序+希尔排序

    目录 一.前言(总体简介) 关于插入排序  关于希尔排序: 二.插入排序 函数首部: 算法思路: 算法分析 插入排序代码实现: 插入排序算法的优化前奏:  三.希尔排序(缩小增量排序) 1.算法思想:  2.算法拆分解析  序列分组 分组预排序: 分组预排序的另一种实现方式: 希尔排序的实现

    2023年04月09日
    浏览(43)
  • 【算法】经典的八大排序算法

    点击链接 可视化排序 动态演示各个排序算法来加深理解,大致如下 原理 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过多次比较和交换相邻元素的方式,将最大(或最小)的元素逐步冒泡到数组的一端。每一轮冒泡将会将未排序部分中最大(或最小)的元素“浮”

    2024年02月11日
    浏览(41)
  • 八大排序算法--冒泡排序(动图理解)

    算法思路 冒泡排序的原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。 以从小到大排序为例,第一轮比较后,所有数中最大的那个数就会浮到最右边;第二轮比较后,所有数中第二大的那

    2024年02月14日
    浏览(41)
  • 八大排序算法--希尔排序(动图理解)

    目录 希尔排序 概念 算法思路 动画演示 代码如下 复杂度分析 时间复杂度测试 运行结果  完整代码  创作不易,如果本篇博客对您有一定的帮助,大家记得留言+点赞哦。 概念 希尔排序是插入排序的一种,是对直接插入排序的优化。其特点在于分组排序。 算法思路 希尔排序

    2024年02月14日
    浏览(54)
  • 八大排序算法--选择排序(动图理解)

    算法思路 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。  选择排序的步骤: 1首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 2再从剩余未排序元素中继续寻找最小(大)元

    2024年02月14日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包