一.排序方法
- 被排列的数组data[0...n],选定当前位置i=0作为最小值下标position;在data[i+1...n]区间每个元素与data[position]比较,记录新position,最后交换data[i]和data[position]。这样最小的元素就到了当前位置了。
- 当前位置i+1,重复1...
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhijiexuanze.htm
三.Java代码
public static int[] selectSort(int[] data) {
int temp = 0;
int position = 0;
int j = 0;
for (int i = 0; i < data.length - 1; i++) { //i当前位置
position = i; //position最小下标
j = i + 1;
for (; j < data.length; j++) { //j从此区间选取最小下标
if (data[j] < data[position]) {
position = j;
}
}
if (position != i) {
temp = data[i];
data[i] = data[position];
data[position] = temp;
}
}
return data;
}
四.时间复杂度和稳定性
- 最好时间复杂度
- 若文件的初始状态是正序的,所需的关键字比较次数C和记录移动次数M。
- Cmin=n(n-1)/2=0(n2)
- Mmin=0
- 直接选择排序最好的时间复杂度为O(n2)
- 最坏时间复杂度
- 若初始文件是反序的,所需的关键字比较次数C和记录移动次数M。
- Cmax=n(n-1)/2=O(n2)
- Mmax=3(n-1)=O(n)
- 直接选择排序的最坏时间复杂度为O(n2)
- 平均时间复杂度
- O(n2)
- 直接选择排序是就地排序,它是不稳定的。反例[2,2,1] 。
分享到:
相关推荐
《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法分析方面卓有建树,他的数据结构和算法分析的著作尤其畅销,并受到广泛好评,已被世界500余所大学选作教材。...
Sahni博士为每一个数据结构和算法都提供了若干个应用实例,涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起,使理论与实践统一,从而让概念容易理解,使学生增加学习动力和兴趣。 ...
介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、...
数据结构与算法之内部及外部排序算法的学习
c语言版本的数据结构的快速排序算法,适用于新手学习
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
数据结构与算法的定义 1.广义上理解数据结构与算法: 数据结构是指一组数据的存储结构。算法就是操作数据的一组方法。 ps:图书馆管理员将书籍分门别类“存储”,按照一定规律编号,就是书籍这种“数据的存储结构...
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
本资源适合数据结构与算法学习者和考生使用,帮助他们通过项目实践来加深对冒泡排序算法的理解和掌握,提高编程的能力和水平。 提供了多种算法演示和验证的功能,如输入和输出待排序的数据,显示冒泡排序的过程和...
本资源为数据结构与算法第三章(排序)的作业程序代码。包含以下的两个程序: 3.4 rk作哨兵直接插入排序 3.8 双向起泡 北工大电控学院《数据结构与算法》课程的其它章节程序实验及作业代码亦已在本站上传,需要的...
数据结构与算法内部排序分析PPT学习教案.pptx
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡...在研究学习了之前几种排序算法的基础上,讨论发现一种新的排序算法,并通过了进一步的探索,找到了新的排序算法较之前几种算法的优势与不足。
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
08:排序:如何利用合并与快排的小技巧,解决算法难题?.mp4 09:二分搜索:为什么说有序皆可用二分?.mp4 11:贪心:这种思想,没有模板,如何才能掌握它?.mp4 12:回溯:我把回溯总结成一个公式,回溯题一出就用它....
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
项目标题:Python数据结构与算法源码集合 项目概述: 本项目采用Python语言编写,包含了丰富的数据结构与算法...本源码集锦旨在提供一份清晰、实用的数据结构与算法实现参考,助力读者在计算机科学领域的学习与成长。
《数据结构与算法设计》以基本...《数据结构与算法设计》内容丰富,观点新颖,理论联系实际,不仅可用做高等院校计算机科学与工程专业学生学习数据结构与算法的教材,而且也适合广大工程技术人员参考。本书由王晓东著。
本资源为数据结构与算法第三章(排序)的实验程序代码。包含以下的三个程序:1.快速排序;2.归并排序;3.基数排序。 北工大电控学院《数据结构与算法》课程的其它章节实验及作业程序代码亦已在本站上传,需要的同学...