最近,在通过《算法4》这本书来重新学习一下算法,从最初级的排序算法。初级的排序算法有3种:选择排序、插入排序、希尔排序。
选择排序
假定我们有一组没有顺序的数组,如{5,8,1,7,3,9,4,6}。那么,选择排序是这样的:
1、找到这个数组中最小的元素,然后与第一个元素交换;
2、在剩下的元素中找到最小的元素,与第二个元素交换;
如此重复,直至整个数组中的所有元素都按顺序排列,这样的方法就被称为选择排序。
简单排序如果用java来实现的话是这样的。
选择排序
pubic class Selection{
public static void sort(int[] numbers){
int length = numbers.length;
for(int i = 0; i < N; i++){
int min = i; //最小的数从第i位开始排起
for(int j = i+1; j < N ; j++){
//循环判断,获取最小的数值的下标
if(numbers[min] > numbers[j]){
min = j;
}
}
//更换最小值的位置
int t = numbers[i];
numbers[i] = numbers[min];
numbers[min] = t;
}
//打印出重新排序后的数值
for(int i : numbers)
System.out.print(i + " ");
}
}
其实,这和我们用眼睛在一堆数字里面找最小值没什么区别,而这个算法只是把找的步骤完整的复述出来而已。
插入排序
玩过扑克牌的知道,每一次抽牌,我们都会把牌插入手里牌组中合适的位置。而在计算机中,每次数据要插入的时候,都得先移动一下已有的数据,腾出一个空间来给这个数据插入。比如,在一个有序的数据集【1,5,8,15】中,要插入【6】,我们可以直观的看出是插入在5和8之间。但是,在计算机中,它是一个固定数组,由固定的4个空间存放这四个数字,如果要插入6,就必须把8和15往后移动一个空间,腾出来的位置才能插入6。
从这里可以看出,每一次的插入排序其实是把拿到的数字去与已经排好顺序的数组(即使一开始没有排好序的数组也不影响)进行对比,然后把它插入到合适的顺序中。
用代码说事
插入排序
public void insertionSort(){
int[ ] a = new int[ ]{3,6,9,1,5,2,8};
int len = a.length;
for(int i=1;i<len;i++){
for(int j=i; j>0 && a[j] < a[j-1]; j--){
int k = a[j];
a[j] = a[j-1];
a[j-1] = k;
}
}
for(int b : a){
System.out.print(b+" ");
}
}
首先,第一个数不进行排序,从第二个数开始,当这个数小于它的前一个数时,则两个数交换位置。交换完后通过j--继续与前一个数进行比较,直至找到合适的位置。然后再用第三个数进行比较,直接全部排序完。这样就通过插入排序得到了一个从小到大的数组。
因为插入排序每次只能比较合交换相邻的两个数字,如果数据规模过大的话,效率就显得很低了。
希尔排序
希尔排序是在插入排序的基础上做一定改进来加快排序的速度。
希尔排序
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
//通过不断除以3,得到一个比N/3略大的数 h
while(h < N/3){
h = 3 * h + 1;
}
while(h >= 1){
for(int i = h;i < N ; i++){
for(int j = i ;j >= h && a[j] < a[j-h]; j -= h){
int k = a[j];
a[j] = a[j-h];
a[j-h] = k;
}
}
h = h/3;
}
}
}
希尔排序本质上还是插入排序,区别在于希尔排序一开始是把整个数组分成了若干份(这若干份数组中的元素在整个大数组中是间隔的,间隔距离是h),对这若干份先一一进行排序,然后再重新分成更少的若干份,再进行排序,直到最后只剩下一份,也就是整个数组时,这时候整个数组的排序已经接近我们想要的排序了,进行一次插入排序,需要移动的元素就很少了。相对来说,也就比直接使用插入排序会高效很多。