三大基础排序算法——我欲修仙(功法篇)

这篇具有很好参考价值的文章主要介绍了三大基础排序算法——我欲修仙(功法篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:【😊个人主页】
系列专栏:【❤️我欲修仙】
学习名言:莫等闲、白了少年头,空悲切。——岳飞



系列文章目录

第一章 ❤️ 学习前的必知知识
第二章 ❤️ 二分查找



前言🚗🚗🚗

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。今天就让我们学习其中最基础的三种算法吧!


冒泡排序

介绍

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端

运行原理

冒泡排序算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

三大基础排序算法——我欲修仙(功法篇)

基本概念

依次比较相邻的两个数,将小数放在前面,大数放在后面。

即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。
至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
这里特别说明:冒泡排序是有改进算法的,感兴趣的道友可以自己感悟感悟

代码实现

#include<stdio.h>
typedef  int Elemtype;
#define  MAX 10
typedef struct
{
	int *arr;
	int length;
}num;
num Sort_bobble(int *arr,int n){

	int end = n;
	int i = 0;
	while (end)
	{
		int flag = 0;
		for (i = 1;i < end;i++)
		{

			if (arr[i - 1] > arr[i])
			{
			/*	int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;*/
				swap(&arr[i], &arr[i - 1]);
				flag = 1;
			}

	    }
		if (flag == 0)
			break;
		end--;
	}
	num retult = { arr,n };
	return retult;
}//冒泡排序
int main()
{
	int arr[MAX] = { 2,3,4,5,1,3 };
	int n = 6;
	int i = 0;
	num retult = Sort_bobble(arr, n);  
	for(i = 0;i < retult.length;i++)
	{
	    printf("%d",retult.arr[i]);
	}
	return 0;
}

插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

运行原理

插入排序算法的运作如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到下一位置
  6. 重复步骤2
    如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

三大基础排序算法——我欲修仙(功法篇)

基本概念

假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.
插入算法还分为:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。

代码实现

#include<stdio.h>
typedef  int Elemtype;
#define  MAX 10
typedef struct
{
	int *arr;
	int length;
}num;
void swap(int* a, int* b)
{
	int tem = *a;
	*a = *b;
	*b = tem;
}//交换位置
num Sort_insert(int * arr, int n) {
	int i = 0;
	for (i = 0;i < n - 1 ;++i)
	{
		int end = i;
		int tem = arr[end + 1];
		while (end >= 0)
		{
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;

		}

		arr[end + 1] = tem;
	}
	num result = { arr,n };
	return result;
}//插入排序
int main()
{
	int arr[MAX] = { 2,3,4,5,1,3 };
	int n = 6;
	int i = 0;
	num retult = Sort_insert(arr, n);  
	for(i = 0;i < retult.length;i++)
	{
	    printf("%d",retult.arr[i]);
	}
	return 0;
}

选择排序

介绍

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。

运行原理

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

  1. 初始状态:无序区为R[1…n],有序区为空。
  2. 第1趟排序
  3. 在无序区R[1…n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1…1]和R[2…n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  4. 第i趟排序第i趟排序开始时,当前有序区和无序区分别为R[1…i-1]和R(i…n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1…i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

三大基础排序算法——我欲修仙(功法篇)

基本概念

对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置,接着第二次比较,前面"后一个元素"现变成了"前一个元素",继续跟他的"后一个元素"进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了,然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值,这样就找到整个数组中最小的数了。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。

代码实现

#include<stdio.h>
typedef  int Elemtype;
#define  MAX 10
typedef struct
{
	int *arr;
	int length;
}num;
num Sort_selection(int* arr, int n)
{
	int  i = 0;

	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int max = begin;
		int min = begin;
		for (i = begin;i <= end;i++)
		{
			if (arr[i] < arr[min])
				min = i;
			if (arr[i] > arr[max])
				max = i;
		}

		swap(&arr[min], &arr[begin]);
		if (begin == max)
			max = min;
		swap(&arr[max], &arr[end]);
		++begin;
		--end;
	}
	num retult = { arr,n };
	return retult;

}//选择排序
int main()
{
	int arr[MAX] = { 2,3,4,5,1,3 };
	int n = 6;
	int i = 0;
	num retult = Sort_selection(arr, n);  
	for(i = 0;i < retult.length;i++)
	{
	    printf("%d",retult.arr[i]);
	}
	return 0;
}

三大基础排序算法——我欲修仙(功法篇)文章来源地址https://www.toymoban.com/news/detail-467621.html

到了这里,关于三大基础排序算法——我欲修仙(功法篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法基础】(一)基础算法 --- 快速排序

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹   题目要求: 给定你一个长度为n的整数数列 请你使用快速排序对这个数列按照从小到大

    2023年04月14日
    浏览(41)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(53)
  • 〖大前端 - 基础入门三大核心之JS篇⑯〗- JavaScript的流程控制语句「for循环语句及算法题」

    当前子专栏 基础入门三大核心篇 是免费开放阶段 。 推荐他人订阅,可获取扣除平台费用后的35%收益,文末名片加V! 说明:该文属于 大前端全栈架构白宝书专栏, 目前阶段免费开放 , 购买任意白宝书体系化专栏可加入 TFS-CLUB 私域社区。 福利:除了通过订阅\\\"白宝书系列专

    2024年02月07日
    浏览(51)
  • 基础算法(1):排序(1):选择排序

         今天对算法产生了兴趣,开始学习基础算法,比如排序,模拟,贪心,递推等内容,算法是很重要的,它是解决某个问题的特定方法,程序=数据结构+算法,所以对算法的学习是至关重要的,它可以提高程序效率,不同的算法也是有优劣的,如何进行评价,这也是我们需

    2024年02月04日
    浏览(30)
  • 【基础算法】八大排序算法:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序(快排),归并排序,计数排序

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

    2024年02月01日
    浏览(47)
  • C语言分析基础排序算法——交换排序

    目录 交换排序 冒泡排序 快速排序 Hoare版本快速排序 挖坑法快速排序 前后指针法快速排序 快速排序优化 快速排序非递归版 见C语言基础知识指针部分博客C语言指针-CSDN博客 Hoare版本快速排序 Hoare版本快速排序的过程类似于二叉树前序遍历的过程,基本思想是:在需要排序的

    2024年03月14日
    浏览(49)
  • 算法基础(一)| 快速排序和归并排序详解

    ⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法

    2024年02月21日
    浏览(53)
  • 常见排序宝典:帮助快速上手常见基础排序算法(下)

    目录 五、归并排序 1、算法步骤  2、动图演示​编辑  3、代码实现 六、堆排序 1、算法步骤 2、动图演示  3、代码实现 七、快速排序 1、基本思想 2、动图演示 3、代码实现  八、计数排序 1、算法步骤  2、动图演示 ​编辑 3、代码实现  归并排序(MERGE-SORT)是建立在归并操

    2024年04月13日
    浏览(35)
  • 【基础算法训练】—— 01背包 + 排序

    零零散散的有几个专栏专栏,只是都没有成气候,我这儿了,可能蓝桥专栏,反响最好,只是受限制于自己的算法能力十分薄弱,就更得特别慢,也不全面吧,蓝桥现在是我的心头痛,我想暂时放一放,我自己也还在学,再次更那个专栏,可能有新的突破吧。千锤百炼,静待

    2024年02月13日
    浏览(34)
  • 算法基础学习笔记——①排序

    ✨ 博主:命运之光 ✨ 专栏: 算法基础学习 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 因为x参与交换之后仍然会被留在左右区间中的一个里。 1.确定分界点:(这里的分界点不一定是x,可以随意取值,常用取值方法如下) q[l],q[(l+r)/2],q[r],随机

    2024年02月07日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包