我将会写一系列关于算法的博客，因为我是程序员，并不是计算机科学家，也即我是搞工程的，并不是搞学术的，所以对于我来说，最重要的就是
1.有哪些算法
2.这些算法的原理
3.这些算法的实现
4.这些算法的效率
而其他的，相对而言，并没有那么重要，比如算法的证明，所以以后的博客都会按照上述的思维撰写。
一、首先定义一个抽象类，里面集成了排序算法所需要的共同的方法：
public abstract class SortBase {
public abstract Integer[] sort(Integer[] a);
public static void print(Integer[] arrayForSort) {
System.out.print("[");
for(int i=0;i<arrayForSort.length;i++) {
if(i == arrayForSort.length - 1) {
System.out.print(arrayForSort[i]);
} else {
System.out.print(arrayForSort[i] + " ,");
}
}
System.out.println("]");
}
public static void print(String prefix,Integer[] arrayForSort) {
System.out.print(prefix + ": ");
System.out.print("[");
for(int i=0;i<arrayForSort.length;i++) {
if(i == arrayForSort.length - 1) {
System.out.print(arrayForSort[i]);
} else {
System.out.print(arrayForSort[i] + " ,");
}
}
System.out.println("]");
}
}
二、选择排序：
选择排序可以说是最简单的一种排序方法：
1.找到数组中最小的那个元素
2.将最小的这个元素和数组中第一个元素交换位置
3.在剩下的元素中找到最小的的元素，与数组第二个元素交换位置
重复以上步骤，即可以得到有序数组。
代码如下：
public class SelectionSort extends SortBase {
public Integer[] sort(Integer[] a) {
print("init",a);
Integer minIndex = 0;
Integer temp = 0;
for(int i=0;i<a.length;i++) {
minIndex = i;
for(int j=i+1;j<a.length;j++) {
if(a[j] < a[minIndex]) {
minIndex = j;
}
}
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
print((i+1) + "",a);
}
return a;
}
public static void main(String[] args) {
Integer[] a = {2,1,5,9,0,6,8,7,3};
print("result",(new SelectionSort()).sort(a));
}
}
我在代码中打出了每次排序的结果，运行结果如下:
init: [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]
1: [0 ,1 ,5 ,9 ,2 ,6 ,8 ,7 ,3]
2: [0 ,1 ,5 ,9 ,2 ,6 ,8 ,7 ,3]
3: [0 ,1 ,2 ,9 ,5 ,6 ,8 ,7 ,3]
4: [0 ,1 ,2 ,3 ,5 ,6 ,8 ,7 ,9]
5: [0 ,1 ,2 ,3 ,5 ,6 ,8 ,7 ,9]
6: [0 ,1 ,2 ,3 ,5 ,6 ,8 ,7 ,9]
7: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
8: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
9: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
result: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
效率：对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换。也即最好、最差、平均时间效率均为O（n²），只需要一个辅助变量帮助交换元素。
选择排序可以看成是冒泡排序的扩展，一个是把最小或最大的选出来，再交换，一个是一直交换直到最大最小的出现在正确的位置上，选择排序相对于冒泡排序，比较次数是一样的，但是交换次数要少很多。
三、插入排序：
插入排序类似整理扑克牌，将每一张牌插到其他已经有序的牌中适当的位置。
插入排序由N-1趟排序组成，对于P=1到N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。