1.选择排序算法
/***
* 排序算法：选择排序算法
* 实现过程：
* 1.找到数组中最小的那个元素
* 2.将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）
* 3.在剩下的元素中找到最小的元素，将它与数组的第二个元素交换
* 4.一直循环 步骤3， 直到整个数组排序完成。
*
* 特点：
* 1.对于长度为N的数组，选择排序需要大约N ＊ N ／ 2 次比较和N 次交换
* 2.运行时间与输入顺序无关。（有序的和无序的，排序所用时间是一样的）
* 3.数据移动是最少的。（每次交换都会改变两个数组元素的位置，因此选择排序用了N次交换）
* 4.当前索引左边的元素是有序的
*/
// i min 0 1 2 3 4 5 6 7 8 9 10
// 0 6 A O R T E X S M P L E
// 1 4 A E R T O X S M P L E
// 2 10 A E E T O X S M P L R
// 3 9 A E E L O X S M P T R
// 4 7 A E E L M X S O P T R
// 5 7 A E E L M O S X P T R
// 6 8 A E E L M O P X S T R
// 7 10 A E E L M O P R S T X
// 8 8 A E E L M O P R S T X
// 9 9 A E E L M O P R S T X
// 10 10 A E E L M O P R S T X
public class Selection {
//排序算法实现 (升序)
public static void sort(Comparable[] a) {
int N = a.length; //数组长度
System.out.print(" i min");
for (int i = 0; i < N; i++) {
System.out.printf(" %2d" , i);
}
System.out.println();
for (int i = 0; i < N; i++) {
int min = i; //min保存最小数的数组下标
for (int j = i + 1; j < N; j++) //找出a[i+1 ... N-1]中最小的数
if (less(a[j], a[min]))
min = j;
exch(a, i, min); //交换a[i]和a[i+1 ... N-1]中最小的数
System.out.printf("%2d %3d ", i, min);
show(a);
}
}
// 判断第一个数是否大于第二个数
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// 交换两个数的位置
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
// 打印数组
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
// 判断是否已排序
public static boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
if (less(a[i], a[i-1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
//String[] a = {"S", "E", "L", "E", "C", "T", "I", "O", "N", "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
sort(a); //排序
assert isSorted(a); //判断数组是否有序
//show(a); //打印数组
}
}
2.选择排序算法的轨迹图
/***
*
* @author xiaoo_gan
* 选择排序的轨迹图
* 2.1.1 按照算法Selection给出插入排序是如何将数组 E A S Y Q U E S T I O N 排序的。
*/
public class TraceSelection {
public static void sort(String[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
draw(a, i, i, min);
exch(a, i, min);
}
}
private static boolean less(Comparable a, Comparable b) {
return (a.compareTo(b) < 0);
}
private static void exch(String[] a, int i, int j) {
String swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private static void header(String[] a) {
int N = a.length;
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.text(N / 2.0, -3, "a[]");
StdDraw.text(-2.50, -2, "i");
StdDraw.text(-1.25, -2, "min");
for (int i = 0; i < N; i ++) {
StdDraw.text(i, -2, i + "");
}
StdDraw.setPenColor(StdDraw.BOOK_RED);
StdDraw.line(-3, -1.65, N-0.5, -1.65);
StdDraw.setPenColor(StdDraw.BLACK);
for (int i = 0; i < a.length; i++) {
StdDraw.text(i, -1, a[i]);
}
}
private static void footer(String[] a) {
StdDraw.setPenColor(StdDraw.BLACK);
for (int i = 0; i < a.length; i++) {
StdDraw.text(i, a.length, a[i]);
}
}
private static void draw(String[] a, int row, int ith, int min) {
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.text(-2.50, row, ith + "");
StdDraw.text(-1.25, row, min + "");
for (int i = 0; i < a.length; i++) {
if (i == min) {
StdDraw.setPenColor(StdDraw.BOOK_RED);
} else if (i < ith) {
StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
} else {
StdDraw.setPenColor(StdDraw.BLACK);
}
StdDraw.text(i, row, a[i] + "");
}
}
public static void main(String[] args) {
String s = args[0];
int N = s.length();
String[] a = new String[N];
for (int i = 0; i <N; i++) {
a[i] = s.substring(i, i + 1);
}
StdDraw.setCanvasSize(30 * (N + 3), 30 * (N + 3));
StdDraw.setXscale(-3, N + 1);
StdDraw.setYscale(N + 1, -3);
StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
header(a);
sort(a);
footer(a);
}
}
