《算法图解》-2 选择排序

一 数组和链表

    作者一计算机的内存为例，介绍常用的数据结构数组跟链表。

 计算机内存犹如一大堆抽屉（就是一些存储地址）。

 需要存储多个元素时，可使用数组或链表。

 数组的元素都在一起，数组索引是从0开始计算的。

 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。

 数组的读取速度很快。

 链表的插入和删除速度很快。

 在同一个数组中，所有元素的类型都必须相同（都为int、double等）。

操作时间如下：

  

二 选择排序

   

你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？

遍历是一种办法（不是很快的办法，更好的快速排序在下一章介绍）。

作者介绍了这种办法的速度是O（n2）.并且解释了为什么忽略1/2的这样的常数。

实例代码如下：

思路很容易理解，就是找出数组里面最小的数对应的索引，然后弹出来到新数组，重复执行就得到有序的新数据了，很不巧啊，java 数组不支持这种pop操作。换个思路：转成list，遍历list，然后list.remove，在吧list.toarry形成新数组。

还有我找个临时map存放已经排好序的数的位置，遇到就跳过，模拟删除了。

public class SelectSort {
	
	 static Map alreadymap = new HashMap();
	public static int findsmall(int[] nums,Map alreadymap){
		
		int smallest = nums[0];
		int index = 0;
		//找到最小
		for(int i=0; i<= nums.length-1;i++){
			//已排序的过滤掉
			if(alreadymap.containsKey(i)){
				if(smallest == nums[i]){					
					smallest = nums[i+1];
					continue;
				}
				continue;
			}
		
			if(smallest >=nums[i]){
				smallest = nums[i];
				index = i;				
			}			
		}
		alreadymap.put(index, index);
		System.out.println(index+":"+nums[index]);
		return index;
	}
	
	public static int[] selectSort(int [] nums){
		
		int [] res = new int[5];
		
		for(int i=0;i<= nums.length-1;i++ ){
			int smalllest = findsmall(nums,alreadymap);
			res[i] = nums[smalllest];			
		}
		return res;
	}
	

	public static void main(String[] args) {
		int [] test = {5,3,6,2,10};
		int[] res = selectSort(test);
		System.out.println(JSON.toJSON(res));
	}

}

输出：

  3:2
1:3
0:5
2:6
4:10
[2,3,5,6,10]