简单选择排序 C语言

简单选择排序 C语言简单选择排序(SimpleSelectionSort)也称作直接选择排序。算法步骤:1)设待排序的记录存放在数组Data[1…n]中。第一趟从Data[1]开始,通过n-1次比较,从n个记录中选出关键字最小的记录,记为Data[k],交换Data[1]和Data[k]。2)第二趟从Data[2]开始,通过n-2次比较,从n-1个记录中选出关键字最小的记录,记为Data[k],交换Data[2]和Data[k]。3)依次类推,第i趟从Data[i]开始,通过n-i次比较,从n-i

大家好,又见面了,我是你们的朋友全栈君。

简单选择排序

(Simple Selection Sort)也称作直接选择排序。

算法步骤:

1) 设待排序的记录存放在数组Data[1…n]中。第一趟从Data[1]开始,通过n-1次比较,从n个记录中选出关键字最小的记录,记为Data[k],交换Data[1]和Data[k]。
2) 第二趟从Data[2]开始,通过n- 2次比较,从n-1个记录中选出关键字最小的记录,记为Data[k],交换Data[2]和Data[k]。
3) 依次类推,第i趟从Data[i]开始,通过 n – i 次比较,从n-i+1个记录中选出关键字最小的记录,记为Data[K],交换Data[i]和Data[k]。
4) 经过n-1趟,排序完成。

书上的例子:
在这里插入图片描述
时间复杂度

O( n 2 n^2 n2)

空间复杂度

O(1)

算法特点:

1 ) 就选择排序方法本身来讲,它是一种稳定的排序 方法,但图中例子所表现出来的现象是不稳定的,这是因为上述实现选择排序的算法采用“交换记录”的策略所造成的,改变这个策略可以写出不产生“不稳定现象”的选择排序算法。
2 ) 可用于链式存储结构。
3 ) 移动记录次数较少,当每一记录占用的空间较多时,此方法比直接插人排序快。

完整代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100 //顺序表最大容量,可以自行加大 

typedef struct 
{ 
   
	int key;//关键字项 
	char *otherinfo;//其他数据项 
}ElemType;//记录类型 
typedef struct
{ 
   
	ElemType Data[MAXSIZE+1];//静态顺序表的数据域,这里Data[0]为空闲或者为哨兵单元 
	int length;//顺序表的长度 
}SqList;//顺序表 

void InitList(SqList &L)//顺序表的初始化 
{ 
   
	L.length = 0;//使顺序表长度归0,便是顺序表的初始化 
}

void CreateList(SqList &L)//顺序表的创建 
{ 
   
	printf("请输入:"); 
	while(1)//建立一个死循环,循环终止条件是按了enter键 
	{ 
   
		L.length++;//顺序表长度加一 
		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
		{ 
   
			printf("顺序表已满!\n");
			return ;
		}
		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
		if(getchar() == '\n')//循环终止条件 
			break;
	}
}

void InputList(SqList L)//顺序表的输出 
{ 
   
	int i;//记录次数 
	if(L.length == 0)//判断顺序表是否为空 ,若为空结束该函数 
	{ 
   
		printf("顺序表是空的!\n");
		return ;
	}
	printf("打印为:");
	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
		printf("%d ",L.Data[i].key);	
}

void SelectSort(SqList &L)//简单选择排序 
{ 
   
	int i,j,//利用两层循环排序所有关键字 
		k;//k为记录剩余关键字中最小的位置 
	for(i=1;i<L.length;i++)//在L.Data[i…L.length]中选择关键字最小的记录 
	{ 
   
		k = i;
		for(j=i+1;j<=L.length;j++)
		{ 
   
			if(L.Data[k].key > L.Data[j].key)//k指向此趟排序中关键字最小的记录 
				k = j;
		}
		if(k != i)//交换Data[i]与Data[k] 
		{ 
   
			L.Data[0] = L.Data[i];
			L.Data[i] = L.Data[k];
			L.Data[k] = L.Data[0];
		}
	}
}

int main()
{ 
   
	SqList L;
	InitList(L);//初始化顺序表 
	CreateList(L);//创建顺序表 
	SelectSort(L);//简单选择排序 
	InputList(L);//打印排序后结果 
	return 0;
}

在这里插入图片描述
(完)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152977.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • LockWorkStation应用–运行后锁屏

    LockWorkStation应用–运行后锁屏batch脚本如下:rundll32.exe user32.dll,LockWorkStation————msdn上的介绍,BOOLWINAPILockWorkStation(void);http://msdn.microsoft.com/en-us/library/aa376875(VS.85).aspx

  • Python字符串总结大全

    Python字符串总结大全目录操作符标准类型操作符对象值的比较布尔类型序列操作符切片([]和[:])成员操作符(in,notin)连接符(+)运行时刻字符串连接编译时字符串连接普通字符串转化为Unicode字符串重复操作符(*)只适用于字符串的操作符格式化操作符(%)字符串模板:更简单的替代品原始字符串操作符(r/R)Unicode字符串操作符(u/U)常见的转义字符字符串索引编解码内建函数序列类型函数len()max()和min()en

  • 初识SQL Server2017 图数据库(一)

    初识SQL Server2017 图数据库(一)

    2021年11月24日
  • menuconfig 图形化配置

    menuconfig 图形化配置  uboot或Linux内核可以通过输入“makemenuconfig”来打开图形化配置界面,menuconfig是一套图形化的配置工具,需要ncurses库支持。ncurses库提供了一系列的API函数供调用者生成基于文本的图形界面  menuconfig重点会用到两个文件:.config和Kconfig,.config文件保存着uboot或Linux内核的配置项,使用menuconfig配置完uboot或Linux内核以后肯定要更新.config

  • java 代码生成器 generator

    java 代码生成器 generator文章目录写在前面1、mybatis-generator1.1、第一种:利用maven插件实现2、mybatis-plus-generator写在前面我们在java开发中,经常要建一些常用的包、类,他们都千篇一律,没什么技术含量,于是我们想到了用代码生成器去自动生成他们,例如mapper、dao、实体类。1、mybatis-generatormybatis-generator的运行过程:首先连接数据库,然后从数据库的表中读取字段,生成对应文件。1.1、第一种:利用maven插件实现整个过程你只需要

  • wxPython中文教程入门实例「建议收藏」

    wxPython中文教程入门实例「建议收藏」这篇文章主要为大家分享下python编程中有关wxPython的中文教程,分享一些wxPython入门实例,有需要的朋友参考下wxPython中文教程入门实例 wx.Window是一个基类,许多构件从它继承。包括wx.Frame构件。可以在所有的子类中使用wx.Window的方法。wxPython的几种方法:*SetTitle(stri

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号