007+limou+C语言基础排序算法(上)

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

0.前言

您好这里是limou3434的一篇博文,感兴趣可以看看我的其他内容。

排序算法简单理解就是:一串数组经过排序算法后得到有序的数组。排序算法在不同应用场景有不同的效果,因此我们有必要了解一些基础的排序算法。

而本次我给您带来的是一些基础的排序算法,主要涉及四种排序算法:插入排序、选择排序、交换排序、归并排序。

007+limou+C语言基础排序算法(上)

1.插入排序

1.1.直接插入排序

1.1.1.排序思想

在[0,end]有序的前提下,保证插入tmp后依旧有序。

1.1.2.具体code与test用例

#include <stdio.h>
void InsertSort(int* arr, int arrSize)
{
	for(int i = 0; i < arrSize; i++)
	{
		int end = i-1;
		int tmp = arr[i];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
void test(void)
{
	int arr[10];
	srand((unsigned)time(0));
	printf("排序前:");
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 10;
		printf("%d ", arr[i]);
	}
	printf("\n排序后:");
	InsertSort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	test();
	return 0;
}

1.1.3.算法复杂度分析

在最坏情况下,每次tmp进来都需要把索引[0,end]的数据往后挪动,总共挪动的次数是“0+1+2+…+(n-1)=((0+n-1)*(n))/2”,即时间复杂度为O(n^2)。

1.2.希尔排序

1.2.1.排序思想

希尔排序的思想就是:先对数据进行预排序,然后进行直接插入排序。

详细的思路就是:假设有一个值gap,将数据间隔gap分为一组,然后对每一组分别进行直接插入排序,因此这里可以复用之前的直接插入排序代码。

写希尔排序最好先写直接插入排序,然后改写为希尔排序(就是把1改成gap),最后得到预排序数组。

007+limou+C语言基础排序算法(上)
007+limou+C语言基础排序算法(上)
007+limou+C语言基础排序算法(上)

1.2.2.具体code与test用例

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <stdio.h>
#define SIZE 100
void InsertSort(int* arr, int arrSize)//插入排序的实现
{
	for (int i = 0; i < arrSize; i++)
	{
		int end = i - 1;
		int tmp = arr[i];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
void ShellSort(int* arr, int arrSize)//希尔排序的实现
{
	//0.gap的最大意义在于:让最大的数更快跳到后面,让更小的数更快跳到前面
	//0.1.gap越大越不接近有序,但是跳得快
	//0.2.gap越小越接近有序,特别当gap=1时,其效果等价于直接插入排序

	//1.写法一(单组单排)
	//for (int gap = arrSize/2; gap >= 1; gap /= 2)//1.3.控制gap的大小
	//{
	//	for (int j = 0; j < gap; j++)//1.2.分别使用“直接插入排序”排序gap组个数组
	//	{
	//		for (int i = j; i < arrSize; i += gap)
	//		{
	//			//1.1.某一次一组的“直接插入排序”
	//			int end = i - gap;
	//			int tmp = arr[i];
	//			while (end >= 0)
	//			{
	//				if (tmp < arr[end])
	//				{
	//					arr[end + gap] = arr[end];
	//					end -= gap;
	//				}
	//				else
	//				{
	//					break;
	//				}
	//			}
	//			arr[end + gap] = tmp;
	//		}
	//	}
	//}
	
	//2.写法二(多组同排,但是效率没有变化)
	int gap = arrSize;
	while(gap > 1)//2.3.控制gap的大小(注意这里得入口不能写等于,会因为条件“gap=gap/3+1”而死循环,这是代码设计导致的)
	{
		gap = gap / 3 + 1;//加1是为了保证最后一次是1,能用上gap=1的直接插入排序
		for (int i = 0; i < arrSize; i++)//2.2.每组只取一个元素排序
		{
			//2.1.“直接插入排序”代码 
			int end = i - gap;
			int tmp = arr[i];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
void Test1()
{
	int arr[SIZE] = { 0 };
	for (int i = 0; i < SIZE; i++)
	{
		arr[i] = rand() % 10;
	}
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	printf("InsertSort() :");
	InsertSort(arr, SIZE);
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n\n");
}
void Test2()
{
	int arr[SIZE] = { 0 };
	for (int i = 0; i < SIZE; i++)
	{
		arr[i] = rand() % 10;
	}
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	printf("ShellSort()  :");
	ShellSort(arr, SIZE);
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n\n");
}
int main()
{
	Test1();
	Test2();
	return 0;
}

1.2.3.算法复杂度分析

希尔排序的算法复杂度分析不能只看for循环,这是极其错误的,一个典型的例子就是:我们在写希尔排序的时候,写了“四层循环”和“三层循环”的方法,但是两种方法的效果是一样的。

007+limou+C语言基础排序算法(上)

以博主的数学知识是没有办法进行计算的(貌似在数学界也有些问题没有被解决),所以暂时跳过吧。我们只需要记住希尔排序的时间复杂度范围在[O(N*(log(2)(N))2),O(N2)]之间即可,整体认为希尔排序的时间复杂度是O(N^1.3)即可。

2.选择排序

2.1.直接选择排序

2.1.1.排序思想

从一个待排序列中选出最小/最大的数,然后将最小/最大的数和待排序列中的第一个数/最后一个数交换,不断重复。

但是这样效率太低,可以优化一下:从一个待排序列中选出最小的数和最大的数,然后将最小的数和最大的数分别和待排序列中的第一个数和最后一个数交换,不断重复,效率好了一倍。文章来源地址https://www.toymoban.com/news/detail-515041.html

2.1.2.具体code与test样例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <stdio.h>
#define SIZE 10
void _Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
void SelectSort(int* arr, int arrSize)
{
	int begin = 0, end = arrSize - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = end;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] > arr[maxi])//选出最大数的下标
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])//选出最小数的下标
			{
				mini = i;
			}
		}
		_Swap(&arr[begin], &arr[mini]);
		if (begin == maxi)//处理特殊情况
		{
			maxi = mini;
		}
		_Swap(&arr[end], &arr[maxi]);
		begin++;
		end--;
	}
}
int main()
{
  	int arr[SIZE] = { 0 };
	for (int i = 0; i < SIZE; i++)
	{
		arr[i] = rand() % 10;
	}
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	printf("SelectSort() :");
	SelectSort(arr, SIZE);
	for (int i = 0; i < SIZE; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n\n");
	return 0;
}

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

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

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

相关文章

  • 顺序表基本操作算法——基础代码(C语言)

     创建一个顺序表(数据元素个数为5), 输出顺序表中的所有数据元素 查找第3个位置上的元素 查找元素15是否在顺序表中,如果在,请输出该元素在顺序表中的位置 在顺序表中的第1个位置插入数据0 删除刚刚插入的元素 输出顺序表中的所有数据元素 运行结果如下  

    2024年02月06日
    浏览(46)
  • 算法 时间、空间复杂度的计算(C语言/小白/零基础/新手 + 例题)

    目录 1. 时间复杂度 计算时间复杂度( O(N))的方法:   例1:嵌套循环时间复杂度的计算      例2:双重循环时间复杂度的计算   例3:常熟循环的时间复杂度   例6:冒泡排序的时间复杂度   例7: 二分查找的时间复杂度   例8:斐波那契的时间复杂度         常见的时间

    2024年02月08日
    浏览(39)
  • 2023届计算机保研面试基础专业问题(数据结构、算法、计算机语言、计算机网络、数据库、操作系统、数学)

    以下的专业相关基础问题,是在2022年暑期准备面试过程中,断断续续准备的,最终上岸厦大啦,也希望这些内容对后面准备保研的学弟学妹们有帮助。少即是多、快即是慢,希望大家也不必太焦虑,慢慢来比较快! 堆、栈、队列、链表等数据结构 树:红黑树、二叉树的各类

    2024年02月15日
    浏览(57)
  • java语言基础(有c语言基础)

    jdk+记事本编译 编译javac Hello.java 执行java Hello byte b=123;//整型8位最大值是2的7次减一,第一位是符号位 short s=32156;//最大是2的15次-1 int i=101;//31 long l=123;63 float s=3.14; double d=3.14; boolean ok=true; char c=\\\'a\\\'; 3.14默认double 在后面加f float s=3.14f; (F不区分大小写 java无符号 字符 可以赋值

    2024年02月16日
    浏览(40)
  • 数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)

    目录 问题描述  解题思路 伪代码  总体算法 DFS算法 伪代码解读 总体算法 DFS算法 具体实现(C语言) 在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑

    2024年02月05日
    浏览(73)
  • R语言基础之R语言入门

             R语言最初是由新西兰奥克兰大学统计系的教授 Ross Ihaka 和 Robert Gentleman 在 S语言基础上开发完成的。是一门解释性语言。在我看来R语言是一门数学性极强的语言,或者说这是一门为数学而生的语言,因为其具有极其出色的计算与统计分析能力,但是在程序流转方

    2024年02月16日
    浏览(42)
  • 汇编语言笔记(一)——汇编语言基础

    一、开发环境 我使用visual studio 2022 preview,其他版本的设置大同小异。 第一步: 打开visual studio,点击“创建新项目”: 第二步: visual studio并没有专门的汇编项目,所以需要挂羊头卖狗肉,选择C++空项目 第三步: 输入项目名称,点击创建 第四步: 鼠标右键单击项目名称—

    2024年02月05日
    浏览(39)
  • 码蹄杯语言基础:选择结构(C语言)

    请编写一个简单程序,输入一个整数,和10比较,输出比较结果 格式 输入格式: 输入整型 输出格式: 输出…大于或者等于或者小于10 输入a,b两个整数,输出他们之间的最小值 格式 输入格式: 输入2个整数用空格分隔 输出格式: 输出为整型 输入a,b两个整数,输出他们之间

    2024年02月06日
    浏览(37)
  • 码蹄杯语言基础:结构体(C语言)

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist 狼群新生了一只尊贵的艾尔法狼,请设计一个结构体,管理它的信息,信息包括名字,年龄,性别。 输入艾尔法狼宝宝的信息,然后再输出他的信息。 格式 输入格式: 输入名字性别为字符型,年龄整型 输出格式: 输出名字

    2024年02月11日
    浏览(36)
  • Go语言基础知识(一):基础介绍

    Go 语言又称 Golang,由 Google 公司于 2009 年发布,近几年伴随着云计算、微服务、分布式的发展而迅速崛起,跻身主流编程语言之列,和 Java 类似,它是一门静态的、强类型的、编译型编程语言,为并发而生,所以天生适用于并发编程(网络编程)。 目前 Go 语言支持 Windows、

    2024年02月13日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包