排序（冒泡，插入，希尔，归并，选择，快速排序）

排序：所谓排序就是将一组无序的数字用什么样的算法变的有序。
排序

• 排序算法的稳定性：在未排序的序列中，如果a[i]=a[i+1],a[i]在a[i+1]之前，排序之后a[i]仍旧在a[i+1]前面。不稳定性反之。
• 内排序：所有排序操作均在内存中完成。
• 外排序：由于数据过大，因此把数据放在磁盘中那，排序通过磁盘和内存的数据传输才能进行。
• 时间复杂度：一个算法执行完所消耗的时间
• 空间复杂度：运行完一个程序需要的内存大小。

1. 稳定的排序算法

• 冒泡排序
• 插入排序
• 归并排序
• 基数排序

2.不稳定的排序算法

• 选择排序
  首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从未排序的元素中找到最小（大）的元素放在一排序序列的末尾。以此类推，直到所有元素全部排完。
• 快速排序
• 希尔排序
• 堆排序

3.比较排序

元素之间的次序依赖它们之间的比较，每个数需要与其他数进行比较才能确定自己的位置。比较典型的比较排序有快速排序，归并排序，堆排序，冒泡排序。

4非比较排序
非比较排序只要确定每个元素之前的已有元素个数即可，经过一次遍历便可以解决。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	In-place	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
希尔排序	O(n log n)	O(n log2 n)	O(n log 2 n)	O(1)	In-place	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	稳定
快速排序	O(n log n)	O(n log n)	O(n^2)	O(log n)	In-place	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(K)	Out-place	稳定
桶排序	O(n + k)	O(n + k)	O(n^2)	O(n + k)	Out-place	稳定
基数排序	O(n * k)	O(n * k)	O(n * k)	O(n + k)	Out-place	稳定

排序算法

1.冒泡排序
   比较相邻的数字。如果第一个比第二个大就交换它两的位置，对每一个相邻元素都要进行比较，然后最大的就会在最后一个位置，再重复进行上面的步骤就可以。
时间复杂度：O(n^2)
稳定性：稳定

public class maopao1 {
    public static void main(String[] args) {
        int[]a={2,3,1,4,5,32,21,42,12,33};
        int i,j;
        int temp=0;
        int len=a.length;
        for( i=0;i<len-1;i++)
        {      
            for(j=0;j<len-i-1;j++)
            {
                 if(a[j]>a[j+1])
                 {
                     temp=a[j];
                     a[j]=a[j+1];
                     a[j+1]=temp;                  
                 }
            }
          
        }    
        for(i=0;i<len;i++)
        {
            System.out.print(a[i]+",");
        }
    }
}

运行结果为：

1,2,3,4,5,12,21,32,33,42,

其中从小到大的每一步循环的详细步骤如下：
第一轮：2,1,3,4,5,21,32,12,33,42,
第二轮：1,2,3,4,5,21,12,32,33,42,
第三轮：1,2,3,4,5,12,21,32,33,42,
第四轮：1,2,3,4,5,12,21,32,33,42,
第五轮：1,2,3,4,5,12,21,32,33,42,
第六轮：1,2,3,4,5,12,21,32,33,42,
由上面的步骤可以看出在第三轮已经排好序，后面的排序已经没有必要，所以可以改进代码通过添加标志位使时间复杂度更低。

改进版（通过添加标志位来实现优化）

public class maopao1 {
    public static void main(String[] args) {
        int[]a={2,3,1,4,5,32,21,42,12,33};
        int i,j;
        int temp=0;
        int len=a.length;
        for( i=0;i<len-1;i++)
        {
            boolean isSorted=false;//设置标志位
            for(j=0;j<len-i-1;j++)
            {
                 if(a[j]>a[j+1])
                 {
                     temp=a[j];
                     a[j]=a[j+1];
                     a[j+1]=temp;
                     isSorted=true;//如果发生交换则改变标志位
                 }
            }
            for(j=0;j<len;j++)
            {
                System.out.print(a[j]+",");
            }
            System.out.println();
            if(isSorted==false){
                break;
           }
        }
        System.out.println("****************************");
        for(i=0;i<len;i++)
        {
            System.out.print(a[i]+",");
        }
    }
}

运行结果为：

2,1,3,4,5,21,32,12,33,42,
1,2,3,4,5,21,12,32,33,42,
1,2,3,4,5,12,21,32,33,42,
1,2,3,4,5,12,21,32,33,42,
****************************
1,2,3,4,5,12,21,32,33,42,

我在上面程序中输出了每一次排序的结果和最后一次排序的结果（星号线下面），这样可以更加清楚的看出改进版的程序在前三次排好序，在判断第四次的排序时不满足条件，跳出循环。
2.选择排序
  选择排序就是先在为排序的序列中找的最小（大）的元素放在序列的第一个位置，然后从未排序的序列中继续找出最小（大）的元素放在已排序的后面，以此类推直至排完所有的数字。代码中可以这样理解先默认第一个是最小的，然后从未排序的序列中找出最小的元素与第一个交换位置（如果相等就不用交换了）。
稳定性：不稳定
时间复杂度：O(n^2)

import java.util.Arrays;

public class selectSort {
    public static void main(String[] args) {
        int []a = {1,2,1,-1,6,4,8,9,5,8};
        for (int i = 0; i < a.length-1; i++) {
            for (int j = i; j < a.length; j++) {
                if(a[j]<a[i]){
                    int t =a[j];
                    a[j] = a[i];
                    a[i] = t;
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

运行结果为：

[-1, 1, 1, 2, 4, 5, 6, 8, 8, 9]

3.希尔排序
  希尔排序又称缩小增量排序，其基本思想为:先将原表按照增量h分组，每个子文件进行直接插入排序。同样，用下一个增量h/2将文件再分为子文件，再进行直接插入排序，直到h=1时整个文件排好序。
关键因素：选择合适的增量，普通的选择就是使用数组长度的一半。
时间复杂度：O(n log n)
稳定性：不稳定
3.1插入排序
前面讲到希尔排序是以不同的步长来实现插入排序。所谓插入排序就是在一个无序数组中，用第二个数字和第一个数字进行比较，如果比第一个小的话就插入再其前面，接下来第三个的数字就需要和它前两个数字都要进行比较，插入到最小的数字的前面，这样一直到排序完。
稳定性：稳定
时间复杂度：O(n^2)
插入排序代码：

import java.util.Arrays;

public class insertSort {
    public static void main(String[] args) {
        int []a={-1,2,2,9,4,6,8,3,6};
        for (int i = 0; i < a.length-1; i++) {
            for (int j = i+1; j > 0; j--) {
                if(a[j]<a[j-1]){
                    int t = a[j];
                    a[j] = a[j-1];
                    a[j-1] = t;
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

运行结果为：

[-1, 2, 2, 3, 4, 6, 6, 8, 9]

希尔排序代码

import java.util.Arrays;

public class sheelSort {
    public static void main(String[] args) {
        int[]a={-1,-4,-5,23,45,678,34,678};
        for (int h = a.length/2; h >0 ; h/=2) {
            for (int i = h; i < a.length; i++) {
                for (int j = i; j >=h; j-=h) {
                    if(a[j]<a[j-h]){
                        int t = a[j];
                        a[j] = a[j-h];
                        a[j-h] = t;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

运行结果为：

[-5, -4, -1, 23, 34, 45, 678, 678]

4.归并排序
  归并排序就是利用归并的思想实现排序的方法，他的原理时假设出事序列有N个数字，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两进行归并，得到 N/2 个长度为2或1的有序子序列（因为有可能N为奇数会产生单独的一个数字），再两两归并，如此重复，直到得到一个长度为N的有序序列为止，这种排序方法称为归并排序。
时间复杂度：O(n log n)
稳定性：稳定



https://www.cnblogs.com/chengxiao/p/6194356.html（图片链接）
代码如下：

import java.util.Arrays;

public class guiBingSort {
    public static void main(String[] args) {
        int []arr={3, 5, 6, 2, 1, 7, 8, 9, 10,-1};
        //fen
        chaiFen(arr,0,arr.length-1);
        mergeSort(arr,0,(arr.length/2)-1,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void chaiFen(int[] arr, int startIndex, int endIndex) {
        //计算中间索引
        int centerIndex = (startIndex + endIndex)/2;
        //递归来拆分
        if(startIndex < endIndex){
            //拆左边
            chaiFen(arr,startIndex,centerIndex);
            //拆右边
            chaiFen(arr,centerIndex+1,endIndex);

        }
        //归并
        mergeSort(arr,startIndex,centerIndex,endIndex);
    }

    /**
     *
     * @param arr 要归并的数组
     * @param startIndex 开始索引
     * @param centerIndex 中间索引
     * @param endIndex 结束索引
     */
    //mergeSort(arr,0,(arr.length/2)-1,arr.length-1);
    private static void mergeSort(int[] arr, int startIndex, int centerIndex, int endIndex) {
        //定义一个临时数组
        int[]tempArray = new int[endIndex - startIndex+1];
        //定义临时数组的起始索引
        int index = 0;
        //定义左边数组的起始索引
        int i = startIndex;
        //定义右边数组的起始索引
        int j = centerIndex+1;
        //循环比较左右两边的数组元素，往临时数组里边方
        while (i <= centerIndex && j <= endIndex){
            //进行比较
            if(arr[i]<arr[j]){
                tempArray[index] = arr[i];
                i++;
            }else{
                tempArray[index] = arr[j];
                j++;
            }
            index++;//临时数组的索引要增加
        }
        //处理左边剩余元素
        while (i <= centerIndex){
            tempArray[index] = arr[i];
            i++;
            index++;
        }
        //处理右边剩余元素
        while (j <= endIndex){
            tempArray[index] = arr[j];
            j++;
            index++;
        }
        //遍历临时数组，将临时数组中的元素放到原数组中
        for (int k = 0; k < tempArray.length; k++) {
            //这里k要加上起始索引
            arr[k+startIndex] = tempArray[k];
        }
    }
}

运行结果为：

[-1, 1, 2, 3, 5, 6, 7, 8, 9, 10]

5.快速排序
  快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。
实现方法：快速排序会先把数组中的一个数当作基准数（参照数），一般会把数组中最左边的数当作基准数。然后从两边进行查找，先从右边开始查找比基准数小的，再从左边查找比基准数大的（如果选择最右边的数为基准数那么就先从左边检索，方法类似。），如果找到了就停下，然后交换这两个元素，然后在进行查找。直到两个数相遇，那个此时将基准值与相遇位置元素进行交换，此时基准值左边的所有数据全部比基准值小，右边所有数据全部比基准值大。然后将基准数左边和基准数右边的数组分别采用上述同样的方法进行排序，可以采用递归进行，直到整个数据变成有序序列。
时间复杂度：O(n log n)
稳定性：不稳定

后面，然后将基准数左边和基准数右边的数组分别采用上述同样的方法，可以采用递归进行，直到整个数据变成有序序列。
代码如下：

public class quicksort {
    public static void main(String[] args) {
        int []arr={7,2,3,8,10,4,5,6,11,9};
        //调用方法，进行快速排序
        quicksort(arr, 0, arr.length -1);

        //遍历数组输出
        for(int i=0;i<arr .length;i++){
            System.out.print(arr [i]+" ,");
    }
};
    /*
     *定义方法
     */
    public static void quicksort(int []arr,int left,int right) {
        //进行判断，如果左边索引比右边大，那么直接return结束这个方法
        if (left > right) {
            return;
        }
        //定义变量，保存基准数
        int base = arr[left];
        //定义变量i执行最左边
        int i = left;
        //定义变量j只想左右边
        int j = right;
        while (i != j) {
            //先由j从右往左检索比基准数小的，如果比基准数小的，就停下，
            while (arr[j] >= base && i != j) {
                j--;
            }
            //再从i从左向右检索比基准值大的，如果比基准数大，就停下
            while (arr[i] <= base && i!=j) {
                i++;
            }
            //代码运行到这里，i停下，j也停下,然后交换i,j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;

        }
        //如果上面的while循环不成立，会跳出这个循环，往下执行
        //也就是i,j相遇，那么就把相遇位置元素和基准数交换

        arr[left]=arr[i];
        //把基准数赋给相遇位置元素
        arr[i]=base;
        //基准数在这里归为，左边都比他小，右边都比他大
        //排基准数左边
        quicksort(arr, left,i-1);
        //排基准数右边
        quicksort(arr, i+1, right);
    }
}

运行结果为：

2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,

可以看出快速排序是不稳定的，另外平均时间复杂度为O(nlogn),最好情况O(nlogn)，最坏情况O(N^2).在代码中j和i向前查找的条件一定得想好到底那边大，另外此排序采用递归就可以实现，不用每一步都用代码写出来。