文档章节

选择排序算法

i
 iphoenix
发布于 2017/02/07 16:32
字数 248
阅读 5
收藏 0
package com.sort;

/**
 * 选择排序算法
 * 首先,找到数组中最小的那个元素,其次,将它和数组的第1个元素交换位置。
 * 再次,在剩下的元素中找到最小的元素,将它与数组的第2个元素交换位置。
 * 如此往复,直到将整个数组排序。
 * 
 * 时间复杂度
 * 平均情况:O(n2), 最好情况:O(n2), 最坏情况:O(n2)
 * 
 * 空间复杂度
 * 辅助存储:O(1)
 * 
 * 稳定性:不稳定
 * 
 */

public class SelectSort {
	public static void sort(Comparable[] a) {
		int size = a.length;
		for(int i=0; i<size; i++) {
			int min = i;
			for(int j=i+1; j<size; j++) {
				if(less(a[j], a[min])) {
					min = j;
				}
			}
			swap(a, i, min);
		}
		
	}
	
	private static boolean less(Comparable v, Comparable w) {				
		return v.compareTo(w) < 0;
	}
	
	private static void swap(Comparable[] a, int i, int j) {
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public static void show(Comparable[] a) {
		for(int i=0; i<a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		Integer[] a = {2, 34, 17, 54, 90, 20, 1, 5, 8};
		sort(a);
		show(a);
	}
}

 

© 著作权归作者所有

i
粉丝 4
博文 59
码字总数 21063
作品 0
海淀
私信 提问

暂无文章

3_数组

3_数组

行者终成事
19分钟前
2
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部