06.19 算法——初级排序算法

最近，在通过《算法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

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），对这若干份先一一进行排序，然后再重新分成更少的若干份，再进行排序，直到最后只剩下一份，也就是整个数组时，这时候整个数组的排序已经接近我们想要的排序了，进行一次插入排序，需要移动的元素就很少了。相对来说，也就比直接使用插入排序会高效很多。