数据结构笔记 – 排序算法 简单选择排序算法
本文由发表于6年前 | 数据结构与算法 | 暂无评论 |  被围观 5,105 views+

简单选择排序:

假设待排序数组长度为n,通过n-1此循环进行数组元素间的比较,每一轮中,假设该轮为第i轮,从n-i+1个元素中选出最小的,并和第i个元素进行交换。

#include <stdio.h>    

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r,r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 简单选择排序算法 */
void SelectSort(SortList *L)
{
	int i,j,min;
	int temp;
	for(i=1;i<L->length;i++)
	{
		/* 首先设置i为当前最小下标 */
		min = i;
		/* 循环之后的数据和选定的r[min]比较 */
		for (j = i+1;j<=L->length;j++)
                {
			/* 发现更小的元素,把对应的下标赋给min */
			if (L->r[min]>L->r[j])
                                min = j;
                }
		if(i!=min){
			/* 交换r[i]与r[min]的值 */
			temp=L->r[i];
			L->r[i]=L->r[min];
			L->r[min]=temp;
		}
	}
}
简单选择排序的时间复杂度分析:

相比于冒泡排序算法,由于选择排序每次寻找最小元素使用的是数组下标作为标记,直到最后才进行交换移动的,所以减少了交换的次数。

需要的比较次数是固定的:n-1+n-2+n-3+…+1=n(n-1)/2次。

需要的交换次数:最好情况下为0此,最差情况下需要交换n-1次,总得时间复杂度为O(n^2)。

随意时间复杂度与冒泡排序相同,但是简单选择排序的性能还是要比冒泡排序好一点。

除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/data-structure-notes-simple-selection-sort-algorithm-sorting-algorithm.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    没有评论
给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 在YUI中通过YUI.add()添加自定义模块 2012/1/10
2 从一笔交易说起,如何处理好数据的一致性问题 2016/6/14
3 JVM笔记 – 自动内存管理机制(调优案例分析与实战) 2014/11/30
4 乐器销售管理系统 | Project 2011/11/15
5 Java源码分析 – LinkedList双向链表源码分析 2011/10/11
6 谷歌浏览器Chrome控制台提示Uncaught ReferenceError xl_chrome_menu is not defined 2011/7/28
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
猜您喜欢
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.