最近在读java数据结构与算法，很老的一本书了，正在学习第三章简单排序，将所得记录下来。

（一）冒泡排序

这种排序最简单也最容易理解，最基本的规则：1，从第一个位置开始，比较与下个位置的数据大小；2，如果第二个位置大，则交换位置；3，向右移动一个位置，重复第一个步骤。

这样进行到最后，虽然没有全部排好序，但是确保把最大的数放到了最后。之所以成为冒泡，就是因为在算法执行的过程中，最大的数总是‘冒泡’到最右端。4，当碰到第一个排定后，

就返回到最左端开始下一组排序，不断执行这一过程，知道所有数据都排定。

public class BubbleSort {    public static void sort(int[] array){        int temp =0;        for (int i = array.length-1;i>0;i--){            for(int j=0;j
     
      array[j+1]){                    temp = array[j];                    array[j] = array[j+1];                    array[j+1] = temp;                }            }        }    }    public static void main(String[] args) {        int[] array = {1,2,30,6,3,5,6,8,9,0,12,15};        sort(array);        for(int a:array){            System.out.print(a + "  ");        }    }}
     

结果：

效率问题：比如数组的长度为N，则第一次比较了（N-1）次，第二次比较了（N-2）次，依次到最后1次，则（N-1）+(N-2)+（N-3）+···+1=N*（N-1）/2,大约为N^2/2次比较，对于随机数据，大约进行了N^2/4次交换，对于较大的N,比较和交换的都需O（N^2）时间级别，效率很低。

（二）选择排序

选择排序是对冒泡排序的改进，将交换次数降低到O(N),但是比较次数依然是O（N^2）。最基本的规则是对于数组N：1，从最左端开始，两两比较，标记这N个位置中的最小数；2将最小位置数与最左端数进行交换，则第一个数已经排定；3，接下来是数组N-1，重复步骤1，则从小到大依次排定。

public class SelectSort {        public static void sort(int[] array){        int index = 0;        int value = 0;        for(int i=0;i
     
       array[j]){                    index = j;                    value = array[j];                }            }            value = array[i];            array[i] = array[index];            array[index] = value;        }    }    public static void main(String[] args){        int[] array = {1,2,30,6,3,5,6,8,9,0,12,15};        sort(array);        for(int a:array){            System.out.print(a + "  ");        }    }}
     

结果：

（三）插入排序

学习插入排序之前要了解局部有序的概念，在数组中，假定标记某个下标，左边的数组都是有序的，右边的数组是无序的，则称这个数组局部有序；

插入排序就利用这个理念，对于标记的数，它插入到左端有序数组中，需要找到合适位置，将它放到合适位置，左端有序数组合适位置右端的数都要往后移一位，这样就做到往局部

有序中插入了一位，然后标记数右移，依次进行。

 

public class InsertSort {        public static void sort(int[] array){        int value;        int index;        for(int i = 0;i
     
      0&&array[index-1]>value){                array[index] = array[index-1];                index--;            }            array[index] = value;        }    }    public static void main(String[] args) {        int[] array = {1,2,30,6,3,5,7,6,8,9,0,12,15};        sort(array);        for(int a:array){            System.out.print(a + "  ");        }    }}
     

结果：

 效率：O（N^2)，一般情况下比冒泡排序快一倍，也比选择排序快一些。