①冒泡排序

排序原理：

比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。

实现代码：

//冒泡排序
    public static void sort(int[] a){
        for(int i=1; i<a.length; i++){
            for(int j=0;j<a.length-1;j++){
                if(a[j]<a[j+1]){
                    int temp=a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }

冒泡排序的时间复杂度分析:
冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，
我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
在最坏情况下，也就是假如要排序的元素为{6,5,4,3,2,1}逆序，那么：
元素比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
元素交换的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
总执行次数为：
(N^2/2-N/2)+(N^2/2-N/2)=N^2-N;
按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N^2).

②选择排序

排序原理：

1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引 2.交换第一个索引处和最小值所在的索引处的值

实现代码

public static void sort1(int a[]){
        for(int i=0;i<a.length-1;i++){
            int minIndex = i;
            for(int j=i+1;j<=a.length-1;j++) {
                if (a[minIndex] > a[j]) {
                    minIndex = j;
                }
            }
            if (minIndex!=i){
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex]=temp;
            }
        }
    }

选择排序的时间复杂度分析：
选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据
交换次数和数据比较次数：
数据比较次数：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
数据交换次数：
N-1
时间复杂度：N^2/2-N/2+（N-1）=N^2/2+N/2-1;
根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);

③插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我
们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在
手中的每张牌进行比较

排序原理：

1.把所有的元素分为两组，已经排序的和未排序的； 2.找到未排序的组中的第一个元素，向已经排序的组中进行插入； 3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

实现代码:

//插入排序
    public static void sort2(int a[]){
        for (int i = 1; i < a.length; i++) {
            for(int j=i;j>0;j--){
                if (a[j]<a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }else{
                    break;
                }
            }
        }
    }

插入排序的时间复杂度分析:
插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复
杂度，主要分析一下内层循环体的执行次数即可。
最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么：
比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交换的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
总执行次数为：
(N^2/2-N/2)+(N^2/2-N/2)=N^2-N;
按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).

之前我们学习过基础排序，包括冒泡排序，选择排序还有插入排序，并且对他们在最坏情况下的时间复杂度做了分
析，发现都是O(N^2)，而平方阶通过我们之前学习算法分析我们知道，随着输入规模的增大，时间成本将急剧上
升，所以这些基本排序方法不能处理更大规模的问题，接下来我们学习一些高级的排序算法，争取降低算法的时间
复杂度最高阶次幂。

④希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
前面学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为{2,5,7,9,10}，未排序的分组
元素为{1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真
正的插入，每次交换只能和相邻的元素交换位置。那如果我们要提高效率，直观的想法就是一次交换，能把1放到
更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1就向前走了5个位置，可以减少交换的次数.
排序原理：

1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组； 2.对分好组的每一组数据完成插入排序； 3.减小增长量，最小减为1，重复第二步操作。

增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：

  int h=1;
   while(h<5){
     h=2h+1；//3,7
   }
//循环结束后我们就可以确定h的最大值； 
h的减小规则为： 
     h=h/2

实现代码:

//希尔排序   希尔=插入+分组
    public static void sort3(int a[]) {
        int h = 1;
        while (h < a.length) {
            h = h * 2 + 1;
        }
        while(h>=1) {
            //这相当于就是多次插入排序
            for (int i = h; i < a.length; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (a[j - h] > a[j]) {
                        int temp = a[j];
                        a[j] = a[j - h];
                        a[j - h] = temp;
                    } else {
                        break;
                    }
                }
            }
            h = h / 2;
        }
    }

希尔排序的时间复杂度分析
测试的思想：在执行排序前前记录一个时间，在排序完成后记录一个时间，两个
时间的时间差就是排序的耗时。

⑤归并排序

*递归

定义：
定义方法时，在方法内部调用方法本身，称之为递归.
作用：
它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量的
程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意事项：
在递归中，不能无限制的调用自己，必须要有边界条件，能够让递归结束，因为每一次递归调用都会在栈内存开辟
新的空间，重新执行方法，如果递归的层级太深，很容易造成栈内存溢出。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子
序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序
表，称为二路归并。

排序原理：

1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止。 2.将相邻的两个子组进行合并成一个有序的大组； 3.不断的重复步骤2，直到最终只有一个组为止。

分析：

实现代码:

public class test {
    public static void main(String[] args) {
        int []b = {4,3,7,1,2,10,5,12,14,9};
        sort(b);
        System.out.println(Arrays.toString(b));
    }
    //辅助数组
    private static int[] asset;
    //归并排序
    public static void sort(int[] a){
        asset = new int[a.length];
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    public static void sort(int[] a, int lo, int hi){
        if (hi<=lo){
            return;
        }
        int mid = lo + (hi-lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);

        merge(a,lo,mid,hi);
    }
    public static void merge(int[] a, int lo, int mid, int hi){
        int i = lo;
        int p1 = lo;
        int p2= mid +1;

        while(p1<=mid&&p2<=hi){
            if (a[p1]<a[p2]){
                asset[i++]=a[p1++];
            }else{
                asset[i++]=a[p2++];
            }
        }

        while(p1<=mid){
            asset[i++]=a[p1++];
        }
        while(p2<=hi){
            asset[i++]=a[p2++];
        }

        for (int index = lo; index <= hi; index++) {
            a[index] = asset[index];
        }
    }
}

归并排序时间复杂度分析：
归并排序是分治思想的最典型的例子，上面的算法中，对a[lo…hi]进行排序，先将它分为a[lo…mid]和a[mid+1…hi]
两部分，分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果
一个数组不能再被分为两个子数组，那么就会执行merge进行归并，在归并的时候判断元素的大小进行排序。

用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆log8次，值为3，所以
树共有3层,那么自顶向下第k层有2^k个子数组，每个数组的长度为2^(3-k)，归并最多需要2^(3-k)次比较。因此每层
的比较次数为 2^k 2^(3-k)=2^3,那么3层总共为 32^3。

假设元素的个数为n，那么使用归并排序拆分的次数为log2(n),所以共log2(n)层，那么使用log2(n)替换上面32^3中
的3这个层数，最终得出的归并排序的时间复杂度为：log2(n) 2^(log2(n))=log2(n)*n,根据大O推导法则，忽略底
数，最终归并排序的时间复杂度为O(nlogn);

归并排序的缺点：
需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。

⑥快速排序

详见java面经

数据结构与算法

三、排序

①冒泡排序

②选择排序

③插入排序

④希尔排序

⑤归并排序

*递归

归并排序

⑥快速排序