一.总览

二.基于比较的排序算法

1.简单插入排序（重点）

注意：区间较小时，最快
原理：
一组数据array[]，认为以下标i为分界，[0，i+1)认为有序，[i+1,array.length)无序，从无序数据中每次取出一个数据，插入有序数据中

代码实现：

 public static void insertSort(long []array){
        //数据一共有array.length个
        //所以，子操作需要执行array.length次
        //减不减一都可以，减一认为第一个数已经有序
        for (int i = 0; i <array.length-1 ; i++) {
            //有序[0,i+1)  例如刚开始[0,1)有序
            //无序[i+1,array.length)
            //抓取出来的数是[i+1]

            long key=array[i+1];
            int j=0;
            //依次在有序区间进行比较
            for ( j = i; j>=0 ; j--) {
                //[j]就是需要和key比较的数
                /**
                 * key<array[j]   把array[j]往后移 继续往前比较
                 * key==array[j]  把key放入array[j]的后边
                 * key>array[j]   把key放入array[j]的后边
                 */
                if(key<array[j]){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=key;

        }
    }

性能分析：

2.冒泡排序（重点）

原理：

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

无序区间：[0,array,length-i)

有序区间：[array.length-i,array.length)

从下标j开始，将其与下标j+1依次比较，如果大于，交换。

代码实现：

public static void bubblingSort(long []array){
    //外层循环，需要多少次冒泡的过程
        for (int i = 0; i <array.length ; i++) {
            //无序区间：[0,array,length-i)
            //有序区间[array.length-i,array.length)

            //假设数组已经有序
            boolean isSorted=true;

            //冒泡过程
            //只在无序区间中进行
            //循环到无序区间的倒数第二个数，然后倒数第二会和倒数第一再比较
            for (int j  = 0; j  <array.length-i-1 ; j ++) {
                if(array[j]>array[j+1]){
                  swap(array, j, j+1);
                  //交换过，说明数组无序
                    isSorted=false;
                }
            }

            //如果数组有序，退出循环
            if(isSorted){
                break;
            }
        }
    }

    public static void swap(long []array,int i,int j){
     long t=array[i];
     array[i]=array[j];
     array[j]=t;
    }

性能分析：

3.简单选择排序

**原理：

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

以选取最大为例：

无序区间[0,array.length-i)

有序区间[array.length-i,array.length)

动态图为选取最小为例：

代码实现：

//选择排序

    /**
     *选择大的数
     * 前面为有序区间，后面为无序区间
     * 再无序区间中遍历，找到最大的数，和无序区间的最后一个数进行交换
     */
    public static void selectSort(long[]array){
        //一共多少次选择的过程
        for (int i = 0; i <array.length ; i++) {
            //无序区间：[0,array.length-i)
            //有序区间：[array.length-i,array.length)
            //记录无序区间最后一个值的下标和值
            int maxindex=array.length-i-1;
            long key=array[array.length-i-1];
            for (int j = 0; j <array.length-i ; j++) {
                if(array[j]>key){
                    maxindex=j;
                    key=array[j];
                }
            }
            //期望maxIndex指向无序区间的最大值的下标
            //交换最大数所在下标和无序区间最后一个数的下标
            swap(array, maxindex, array.length-i-1);
        }
    }

    public static void swap(long[]array,int i,int j){
        long t=array[i];
        array[i]=array[j];
        array[j]=t;
    }

性能分析：

4.堆排序

原理：
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意：排升序要建大堆，排降序要建小堆，否则不行

代码实现：

public class HeapSort {
    public static void heapSort(long[]array,int size){
       //1.建大堆
          bulidHeap(array,size);
        //2.进行选择的过程，一共需要array.length-1组
        for (int i = 0; i <array.length-1 ; i++) {
            //无序区间：[0,array.length-i)
            //有序区间：[array.length-i,array.length)
            swap(array,0,array.length-i-1);
            //此时无序区间：[0,array.length-i-1)
            //无序区间的个数为array.length-i-1
            adjustDown(array,array.length-i-1,0);
        }
    }
    //交换
    public static void swap(long[]array,int i,int j){
        long t=array[i];
        array[i]=array[j];
        array[j]=t;
    }
    //建大堆
    public static void bulidHeap(long []array,int size){
        int lastNodeIndex=size-1;
        int lastParentIndex=(lastNodeIndex-1)/2;
        for (int i = lastParentIndex; i >=0 ; i--) {
            adjustDown(array,size,i);
        }


    }
    //向下调整
    public static void adjustDown(long[]array,int size,int index){
        while (true){
            //堆是完全二叉树，一定有左孩子
            int leftIndex=index*2+1;
            //如果没有左孩子，则为叶子结点,直接return
            //等于size也超出了数组下标范围
            if(leftIndex>=size){
                return;
            }
            //找最大的孩子
            int maxIndex=leftIndex;
            int rightIndex=leftIndex+1;
            //如果右孩子存在且右孩子的值大于左孩子，则将最大值的下标改为右孩子
            if(rightIndex<size&&array[rightIndex]>array[leftIndex]){
               maxIndex=rightIndex;
            }
            //比较maxIndex和index位置的值，如果maxIndex大，则交换，否则retrun
            if(array[maxIndex]<=array[index]){
                return;
            }
            swap(array, maxIndex, index);
            index=maxIndex;
        }
    }
}

性能分析：

5.希尔排序

原理：

分组插入排序

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有

距离为的记录分在同一组内，并对每一组内的记录进行插入排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

步骤：

1.分为gap组，认为gap之前的都是有序的（每组一个数）

2.对分好的每一个组，在组内进行插入排序

代码实现：

//希尔排序(带间隔的插入排序）
public class ShellSort {
    public static void shellSort(long[]array){
        int gap=array.length/2;

        while (true){
            insertSortWithGap(array, gap);
            if(gap==1){
                break;
            }
            gap=gap/2;
        }
    }


    public static void insertSortWithGap(long[]array,int gap){
        //分为gap组，认为gap之前的都是有序的（每组一个数）
        for (int i =gap; i <array.length ; i++) {
            //记录需要比较的值
          long key=array[i];
          int j=0;
          //对每组的值进行插入排序，每组间隔为gap个
            for (j =i-gap; j >=0 ; j=j-gap) {
                if(key<=array[j]){
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            array[j+gap]=key;
        }
    }
}

性能分析：

6.快速排序（重点）

原理：
快速排序原理：

partition分割原理：Hover法

步骤：
1.选择一个数key（一般选最左边）
2.做partition分隔（小的放左边，大的放右边）
3.分别做左右两个小区间按相同的方式处理（递归）
4.知道（小区间有序：区间数的个数size<=1)

代码实现：


public class QuickSort {
    public static void quickSort(long[]array){
        //排序的区间为lowIndex到highIndex
        quickSortInteral(array,0,array.length-1);
    }

    private static void quickSortInteral(long[]array,int lowIndex,int highIndex){
        //记录区间内数的个数
        //区间是[lowIndex,highIndex]
        int size=highIndex-lowIndex+1;
        //当区间内个数小于等于一时，区间有序
        if(size<=1){
            return;
        }

        //1.选择其中一个数出来（最左边）->array[lowIndex]
        //2.执行partition（分隔），小的数放左，大的数放右

        //keyIndex是经过partition后，选出来的数的最终下标
        int keyIndex=partitionHover(array,lowIndex,highIndex);

        //keyIndex左边： 左边的lowIndex=lowIndex，highIndex=keyIndex-1
        //keyIndex右边： 右边的lowIndex=keyIndex+1，highIndex=highIndex

        //分别左左右区间相同处理->递归
        quickSortInteral(array, lowIndex, keyIndex-1);
        quickSortInteral(array, keyIndex+1, highIndex);

    }
    //区间为array[lowIndex,highIndex]
    //1.选择array[lowIndex]作为特殊的数
    //2.需要遍历整个区间（不能遗漏任何数），与选择出来的数进行比较
    //3.保证小于等于的在最左边，大于等于的数在最右边（但没有顺序要求）
    private static int partitionHover(long []array,int lowIndex,int highIndex){
       int leftIndex=lowIndex;
       int rightIndex=highIndex;
       //选择的数是最左边的
        //注意：选择最左边的数key，要让rightIndex先动起来，不然右边全小于key的情况不好考虑
        long key=array[lowIndex];
        while (leftIndex<rightIndex){
            while (leftIndex<rightIndex&&array[rightIndex]>=key){
                //当右边的值大于key，rightIndex继续往左走
                rightIndex--;
            }
            while (leftIndex<rightIndex&&array[leftIndex]<=key){
                //当左边的值小于key，leftIndex继续往右走
                leftIndex++;
            }
            //当leftIndex和rightIndex都停下来时，交换
            swap(array, leftIndex, rightIndex);

            //当leftIndex和rightIndex相遇时，循环结束
        }
        //交换开始选中的值leftIndex和上述停止相遇的值lowIndex
        swap(array, leftIndex, lowIndex);

        //返回选中的key值当前的位置
        return leftIndex;

    }

    private static void swap(long[]array,int i,int j){
        long t=array[i];
        array[i]=array[j];
        array[j]=t;
    }
}

性能分析：

时间复杂度：每次partition的时间为O（n），然后乘以二叉树的高度

7.归并排序（二路归并）（重点）

原理：
归并思想：

数组合并思想：
创建一个新数组，数组大小个原数组大小相等
遍历将左边和右边两个有序区间，并比较。如同打擂台，小的数放入新数组
最后将新创建的数组复制到原数组即可

整体思想：

代码实现：

//归并排序
public class MergeSort {
    public static void mergeSort(long[]array){
        mergeSortInternal(array,0,array.length);

    }

    //区间范围是左闭右开
    //array[lowIndex,highIndex)
    private static void mergeSortInternal(long[] array, int lowIndex, int highIndex) {

        int size=highIndex-lowIndex;
        if(size<=1){
            return;
        }
        int middleIndex=(highIndex+lowIndex)/2;
        //区间被分成左右两份
        //左区间：[lowIndex,middleIndex)
        //右区间: [middleIndex,highIndex)


        //递归
        mergeSortInternal(array, lowIndex, middleIndex);
        mergeSortInternal(array, middleIndex, highIndex);


         //左右两个区间都有序
        mergeLeftAndRight(array,lowIndex,middleIndex,highIndex);


    }

    //合并两个有序区间
    private static void mergeLeftAndRight(long[] array, int lowIndex, int middleIndex, int highIndex) {
        //两个区间数的总数
        int size=highIndex-lowIndex;
        long[]extraArray=new long[size];

        //遍历（三个下标，一个数组一个）
        int leftIndex=lowIndex;
        int rightIndex=middleIndex;
        int extraIndex=0;

        //两个队伍都有人
        while (leftIndex<middleIndex&&rightIndex<highIndex){
            //加等于保证稳定性
            if(array[leftIndex]<=array[rightIndex]){
                extraArray[extraIndex]=array[leftIndex];
                leftIndex++;
            }else {
                extraArray[extraIndex]=array[rightIndex];
                rightIndex++;
            }
            extraIndex++;
        }

        //直到有个队伍没有人
        if(leftIndex<middleIndex){
            //左边队伍有人
            while (leftIndex<middleIndex){
                extraArray[extraIndex++]=array[leftIndex++];
            }
        }else {
            //右边队伍有人
            while (rightIndex<highIndex){
                extraArray[extraIndex++]=array[rightIndex++];
            }
        }

        //最后把数据从extraArray新数组搬回去
        //新数组extraArray[0,size)
        //搬回去的下标范围[lowIndex,highIndex)
        for (int i = 0; i <size; i++) {
            array[i+lowIndex]=extraArray[i];
        }
    }
  
}

性能分析：