插入排序：

• 直接插入排序

基本原理：對于給定的一組記錄，初始時假設第一個記錄自成一個有序序列，其余記錄為無序序列，接著從第二個記錄開始，按照記錄的大小依次將當前處理的記錄插入到其之前的有序序列中，直至最后一個記錄插入到有序序列中為止。

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時，才進入循環(huán)進行判斷
            while(j>=1&&n[j-1]>temp){
                    n[j]=n[j-1];
                    j--;
                }
            }
            n[j]=temp;
            }
        
        return n;
    }
}

• 希爾排序（從小到大）

基本原理：先將待排序的數(shù)組元素分成多個子序列，使得每個子序列的元素個數(shù)相對較少，然后對各個子序列分別進行直接插入排序，待整個待排序序列“基本有序后”，最后再對所有元素進行一次直接插入排序。

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的數(shù)組元素開始，依次與子序列中前面的元素進行對比
                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個記錄，初始時把這些記錄看作一棵順序存儲的二叉樹，然后將其調整為一個大頂堆，然后將堆的最后一個元素與堆頂元素（即二叉樹的根節(jié)點）進行交換后，堆的最后一個元素即為最大記錄；接著將前（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);//循環(huán)建堆
            exchange(n, 0, n.length-1-i);//交換堆頂與堆中最后一個元素
            System.out.println(Arrays.toString(n));
        }
    }

    //建立大頂堆
    public static void buildMaxHeap(int[]n,int lastindex){
        //從最后一個結點的父節(jié)點開始構建
        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;
             }
            }
        }
        
    }
    //交換數(shù)組中的兩個元素
    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++){//比較的趟數(shù)
            for(int j=0;j<n.length-i-1;j++){//每趟比較的次數(shù)
                //按從小到大的順序排序
                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;//對數(shù)組進行分解的基準值的索引
       if(start<end){
           flag=partition(n,start,end);
           sort(n,start,flag-1);//遞歸對基準值左邊的子數(shù)組進行排序
           sort(n,flag+1,end);//遞歸對基準值右邊的子數(shù)組進行排序
       }
   }
   
   public static int partition(int[]n,int start,int end){
       int temp=n[start];//將數(shù)組最左邊的值設置為基準值
       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的有序子序列，再將其兩兩歸并，反復執(zhí)行此過程，直到得到一個有序序列。

public class MergeSort {

    public static void sort(int[] n,int left,int right){
        if(left<right){
        int mid=(left+right)/2;//計算數(shù)組中間元素索引位置
        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];//定義一個臨時數(shù)組用于存放排好序的數(shù)組元素
        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數(shù)組中
        while(left<=mid){
            temp[p++]=n[left++];
        }
        while(right<=end){
            temp[p++]=n[right++];
        }
        //將temp數(shù)組中的元素復制到數(shù)組n中
        while(k<=end){
            n[k]=temp[k];
            k++;
        }
        
    }
}

• 基數(shù)排序

基本思想：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位比較短的數(shù)前面補零。然后，從最低位開始，依次進行依次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列。

public class RadixSort {

   public static void sort(int[]n){
       //獲取數(shù)組中最大的數(shù)
       int temp=0;
       for(int i=0;i<n.length;i++){
           if(n[i]>temp){
               temp=n[i];
           }
       }
       //得到需要比較的次數(shù)
       int count=0;
       while(temp>0){
           temp=temp/10;
           count++;
       }
       //創(chuàng)建十個數(shù)組
       List<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
       for(int i=0;i<10;i++){
           ArrayList<Integer> list=new ArrayList<Integer>();
           queue.add(list);
       }
       //每一數(shù)組中元素的排序
       for(int i=0;i<count;i++){
           for(int j=0;j<n.length;j++){
               //獲取數(shù)值中的各位數(shù)字
               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]);//將原數(shù)組中的數(shù)值添加到集合中
           }
           //按照數(shù)組中值的各位大小進行排序
           int num=0;//元素計數(shù)器
           for(int k=0;k<10;k++){
               while(queue.get(k).size()>0){//遍歷數(shù)組中各個集合中的元素值
                   ArrayList<Integer>list2=queue.get(k);//獲取索引值k所對應的集合
                   n[num]=list2.get(0);//依次移除集合中的各個元素
                   list2.remove(0);
                   num++;
               }
           }
       }
   }
}