[排序基础]选择排序法SelectionSort
/**
* 排序算法 O(N^2)
*
* @author Cindy
* @version $Id SelectionSort.java, v 0.1 2018-04-23 20:54 Administrator Exp $$
*/
public class SelectionSort {
public static void swap(int [] arr,int i,int j){
int t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void sort(int[] arr){
int n=arr.length;
for (int i = 0; i < n; i++) {
// 寻找[i, n)区间里的最小值
int minIdex=i;
for (int j = i+1; j <n ; j++) {
if(arr[j]<arr[minIdex]){
minIdex=j;
}
}
swap(arr,i,minIdex); // 交换 当前轮最小值
}
}
public static void main(String[] args) {
int[] arr = {10,9,8,7,6,5,4,3,2,1};
SelectionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]+" ");
}
}
测试结果：
1、2、3、4、5、6、7、8、9、10
选择排序在第i轮（i从0开始），找到 [i, n) 这个区间里的最小值，之后和第i个元素交换位置。也就是外循环每轮只会交换元素一次，内循环的目的是找到[i, n)范围内的最小元素。
以数组：10, 15, 9, 13, 8，为例一共5个元素。
首先找到索引是 [0, 5) 这个区间里的最小元素，即8。如下图所示：
[10, 15, 9, 13, 8]
之后将8和第0个元素，即10交换位置，得到：
8, 15, 9, 13, 10
之后，找到索引是 [1, 5) 这个区间里的最小元素，即9。如下图所示：
8, [15, 9, 13, 10]
之后将9和第1个元素，即15交换位置，得到：
8, 9, 15, 13, 10
之后，找到索引是 [2, 5) 这个区间里的最小元素，即10。如下图所示：
8, 9, [15, 13, 10]
之后将10和第2个元素，即15交换位置，得到：
8, 9, 10, 13, 15
之后，找到索引是 [3, 5) 这个区间里的最小元素，即13。如下图所示：
8, 9, 10, [13, 15]
之后将13和第3个元素，即13交换位置(就是自己)，得到：
8, 9, 10, 13, 15
其实到这里，排序已经完成了，因为只剩下最后一个元素，此时一定是最大的元素。当然，在程序上，再多做一步，并没有关系，即：
找到索引是 [4, 5) 这个区间里的最小元素，即15。如下图所示：
8, 9, 10, 13, [15]
之后将15和第4个元素，即15交换位置(就是自己)，得到：
8, 9, 10, 13, 15
上面的排序算法，只能针对一种Integer类型的数字进行排序，如果在进行浮点型数组，双精度类型数组等类型来排序，就不适用了。在这里，我们可以利用模板（泛型）的方式来进行算法编程。
示例：
Student.class
/**
* 学生类型
* 姓名，成绩。
* 按照成绩排序，若相等，则根据姓名字母排序
* 若成绩不相等，则按照成绩高的考前排序
* @author Cindy
* @version $Id Student.java, v 0.1 2018-04-23 22:17 Cindy Exp $$
*/
public class Student implements Comparable<Student>{
private String name;
private int score;
public Student() {
}
public Student(String name, int score) {
this.name = name;
this.score = score;
}
/**
* 重写Student的compareTo函数
* if the scores are equal,
* sort them according to the alphabetic order of the names.
* if the scores are not equal, the score is high.
* @param other
* @return
*/
@Override
public int compareTo(Student other) {
if(this.score==other.score){
return this.name.compareTo(other.name);
}
if(this.score<other.score){
return 1;
}else if(this.score>other.score){
return -1;
}else // this.score==other.score
return 0;
}
// 定义Student实例的打印输出方式
@Override
public String toString() {
return "Student{" +
"name='" + this.name + '\'' +
", score=" + Integer.toString(this.score) +
'}';
}
}
SelectionSortTemplet.Class
/**
* 排序算法 O(N^2)
* 为了是排序算法更加灵活，我们可以使用模板（泛型）编写算法
* @author Cindy
* @version $Id SelectionSortTemplet.java, v 0.1 2018-04-23 20:54 Cindy Exp $$
*/
public class SelectionSortTemplet {
public static void swap(Object [] arr,int i,int j){
Object t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void sort(Comparable[] arr){
int n=arr.length;
for (int i = 0; i < n; i++) {
int minIdex=i;
for (int j = i+1; j <n ; j++) {
if(arr[j].compareTo(arr[minIdex])<0){
minIdex=j;
}
}
swap(arr,i,minIdex);
}
}
public static void main(String[] args) {
// 测试Integer
Integer[] a = {10,9,8,7,6,5,4,3,2,1};
SelectionSortTemplet.sort(a);
for( int i = 0 ; i < a.length ; i ++ ){
System.out.print(a[i]+" ");
}
System.out.println();
// 测试Double
Double[] b = {4.4, 3.3, 2.2, 1.1};
SelectionSortTemplet.sort(b);
for( int i = 0 ; i < b.length ; i ++ ){
System.out.print(b[i]);
System.out.print(' ');
}
System.out.println();
// 测试String
String[] c = {"D", "C", "B", "A"};
SelectionSortTemplet.sort(c);
for( int i = 0 ; i < c.length ; i ++ ){
System.out.print(c[i]);
System.out.print(' ');
}
System.out.println();
// 测试自定义的类 Student
Student[] d = new Student[4];
d[0] = new Student("D",90);
d[1] = new Student("C",100);
d[2] = new Student("B",95);
d[3] = new Student("A",95);
SelectionSortTemplet.sort(d);
for( int i = 0 ; i < d.length ; i ++ ){
System.out.println(d[i]);
}
}
}
测试结果：
1 2 3 4 5 6 7 8 9 10
1.1 2.2 3.3 4.4
A B C D
Student{name='C', score=100}
Student{name='A', score=95}
Student{name='B', score=95}
Student{name='D', score=90}
