1.直接插入排序（Straight Insertion Sort）

时间复杂度O(n^2)，空间复杂度O(1)，稳定

    public void InsertionSort(int[] a){
        for(int i=1;i<a.length;i++){
            int insertionNode = a[i];
            int j=i-1;
            for(;j>=0&&insertionNode<a[j];j--){
                a[j+1]=a[j];
            }
            a[j+1] = insertionNode;
        }
    }

2.希尔排序（Shell Sort）

3.简单选择排序（Simple Selection Sort）

时间复杂度O(n^2)，空间复杂度O(1)，不稳定

    public static void SelectionSort(int[] a){
        for(int i=0;i<a.length;i++){
            int min = a[i];
            int position = i;
            //寻找最小值
            for(int j=i+1;j<a.length;j++){
                if(a[j]<min){
                    min = a[j];
                    position = j;
                }
            }
            //交换a[i]和最小值
            if(position!=i) {
                a[position] = a[i];
                a[i] = min;
            }
        }
    }

4.堆排序（Heap Sort）

5.冒泡排序(Bubble Sort)

时间复杂度O(n^2)，空间复杂度O(1)，稳定

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

6.快排（Quick Sort）

平均时间复杂度O(nlogn)，空间复杂度O(logn)，不稳定
最好时间复杂度O(nlogn)，最好情况是每次pivot都可以均分两段
最坏时间复杂度是O(n^2)，最坏情况是每次只能缩短一个排序位。即数据有序情况

   public static void QuickSort(int[] a,int l,int r){
        //这里是if
        if(l<r){
            int position = partition(a,l,r);
            QuickSort(a,l,position-1);
            QuickSort(a,position+1,r);
        }
    }
    private static void swap(int[] a,int l,int r){
        int temp = a[r];
        a[r]=a[l];
        a[l]=temp;
    }
    private static int partition(int[] a,int l,int r){
        int pivot = a[l];
       //两次交换:或者是每次都交换小值到低端，大值到高端；或者是直接交换low,high，然后最后把pivot换回来。这种情况需要记录pivot的初始位置
        while(l<r){
            while(l<r&&a[r]>=pivot)r--;
            swap(a,l,r);
            while(l<r&&a[l]<=pivot)l++;
            swap(a,l,r);
        }
        return l;
    }
    public static void main(String[] args){
        int[] a = {3,1,5,7,2,4,9,6};
        QuickSort(a,0,a.length-1);
        print(a);
    }