选择排序

原创
2014/08/19 17:52
阅读数 139
package com.victor.sort.algorithms;

import java.util.ArrayList;
import com.victor.sort.seeds.*;

/**
 * 选择排序
 * @author 黑妹妹牙膏
 *
 */
public class Selection extends SortAlgorithms {

	/**
	Algorithm
	for i = 1:n,
	    k = i
	    for j = i+1:n, if a[j] < a[k], k = j
	    → invariant: a[k] smallest of a[i..n]
	    swap a[i,k]
	    → invariant: a[1..i] in final position
	end
	Properties
	■Not stable 
	■O(1) extra space 
	■Θ(n2) comparisons 
	■Θ(n) swaps 
	■Not adaptive 
	Discussion
	From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic. 

	However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice. 
	*/
	
	@Override
	protected ArrayList<Integer> doSort(ArrayList<Integer> Alist) {
		ArrayList<Integer> a = Alist;
		int n = a.size();
		int k = 0;
		for(int i=0;i<n;i++)
		{
			k = i;
			for(int j = i+1;j<n;j++)
			{
				if(a.get(j)<a.get(k))
				{
					k=j;
				}
			}
			int temp = a.get(i);
			a.set(i, a.get(k));
			a.set(k,temp);
			moveMentIncrease();
		}
		return a;
	}

	@Override
	public String getName() {
		return "Selection";
	}
	
	public static void main(String[] args)
	{
		Seeds seed1 = new Random();
//		Seeds seed2 = new NearSorted();
//		Seeds seed3 = new Reversed();
//		Seeds seed4 = new FewUniqueKeys();
		SortAlgorithms SA = new Selection();
		SA.sort(seed1,20);
		SA.print();
//		SA.sort(seed2,10000);
//		SA.sort(seed3,10000);
//		SA.sort(seed4,10000);
	}

}


展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部