Java排序之直接插入排序、希尔排序、冒泡排序、快速排序（持续更新）

注：java排序我会用Integer数组进行演示，这样就纯粹的研究排序，如果使用别的类型来需要compareTo()方法进行对象大小比较，这样在一定的情况下会影响同学们的理解。

插入排序：直接插入排序、折半插入排序、希尔排序

交换排序：冒泡排序、快速排序。

直接插入排序

插入排序的原理是将一个数与一个有序的序列进行比较，然后再将其插入这个有序的序列中。所以第一次讲序列的前两个值进行比较进行排序，然后第三个值再与这个序列进行比较，直到结束。

private static void insertSort(Integer[] table) {
        
        for (int i = 1; i < table.length; i++) {
            int temp=table[i];
            int j;
            for (j = i-1; j>=0 && temp<table[j]; j--) {
                table[j+1]=table[j];
                    
            }
            table[j+1]=temp;
        }
    }

希尔排序

希尔排序，是将一个序列的长度/2，当作比较的距离叫做增量（取变量名为detal）。将i和i+detal的值进行比较，将如果i所处的位置值大于i+detal的值，两个就换位置。一次循环之后，再将detal/2，依次进行操作，知道detal=1，越接近1时，数组就会越趋于有序。

private static void shellSort(Integer[] table) {
        
        for (int detal = table.length/2; detal>0; detal=detal/2) {
            
            
            for (int i = detal; i < table.length; i++) {
                
                int temp=table[i];
                
                int j;
                
                for ( j = i-detal; j>=0 && temp<table[j]; j-=detal) {
                    table[j+detal]=table[j];
                }
                table[j+detal]=temp;
            }
            
        }
    }

冒泡排序

    冒泡排序的原理是遍历数组中的数据并在相邻的进行比较，如果当前位置i的值大于i+1的值，就换位置。如果当前位置的值小于i+1的值，就不变。这样每次循环都会确定最后以为的最大的数字。

第一次遍历之后，就会确定数组最大的值在最后面。

第二次遍历的时候，就会确定数组中倒数第二个值在正确的位置（倒数第二位上）。

来吧，贴测试代码喽~

        Integer[] intArray={1,20,39,23,45,63,35,12,56,92,34,56,15};
        Integer temp=0;
        int len=intArray.length;
        for (int i = 0; i < len; i++) {
           
            for (int j = 0; j < len-i-1; j++) {
            
                if (intArray[j]>intArray[j+1]) {
                    temp=intArray[j];
                
                    intArray[j]=intArray[j+1];
                
                    intArray[j+1]=temp;
                
                }
            }
        }

解释一下：为什么是j < len-i-1？首先是关注“1”的问题，因为我写代码的问题，如果不-1会造成数组越界。

                 为什么要-i，刚才已经提到了，每一次遍历都会确定一个最大值，所以-i可以减少递归的次数。

快速排序：

因为冒泡排序，每次值的交换都会进行三次赋值，加入冒泡排序的第一个数据是最大值，那么第一次遍历，这个值就会移动length-1次，存在重复数据移动，快速排序算法是希望尽可能的减少这种重复的数据移动。

快速排序的基本思想：

在数据序列中选择一个值作为比较的基准值，每趟数据序列的两端开始交替进行。

以代码举例Integer[] intArray,将第一个值作为基准值取名为vot，两端i=0，j=intArray.length-1;

如果intArray[j]>=vot，那么没有任何操作，并且j--，继续从用intArray[j]与vot进行比较;

用vot和j比较，如果intArray[j]<=vot,那么intArray[j]就移动到i的位置上，并且i++；

并且下一次用i与vot比较，如果intArray[i]>vot,那么intArray[i]就移动到j的位置，并且j--，并在j那边进行比较;

如果intArray[i]<=vot，那么没有任何操作，并且i++,继续从用intArray[i]与vot进行比较;

直至i==j，第一次遍历结束，intArray[i]=vot；

这样结束下来，标准值vot左边都是小于自己的，右边都是大于自己的。再讲左边和右边分别看成一个集合再进行如此操作，当最后每个集合不可分割时，就结束了。

图示：

    为了让大家更好的了解，也是为了让我自己温习时能更好的理解，我画了一个图示。 

图中我把移动的数据以“”来表示，其实正常是不需要的，为什么要这样，是为了让大家理解的时候更加简单。因为整个数列里面，空的值都是无效的，最终都会被替换掉。

下面是是代码实例，注意这里while和if的用法，很强大，比我自己写的强的很多~自己根据理解写了一下，受益匪浅。

public static void main(String[] args) {
        Integer[] table={4,1,7,3,2,5,6};
        quickSort(table,0,table.length-1);
    }

    /**
    * @Title: quickSort
    * @Description: TODO(快速排序)
    * @param @param table  排序的数组
    * @param @param begin  开始排序的数组下标
    * @param @param end    结束排序的数组下标
    * @return void    返回类型
    * @author guojian 
    * @throws
    
    */
    private static void quickSort(Integer[] table, int begin, int end) {
        //判断比较的数组是否长度为1(数组长度逐步分解为1时，停止快速排序)
        if (begin<end) {
            int i=begin;
            int j=end;
            int vot=table[i];//设定标准值
            
            while(i<j){
                //判断标准值与j的大小，如果vot<=table[j],就一直执行j--操作。
                //如果大于，就将table[j]移动到i的位置上，并且i++，然后再从i端与vot进行比较
                while (i<j && vot <=table[j]) {
                    j--;
                }
                
                if (i<j) {
                    table[i++]=table[j];
                }
                //判断标准值与i的大小，参考上方注释
                while (i<j && table[i] <=vot){
                    i++;
                }
                if (i<j) {
                    table[j++]=table[i];
                }
                
            }
            table[i]=vot;
            quickSort(table,begin,j-1);//标准值前面的序列再进行排序
            quickSort(table,i+1,end);//标准值后面的序列再进行排序
        }
        
    }