奔走在算法的大路上（一）排序之选择排序

清疚 2022-08-07 12:35 6阅读 0赞

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法交租选择排序。

推荐维基百科的解释：[选择排序][Link 1]

package Sort;
 /**
 * 
 * Description: 选择排序
 * 
 * @author zhangjunshuai
 * @version 1.0
 * Create Date: 2015年4月6日 上午11:12:37
 * Project Name: ArithMetic
 *
 * <pre>
 * Modification History: 
 * Date Author Version Description 
 * ----------------------------------------------------------------------------------------------------------- 
 * LastChange: $Date:2015年4月6日 $ $Author: zhangjunshuai$ $Rev:1.0 $ 
 * </pre>
 *
 */
 public class Selection {
 	
 	public static void sort(Comparable[] a){
 		for(int i=0;i<a.length;i++){
 			for(int j = a.length-1;j>i;j--){
 				if(less(a[j],a[i]))
 					exch(a,j,i);
 			}
 			show(a);
 		}
 		
 	}
 	
 	
 	/**
 	 * 
 	 * 是否小于
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:14:52
 	 * @param v
 	 * @param w
 	 * @return
 	 */
 	private static boolean less(Comparable v,Comparable w){
 		return v.compareTo(w)<0;
 	}
 	/**
 	 * 
 	 * 交换函数
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:14:32
 	 * @param a
 	 * @param i
 	 * @param j
 	 */
 	private static void exch(Comparable[] a,int i ,int j){
 		 Comparable t = a[i];
 		 a[i] = a[j];
 		 a[j] = t;
 	 }
 	/**
 	 * 
 	 * 打印输出
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:19:03
 	 * @param a
 	 */
 	private 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 = {1,3,4,5,6,7,3,4,3,45,78,1,26,9,9,6,1};
 		sort(a);
 		/*Character[] b = {'a','b','d','w','e','f','g','y','u','t','q','s','d','l','j','g','g','z'};
 		sort(b);*/
 	}
 }

执行结果（注意每次的顺序）：

![Center][]

[Link 1]: http://zh.wikipedia.org/wiki/选择排序
[Center]: /images/20220805/873d2eeb379b438e8af93f824c7504f2.png