1. 选择排序：首先找到数组中最小的那个元素，然后将它和数组中第一个元素进行交换，再从剩下的元素中找到最小的元素，然后和第二个元素进行交换， 以此类推。O(N^2) ```java import java.util.Scanner;

    public class SelectionSort { public static void main(String args[]){ Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); String array[] = str.split(“,”); int a [] = new int [array.length]; for(int i= 0; i<a.length;i++){ a[i] = Integer.parseInt(array[i]); System.out.print(a[i]+”、”); } sort(a); System.out.println(); System.out.println(“排序后：”); for(int i= 0; i<a.length;i++){ System.out.print(a[i]+”、”); }

    1. }
    2. public static int [] sort (int temp[]){
    3.     int N = temp.length;
    4.     for(int i = 0; i < N ; i++){
    5.         int min =i;
    7.         for(int j =i+1;j < N; j++){
    8.             if(temp[j]<temp[min]){
    9.                 int t= temp [j];
    10.                 temp[j] =temp[min];
    11.                 temp[min] =t;
    12.             }
    13.         }
    14.     }
    15.    return temp;
    16. }

    }

    2.插入排序： 应用于某些类型非随机数组有效（接近有序）与选择排序相同，插入排序左边的都是有序，将较小的元素插入前面，插入之前右边的元素向右移动一位：
```java
import java.util.Scanner;

public class SectionSort {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String array [] = str.split(",");
        int a [] = new int [array.length];
        for(int i =0; i<array.length;i++){
            a[i]= Integer.parseInt(array[i]);
        }
        System.out.println("排序前：");
        for(int i = 0; i<array.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println("排序后");
        sort(a);
        for(int i = 0; i<array.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static int [] sort(int temp[]){
        int N =temp.length;
        for(int i=1;i<N;i++){
            for(int j =i;j>0&&(temp[j]<temp[j-1]);j--){
                int t= temp [j];
                temp[j] =temp[j-1];
                temp[j-1] =t;
            }
        }
        return temp;
    }

}

    3.希尔排序：加快改进插入排序，交换不相邻的元素以对数组局部进行排序，最终使用插入排序将局部有序的数组进行排序：思想：就是任意间隔h的元素是有序的

    import java.util.Scanner;

public class ShellSort {
    public static void main(String args[]){
        /**
         *
         * 希尔排序首先让大规模乱序数组变成局部有序的数组对，然后用插入排序对处理后的数组对进行排序。
         */
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String array[] = str.split(" ");
        int a [] = new int[array.length];
        System.out.println("排序前：");
        for(int i = 0;i<array.length;i++){
            a[i] = Integer.parseInt(array[i]);
            System.out.print(a[i]+"、");
        }
        sort(a);
        System.out.println("排序后：");
        for(int i : a){
            System.out.print(i+"、");
        }
    }
    public static int [] sort (int temp[]){
        int N = temp.length;
        int h =1;
        while(h<N/3){
            h= 3*h+1;
        }
            while(h>=1){
                for(int i =h; i<N;i++){
                    for(int j= i;j>=h&&(temp[j]<temp[j-h]);j-=h){
                        int t =temp[j];
                        temp[j] = temp[j-h];
                        temp[j-h] = t;
                    }
                }
                h=h/3;
            }

        return temp;
    }
}

    4.归并排序：

      public static void mergeSort(int temp[],int start ,int end){
        if(end<=start)return;
        int mid =start +(end-start)/2;
        mergeSort(temp,start,mid);//左边排序
        mergeSort(temp,mid+1,end);
        merge(temp,start,mid,end);
    }
   public static void merge(int temp[],int start,int mid,int end){
        int i= start;
        int j= mid+1;
        int array [] = new int [temp.length];
        for(int k=start;k<array.length;k++){
            array[k]=temp[k];
        }
        for(int k =start;k<temp.length;k++){
        if(i>mid) temp[k]=array[j++];
        else if(j>end)  temp[k] =array[i++];
        else if(array[j]<array[i])temp[k]=array[j++];
        else temp[k] =array[i++]  ;
        }
   }

    5.快速排序

    //快速排序
    public static void quickSort (int temp[],int start,int end ){
        //int M=3;
        //if(end<=start+M){
            //对小数组进行插入排序
          //  insert(temp, start,end);
            //return;}

        if(end<=start)return;
        int j = partition(temp,start ,end);
        quickSort(temp,start,j-1);
        quickSort(temp,j+1,end);
    }
    //切分
    public static int partition(int temp[],int start ,int end) {
//        int i = start;
//        int j = end;
//        int vo = temp[start];
//        while (i < j) {
//            //从右边开始
//            while (vo <=temp[j]&&i<j) {
//                j--;
//            }
//            //从左边开始
//            while (vo >= temp[i]&&i<j) {
//                i++;
//            }
//            //如果找到了
//            if (i < j) {
//                exchange(temp, i, j);
//
//            }
//        }
//        //调整首位置元素到准确位置
//        exchange(temp,start,j);
//        //返回准备位置作为切分位置
//        return j;
        /*****************************算法书上********/
        int i =start;
        int j =end+1;
        int vo =temp[start];
        while(true){
            while(temp[++i]<vo&&i<end);



            while(vo<temp[--j]&&j>start);



            if(i>=j)break;
            exchange(temp,i,j);
        }
        exchange(temp,start,j);
        return j;
        /**************************/




    }
    public static void exchange( int a[],int i,int j){
        int t =a[i];
        a[i]=a[j];
        a[j]=t;
    }