文档章节

《排序算法系列一、简单选择排序》

pradosoul
 pradosoul
发布于 2015/06/09 17:03
字数 1019
阅读 18
收藏 1
点赞 0
评论 0

一、简单选择排序

    1. 描述:给定待排序序列A[ 0......n ] ,选择出第i小元素,并和A[i]交换,这就是一趟简单选择排序。

    2. 示例:给定数组A[0 ...... 5]={3, 5, 8, 9, 1, 2},分析A数组进行选择排序的过程:

    3.             第一趟:i=1,index=5, a[1] 和 a[5] 进行交换。得到序列:{ 1,5,8,9,3,2 }

                  第二趟:i=2,index=6, a[2] 和 a[6] 进行交换。得到序列:{ 1,2,8,9,3,5 }

                  第三趟:i=3,index=5, a[3] 和 a[5] 进行交换。得到序列:{ 1,2,3,9,8,5 }

                  第四趟:i=4,index=6, a[3] 和 a[5] 进行交换。得到序列:{ 1,2,3,5,8,9 }

                  第五趟:i=5,index=5, 不用交换。得到序列:{ 1,2,3,5,8,9 }

                  6-1)趟选择结束,得到有序序列:{ 1,2,3,5,8,9 }

    4. public class SimpleSelectionSort1 {
      	
      	void simpleSelectionSort(int[] arr) {
      		int length = arr.length;
      		int i, j, index;
      		//1. 进行length-1趟选择,每次选择出最小值
      		for (i = 0; i < length; i++) {
      			index = i;
      			//2. 选择第i小记录为arr[index]
      			for (j = i+1; j < length; j ++) {
      				if (arr[j] < arr[index]) {
      					index = j;
      				}
      			}
      			
      			if (index != i) {
      				arr[i] = arr[i] + arr[index];
      				arr[index] = arr[i] - arr[index];
      				arr[i] = arr[i] - arr[index];
      			}
      		}
      		
      		printArray(arr);
      	}
      	
      	void printArray(int[] array) {
      		for (int i = 0; i < array.length; i++) {
      			System.out.print(array[i] + " ");
      		}
      	}
      	
      	public static void main(String[] args) {
      		int[] arr = {9, 6, 12, 1, 15, 10, 17, 2, 11, 1, 4, 8, 19, 14};
      		SimpleSelectionSort1 selectionSort = new SimpleSelectionSort1();
      		selectionSort.simpleSelectionSort(arr);
      	}
      }
    5. import java.util.ArrayList;
      import java.util.Arrays;
      import java.util.Iterator;
      import java.util.List;
      
      public class SimpleSelectionSort2 {
      	public List<Integer> list = new ArrayList<Integer>();
      	
      	/**
      	 * 递归函数进行简单选择排序--采用list存储新排序的array,不太好
      	 * @param arr  待排序的数组
      	 */
      	void simpleSelectionSort(int[] arr) {
      		int length = arr.length;
      		int i, index;
      		
      		if (length == 1) {
      			list.add(arr[0]);
      			printArray(list);
      			return;
      		}
      		//选择序列中最小元素,下标为index
      		for (i = index = 0; i < length; i++) {
      			if (arr[i] < arr[index]) {
      				index = i;
      			}
      		}
      		
      		//将最小元素与序列中首元素交换
      		if (index != 0) {
      			arr[0] = arr[0] + arr[index];
      			arr[index] = arr[0] - arr[index];
      			arr[0] = arr[0] - arr[index];
      		}
      		
      		list.add(arr[0]);
      		//去除序列中的最小首元素,进行递归调用
      		arr = Arrays.copyOfRange(arr, 1, arr.length);
      		simpleSelectionSort(arr);
      	}
      	
      	/**
      	 * 递归函数进行简单选择排序
      	 * @param array  待排序的数组
      	 * @param startIndex  从startIndex数组下标开始往后排序,忽略startIndex之前的元素
      	 */
      	public void simpleSelectionSortRecursion(int[] array, int startIndex){
      		//递归结束条件
      		if(startIndex == array.length - 1){
      			printArray(array);
      			return;
      		}
      		
      		//假设start元素为最小值
      		int minIndex = startIndex;
      		
      		for(int i = startIndex; i < array.length; i++){
      			if(array[i] < array[minIndex]){
      				minIndex = i;
      			}
      		}
      		
      		//如果start元素就是最小值,则不再交换
      		if (minIndex != startIndex) {
      			array[startIndex] = array[startIndex] + array[minIndex];
      			array[minIndex] = array[startIndex] - array[minIndex];
      			array[startIndex] = array[startIndex] - array[minIndex];
      		}
      		
      		//递归:前面一位已经排序成功,排序startIndex元素往后移一位
      		simpleSelectionSortRecursion(array, startIndex + 1);
      	}
      	
      	void printArray(List<Integer> array) {
      		Iterator iterator = array.iterator();
      		while (iterator.hasNext()) {
      			System.out.print(iterator.next() + " ");
      		}
      	}
      	
      	void printArray(int[] array) {
      		for (int i = 0; i < array.length; i++) {
      			System.out.print(array[i] + " ");
      		}
      	}
      	
      	public static void main(String[] args) {
      		int[] arr = {9, 6, 12, 1, 15, 10, 17, 2, 11, 1, 4, 8, 19, 14};
      		SimpleSelectionSort2 selectionSort2 = new SimpleSelectionSort2();
      		selectionSort2.simpleSelectionSort(arr);
      		
      		System.out.println("\n------------分割线--------------");
      		
      		selectionSort2.simpleSelectionSortRecursion(arr, 0);
      	}
      }
    6. 性能分析

      容易看出,简单选择排序所需进行记录移动的操作次数较少,这一点上优于冒泡排序,最佳情况下(待排序序列有序)记录移动次数为0,最坏情况下(待排序序列逆序)记录移动次数n-1。

      外层循环进行了n-1趟选择,第i趟选择要进行n-i次比较。每一趟的时间:n-i次的比较时间+移动记录的时间(为一常数0或1,可以忽略)。总共进行了n-1趟。忽略移动记录的时间,所以总时间为(n-1)*(n-i)=n^2-(i+1)*n+i。时间复杂度为O(n^2)。不管是最坏还是最佳情况下,比较次数都是一样的,所以简单选择排序平均时间、最坏情况、最佳情况 时间复杂度都为O(n^2)。同时简单选择排序是一种稳定的原地排序算法。当然稳定性还是要看具体的代码,在此就不做深究。

本文转载自:http://blog.csdn.net/touch_2011/article/details/6767673

共有 人打赏支持
pradosoul
粉丝 6
博文 40
码字总数 37445
作品 0
闵行
程序员
JavaScript 、Python Java、Go算法系列之【快速排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 选择排序 选择排序是一种简单直观的排序算法,无论什么数据进去都...

湖南小影 ⋅ 2017/05/15 ⋅ 0

JavaScript 、Python Java、Go算法系列之【快速排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 选择排序 选择排序是一种简单直观的排序算法,无论什么数据进去都...

湖南小影 ⋅ 2017/05/15 ⋅ 0

JavaScript 、Python Java、Go算法系列之【快速排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 快速排序 选择排序是一种简单直观的排序算法,无论什么数据进去都...

湖南小影 ⋅ 2017/05/15 ⋅ 0

JavaScript ,Python,java,Go系列算法之选择排序

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 选择排序 选择排序是一种简单直观的排序算法,无论什么数据进去都...

湖南小影 ⋅ 2017/05/10 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

5Python全栈之路系列之算法

ython全栈之路系列之算法 一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 冒泡排序 冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访...

余二五 ⋅ 2017/11/15 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Greys Java在线问题诊断工具

https://github.com/oldmanpushcart/greys-anatomy/wiki/greys-pdf#command-monitor

素雷 ⋅ 14分钟前 ⋅ 0

git从远程仓库拉取代码的常用指令

一种(比较麻烦的)拉代码的方法 git clone //克隆代码库,与远程代码库的主干建立连接,如果主干已经在就不用再clone啦,克隆路径为当前路径下的新创建的文件夹 git checkout -b //本地建立...

Helios51 ⋅ 29分钟前 ⋅ 0

005. 深入JVM学习—Java堆内存参数调整

1. JVM整体内存调整图解(调优关键) 实际上每一块子内存区域都会存在一部分可变伸缩区域,其基本流程:如果内存空间不足,则在可变的范围之内扩大内存空间,当一段时间之后,内存空间不紧张...

影狼 ⋅ 34分钟前 ⋅ 0

内存障碍: 软件黑客的硬件视图

此文为笔者近日有幸看到的一则关于计算机底层内存障碍的学术论文,并翻译(机译)而来[自认为翻译的还行],若读者想要英文原版的论文话,给我留言,我发给你。 内存障碍: 软件黑客的硬件视图...

Romane ⋅ 今天 ⋅ 0

SpringCloud 微服务 (七) 服务通信 Feign

壹 继续第(六)篇RestTemplate篇 做到现在,本机上已经有注册中心: eureka, 服务:client、order、product 继续在order中实现通信向product服务,使用Feign方式 下面记录学习和遇到的问题 贰 or...

___大侠 ⋅ 今天 ⋅ 0

gitee、github上issue标签方案

目录 [TOC] issue生命周期 st=>start: 开始e=>end: 结束op0=>operation: 新建issueop1=>operation: 评审issueop2=>operation: 任务负责人执行任务cond1=>condition: 是否通过?op3=>o......

lovewinner ⋅ 今天 ⋅ 0

浅谈mysql的索引设计原则以及常见索引的区别

索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索...

屌丝男神 ⋅ 今天 ⋅ 0

String,StringBuilder,StringBuffer三者的区别

这三个类之间的区别主要是在两个方面,即运行速度和线程安全这两方面。 首先说运行速度,或者说是, 1.执行速度 在这方面运行速度快慢为:StringBuilder(线程不安全,可变) > StringBuffer...

时刻在奔跑 ⋅ 今天 ⋅ 0

java以太坊开发 - web3j使用钱包进行转账

首先载入钱包,然后利用账户凭证操作受控交易Transfer进行转账: Web3j web3 = Web3j.build(new HttpService()); // defaults to http://localhost:8545/Credentials credentials = Wallet......

以太坊教程 ⋅ 今天 ⋅ 0

Oracle全文检索配置与实践

Oracle全文检索配置与实践

微小宝 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部