文档章节

选择排序详述

liddblog
 liddblog
发布于 2017/01/07 19:10
字数 560
阅读 4
收藏 0

选择排序

      选择排序改进了冒泡排序,将必要的交换次数从O(n2)减少到了O(N),不幸的是比较次数仍然保持为O(N2),然而选择排序仍然为大记录量的排序提出了一个非常了不去的重要的改进,因为这些记录需要在内存中移动,这就使交换的时间和比较的时间相比起来,交换的时间更为重要.(一般来说,在java中不是这种情况,java中只是改变了引用位置,而实际对象的位置并没有发生改变。)

// selectSort.java
	// demonstrates selection sort
	// to run this program: C>java SelectSortApp
	////////////////////////////////////////////////////////////////
	class ArraySel
	   {
	   private long[] a;                 // ref to array a
	   private int nElems;               // number of data items
	//--------------------------------------------------------------
	   public ArraySel(int max)          // constructor
	      {
	      a = new long[max];                 // create the array
	      nElems = 0;                        // no items yet
	      }
	//--------------------------------------------------------------
	   public void insert(long value)    // put element into array
	      {
	      a[nElems] = value;             // insert it
	      nElems++;                      // increment size
	      }
	//--------------------------------------------------------------
	   public void display()             // displays array contents
	      {
	      for(int j=0; j<nElems; j++)       // for each element,
	         System.out.print(a[j] + " ");  // display it
	      System.out.println("");
	      }
	//--------------------------------------------------------------
	   public void selectionSort()
	      {
	      int out, in, min;
	
	      for(out=0; out<nElems-1; out++)   // outer loop
	         {
	         min = out;                     // minimum
	         for(in=out+1; in<nElems; in++) // inner loop
	            if(a[in] < a[min] )         // if min greater,
	                min = in;               // we have a new min
	         swap(out, min);                // swap them
	         }  // end for(out)
	      }  // end selectionSort()
	//--------------------------------------------------------------
	   private void swap(int one, int two)
	      {
	      long temp = a[one];
	      a[one] = a[two];
	      a[two] = temp;
	      }
	//--------------------------------------------------------------
	   }  // end class ArraySel
	////////////////////////////////////////////////////////////////
	class SelectSortApp
	   {
	   public static void main(String[] args)
	      {
	      int maxSize = 100;            // array size
	      ArraySel arr;                 // reference to array
	      arr = new ArraySel(maxSize);  // create the array
	
	      arr.insert(77);               // insert 10 items
	      arr.insert(99);
	      arr.insert(44);
	      arr.insert(55);
	      arr.insert(22);
	      arr.insert(88);
	      arr.insert(11);
	      arr.insert(00);
	      arr.insert(66);
	      arr.insert(33);
	
	      arr.display();                // display items
	
	      arr.selectionSort();          // selection-sort them
	
	      arr.display();                // display them again
	      }  // end main()
	   }  // end class SelectSortApp

选择排序的效率

       选择排序和冒泡排序执行了相同次数的比较:N*(N-1)/2。对于10个数据,需要45次比较。然而10个数据需要少于10次交换,对于100个数据,需要4950次比较,但只进行了不到100次交换,N值很大时,比较次数是主要的,所以结论是选择排序和冒泡排序一样运行了O(N2)时间。但是,选择排序无疑更快,因为它进行的交换少的多,当N值较小时,特别是如果交换的时间比比较的时间级大得多时,选择排序实际上是相当快的。

© 著作权归作者所有

上一篇: 插入排序详述
下一篇: 冒泡算法详述
liddblog
粉丝 4
博文 70
码字总数 65593
作品 0
海淀
程序员
私信 提问
学习JavaScript数据结构和算法(第二版) 读后感

总体概述 本书是由[巴西] 格罗纳(Loiane Groner)[著作],全书总共238页; 本书从介绍javascript语言入手,然后分别介绍了数组(列表)、栈、队列、链表等顺序数据结构,然后依次介绍了集合、...

张蕾_
2018/06/01
0
0
Java语言学习(四):数组及常用操作

众所周知,坐标系有一维、二维、三维,Java中数组也不例外,像一维数组、二维数组,下面就数组来说下相关知识。 先通过简单的案例来熟悉数组: (1)任务:实现二维数组的行列互换 (2)准备...

海岸线的曙光
2018/07/12
8
0
排序——简单选择排序

一、选择排序概念 选择排序(Selection Sort)的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中扫描,选择最小的记录将其输出……不断重复这个过程,直到...

翼动动空
2016/06/06
1K
0
直接选择排序(Straight Selection Sort)

1、定义 选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。 常用的选择排序方法有直接选择排序...

野渡书生
2016/05/03
14
0
排序算法篇_选择排序法

image   选择排序(Selection Sort)也是比较简单的排序算法,思路也比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。 选择排序算法 选择排序算法通过选择和交...

一笑小先生
2018/01/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

安全组和云防火墙的区别

前言 熟悉云平台的朋友可能都会注意到这样一个事情:无论公有云还是私有云,创建虚拟机的时候都需要选择安全组,来对虚拟机进行安全防护;有的云平台在VPC里,还能选择防火墙,ZStack在3.6版...

ZStack社区版
18分钟前
1
0
教育性app开发的重要性和好处

在这个精通技术的世界中,流行的app主导着无聊的教育系统。当我们将技术和教育结合在一起时,它将带来当代以及强大的学习资源。因此,将教育移动app集成到您的学习过程中,并根据自己的信念把...

a429011717
19分钟前
2
0
IE6/7/8如何兼容CSS3属性

本文转载于:专业的前端网站➩IE6/7/8如何兼容CSS3属性 最近在工作中总是要求IE8兼容CSS3属性,在网上搜了搜主要是引入了一个htc文件(ie-css3.htc或者PIE.htc。个人认为这两个文件的作用差不...

前端老手
34分钟前
2
0
手把手教你ALLEGRO的约束规则的设置教程!

约束规则的设置 分三步, 定义规则(一、基本约束规则设置:1、线间距设置;2、线宽设置;3、设置过孔;4、区域约束规则设置;5、设置阻抗;6、设置走线的长度范围;7、设置等长:7.1、不过电阻的NET 等...

demyar
36分钟前
3
0
完美解决H5滚动滑动穿透方案:不使用系统滚动

网上有很多黑科技解决这个问题,都不是从根本去解决,例如通过js控制弹出时html加上position:fixed; 弹窗关闭后再去掉该样式,总觉得不太对,像是打补丁。 今天终于找到了滚动穿透的原因和完...

未来cc
41分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部