选择排序

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