title: 选择排序算法.md
date: 2017-11-06 20:06:48
tags:
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 {\displaystyle n} n个元素的表进行排序总共进行至多 {\displaystyle n-1} {\displaystyle n-1}次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。维基百科
代码实现如下
package cai.suanfa;
/**
* Created by caiyl on 2017/11/5.
* 选择排序
*/
public class SelectSort extends TempSort{
private Integer[] arr = {9,2,1,7,3,8};
public static void main(String[] args) {
SelectSort selectSort = new SelectSort();
selectSort.sort(selectSort.arr);
selectSort.show(selectSort.arr);
}
@Override
public void sort(Comparable[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if (isLess(arr[j],arr[min])) {
min = j;//找出最小元素的位置
}
}
exch(arr,i,min);//交换
}
}
}
package cai.suanfa;
/**
* Created by caiyl on 2017/11/5.
*/
public abstract class TempSort {
/**
* 打印排序过的数据
* @param arr
*/
public void show(Comparable [] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
/**
* v1是否小于v2
* @param v1
* @param v2
* @return
*/
public boolean isLess(Comparable v1, Comparable v2){
return v1.compareTo(v2) < 0;
}
/**
* v1是否大于v2
* @param v1
* @param v2
* @return
*/
public boolean isGreater(Comparable v1, Comparable v2){
return v1.compareTo(v2) > 0;
}
public void exch(Comparable[] arr,int i, int j){
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
protected abstract void sort(Comparable[] arr);
}
