插入排序：

• 直接插入排序

基本原理：对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余记录为无序序列，接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

public class InsertSort {
    
    public static int[] sort(int[] n){
        
        if(n.length<=0){
            return null;
        }
        //从第二个元素开始进行对比判断
        for(int i=1;i<n.length;i++){
            int temp=n[i];
            int j=i;
            if(n[j-1]>temp){//当n[j-1]>temp时，才进入循环进行判断
            while(j>=1&&n[j-1]>temp){
                    n[j]=n[j-1];
                    j--;
                }
            }
            n[j]=temp;
            }
        
        return n;
    }
}

• 希尔排序（从小到大）

基本原理：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，最后再对所有元素进行一次直接插入排序。

public class ShellSort {

    public static void sort(int[]n){
        int len=n.length;
        int d=len/2;//初始步长
        int j=0;
        while(d>0){
            for(int i=d;i<n.length;i++){
               //从索引值为d的数组元素开始，依次与子序列中前面的元素进行对比
                int temp=n[i];
                for(j=i;j>=d;j-=d){//对比的索引减量为d
                    if(n[j-d]>temp){
                        n[j]=n[j-d];
                    }else{
                        break;
                    }
                }
                n[j]=temp;
            }
            d=d/2;
        }
    }
}

选择排序：

• 选择排序

基本原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。

public class SelectSort {

    public static int[] sort(int[] n){
        int temp=0;
        for(int i=0;i<n.length-1;i++){
            int flag=i;
            temp=n[i];
            for(int j=i+1;j<n.length;j++){
                if(temp>n[j]){
                    temp=n[j];
                    flag=j;
                }
            }
            if(flag!=i){
            n[flag]=n[i];
            n[i]=temp;
            }
        }
        return n;
    }
}

• 堆排序

基本思想：对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根节点）进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素（即不包括最大记录）重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。

public class HeapSort {
    //排序
    public static void sort(int[]n){
        for(int i=0;i<n.length-1;i++){
            buildMaxHeap(n, n.length-1-i);//循环建堆
            exchange(n, 0, n.length-1-i);//交换堆顶与堆中最后一个元素
            System.out.println(Arrays.toString(n));
        }
    }

    //建立大顶堆
    public static void buildMaxHeap(int[]n,int lastindex){
        //从最后一个结点的父节点开始构建
        for(int i=(lastindex-1)/2;i>=0;i--){
            while(2*i+1<=lastindex){//判断i结点是否有子结点
                int k=2*i+1;//i结点的左子树
                int max=k;//标记最大子树的索引值
                int temp=n[k];//标记最大子树的值
             if(k<lastindex){//判断i结点是否有右子树
                 if(n[k]<n[k+1]){
                     temp=n[k+1];
                     max=k+1;
                 }
             }
             if(n[max]>n[i]){//子结点的值大于父结点
                 exchange(n,i,max);
                 k=max;
             }else{
                 break;
             }
            }
        }
        
    }
    //交换数组中的两个元素
    public static void exchange(int[]n,int i,int j ){
        int temp=0;
        temp=n[i];
        n[i]=n[j];
        n[j]=temp;
    }
}

交换排序：

• 冒泡排序

基本思想：（由小到大）对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。

public class BubbleSort {

    public static int[] sort(int[] n){
        if(n.length<=0){
            return null;
        }
        int temp=0;
        for(int i=0;i<n.length-1;i++){//比较的趟数
            for(int j=0;j<n.length-i-1;j++){//每趟比较的次数
                //按从小到大的顺序排序
                if(n[j]>n[j+1]){
                    temp=n[j];
                    n[j]=n[j+1];
                    n[j+1]=temp;
                }
            }
        }
        return n;
    }
}

• 快速排序

基本思想：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

public class QuickSort {

   public static void sort(int[]n,int start,int end){
       int flag=0;//对数组进行分解的基准值的索引
       if(start<end){
           flag=partition(n,start,end);
           sort(n,start,flag-1);//递归对基准值左边的子数组进行排序
           sort(n,flag+1,end);//递归对基准值右边的子数组进行排序
       }
   }
   
   public static int partition(int[]n,int start,int end){
       int temp=n[start];//将数组最左边的值设置为基准值
       while(start<end){
           while(start<end&&temp<n[end]){//从右往左找到第一个比基准值小的值
               end--;
           }
           if(start<end){
               n[start]=n[end];//将第一个比基准值小的值赋值给start位置索引
               start++;//start指针前移一个位置
           }
           while(start<end&&temp>n[start]){//从左往右找到第一个比基准值大的值
               start++;
           }
           if(start<end){
               n[end]=n[start];//将第一个比基准值大的值赋值给end位置索引
               end--;//end指针后移一个位置
           }
       }
       //此时start=end
       n[end]=temp;
       return end;
   }
}

• 归并排序

基本思想：对于给定的一组记录（假设共有n个记录），首先将每两个相邻的长度为1的子序列进行归并，得到n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。

public class MergeSort {

    public static void sort(int[] n,int left,int right){
        if(left<right){
        int mid=(left+right)/2;//计算数组中间元素索引位置
        sort(n, left, mid);//对左半部分进行递归排序
        sort(n, mid+1, right);//对右半部分进行递归排序
        merge(n, left, mid, right);//合并
        }
    }
    public static void merge(int[]n,int start,int mid,int end){
        int[] temp=new int[n.length];//定义一个临时数组用于存放排好序的数组元素
        int p=start;
        int k=start;
        int left=start;//左指针
        int right=mid+1;//右指针
        while(left<=mid&&right<=end){
            if(n[left]>n[right]){
                temp[p++]=n[left++];
            }else{
                temp[p++]=n[right++];
            }
        }
        //将剩余元素填充到temp数组中
        while(left<=mid){
            temp[p++]=n[left++];
        }
        while(right<=end){
            temp[p++]=n[right++];
        }
        //将temp数组中的元素复制到数组n中
        while(k<=end){
            n[k]=temp[k];
            k++;
        }
        
    }
}

• 基数排序

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位比较短的数前面补零。然后，从最低位开始，依次进行依次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

public class RadixSort {

   public static void sort(int[]n){
       //获取数组中最大的数
       int temp=0;
       for(int i=0;i<n.length;i++){
           if(n[i]>temp){
               temp=n[i];
           }
       }
       //得到需要比较的次数
       int count=0;
       while(temp>0){
           temp=temp/10;
           count++;
       }
       //创建十个数组
       List<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
       for(int i=0;i<10;i++){
           ArrayList<Integer> list=new ArrayList<Integer>();
           queue.add(list);
       }
       //每一数组中元素的排序
       for(int i=0;i<count;i++){
           for(int j=0;j<n.length;j++){
               //获取数值中的各位数字
               int x=n[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
               ArrayList<Integer> list1=queue.get(x);//获取queue中索引值为x的集合
               list1.add(n[j]);//将原数组中的数值添加到集合中
           }
           //按照数组中值的各位大小进行排序
           int num=0;//元素计数器
           for(int k=0;k<10;k++){
               while(queue.get(k).size()>0){//遍历数组中各个集合中的元素值
                   ArrayList<Integer>list2=queue.get(k);//获取索引值k所对应的集合
                   n[num]=list2.get(0);//依次移除集合中的各个元素
                   list2.remove(0);
                   num++;
               }
           }
       }
   }
}