1、选择排序

每次选择剩余序列中最小的数，然后与当前数进行交换。
时间复杂度为平方级别，时间复杂度不需要额外空间。

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 17:14
 */
public class Selection {
    /**
     * 选择排序，每次都选择剩余的当中最小的元素
     * @param a
     */
    public static void sort(int[] a){
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]){
                    min = j;
                }
            }
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
        return;
    }
}

2、插入排序

每次将当前数字插入到已排好序的数组当中。
时间复杂度为平方级别，空间复杂度不需要额外空间。

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 17:14
 */
public class Insertion {
    /**
     * 插入排序，每次将元素插入到已排好序的数组中，并保持有序，
     * 当索引到达数组末端时，排序结束
     * @param a
     */
    public static void sort(int[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]){
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
        return;
    }
}

3、希尔排序

是插入排序的一个变形。
相当于把整个数组看做多个h-子数组，子数组是相互独立的，然后对子数组进行排序，排序方法是插入排序，然后把h逐渐减小，减小的时候再排序之后就是有序数组。

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 17:44
 */
public class Shell {
    /**
     * 希尔排序
     * @param a
     */
    public static void sort(int[] a){
        int n = a.length;
        int h = 1;
        while (h < n){
            h = 3 * h + 1;
        }
        while (h >= 1){
            //将数组变为h有序子数组，其中每个h子数组的排序过程是插入排序
            //然后逐渐将h变小
            //直到将h变为1
            //表明三重循环，但每次循环的比较和交换顺序都很小
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                }
            }
            h /= 3;
        }
        return;
    }
}

4、归并排序

即要将数组排序，可以先递归地将它分成两半分别排序，然后将结果归并起来。
归并排序的时间复杂度为Nlpog(N)级别，空间复杂度为O(N)

4.1、自顶向下的归并排序

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 20:57
 */
public class Merge {
    private static int[] aux;
    public static void sort(int[] a){
        aux = new int[a.length];
        merge(a,0,a.length - 1);
    }
    /**
     * 希尔排序，自顶向下
     * @param a
     * @param lo
     * @param hi
     */
    public static void merge(int[] a,int lo,int hi){
        if (lo >= hi){
            return;
        }
        int mid = lo + (hi - lo) / 2;
        merge(a,lo,mid);
        merge(a,mid + 1,hi);
        int i = lo,j = mid + 1;
        for (int k = lo; k <= hi;k++) {
            if (i > mid){
                aux[k] = a[j++];
            }else if (j > hi){
                aux[k] = a[i++];
            }else if (a[i] < a[j]){
                aux[k] = a[i++];
            }else{
                aux[k] = a[j++];
            }
        }
        for (int k = lo; k <= hi; k++) {
            a[k] = aux[k];
        }
    }
}

4.2、自底向上的希尔排序

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 21:26
 */
public class MergeBU {
    private static int[] aux;
    /**
     * 自底向上的希尔排序
     * @param a
     */
    public static void sort(int[] a){
        aux = new int[a.length];
        for (int i = 1; i < a.length; i = (i +i)) {
            for (int j = 0; j < a.length - i; j += (i + i)) {
                merge(a,j,j + i - 1,Math.min(j + i + i - 1,a.length -1));
            }
        }
    }
    public static void merge(int[] a,int lo,int mid,int hi){
        int i = lo,j = mid + 1;
        for (int k = lo; k <= hi;k++) {
            if (i > mid){
                aux[k] = a[j++];
            }else if (j > hi){
                aux[k] = a[i++];
            }else if (a[i] < a[j]){
                aux[k] = a[i++];
            }else{
                aux[k] = a[j++];
            }
        }
        for (int k = lo; k <= hi; k++) {
            a[k] = aux[k];
        }
    }
}

5、快速排序

快速排序是一种基于分治的排序算法。它将一个数组分为两个子数组，将两部分独立地排序。快速排序每次循环都能把一个数字放在它的最终位置。
快速排序是所有排序算法中平均性能最好的。平均时间复杂度为线性对数级别，不需要额外的空间。

5.2、基础算法

package sort;
/**
 * @author zwlstart
 * @create 2020-12-20 21:53
 */
public class QuickSort {
    public static void sort(int[] a,int start,int end){
       if (start >= end){
           return;
       }
       int i = start,j = end;
       int temp = i;
       while (i < j){
           if (a[i] == a[temp]){
               while (a[j] >= a[temp] && j > i){
                   j--;
               }
               if (j > i){
                   int b = a[temp];
                   a[temp] = a[j];
                   a[j] = b;
                   i = temp;
                   temp = j;
               }
           }else{
               while (a[i] <= a[temp] && i < j){
                   i++;
               }
               if (j > i){
                   int b = a[temp];
                   a[temp] = a[i];
                   a[i] = b;
                   j = temp;
                   temp = i;
               }
           }
       }
       sort(a,start,temp - 1);
       sort(a,temp + 1,end);
    }
}

5.2、算法改进

切换到插入排序：对于小数组，快速排序比插入排序慢。
三取样切分，基础算法是每次取第一个值进行切分，可能切分效果不好，可以取三个数，然后选择三个数的中间数进行切分。
5.3、熵最优的排序
主要针对的是存在大量重复数字的排序。
简单的想法是把数组分为三部分，小于、等于、大于切分元素的三部分。然后只需要继续递归排序小于和大于的部分。
三向切分的快速排序： ```java package sort;

import java.util.HashMap;

/**

@author zwlstart

@create 2020-12-20 22:22 */ public class Quick3Way {

public static void sort(int[] a,int start,int end){

 if (start >= end){
     return;
 }
 //lt记录切分元素，小于lt的都说比切分元素小的
 //在lt和i之间的都说和切分元素相等的
 //在gt之后的都是比切分元素大的
 int lt = start, i = start + 1,gt = end;
 int v = a[start];
 while (i <= gt){
     int cmp = a[i] - v;
     if (cmp < 0){
         //说明该元素比切分元素小,该元素需要转移到lt之后
         int temp = a[i];
         a[i] = a[lt];
         a[lt] = temp;
         i++;
         lt++;
     }else if (cmp > 0){
         int temp = a[i];
         a[i] = a[gt];
         a[gt] = temp;
         gt--;
     }else{
         i++;
     }
 }
 sort(a,start,lt - 1);
 sort(a,gt + 1, end);

} } ```

算法学习

2、排序算法