排序就是使一组数据，按照其中的某个或者某些关键字数据的大小进行递增或递减的方式排列起来的操作。

1、冒泡排序

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

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

2、快速排序

从待排序区间下选择一个值作为基准值，遍历整个待排序区间，将比基准值小的放到基准值左边，比基准值大的放到基准值右边，左右两边再重复这个步骤直到不能分了为止。

    public static void quickSort(int[] arr, int start, int end) {
        //如果指针在同一位置(只有一个数据时)，退出
        if (end - start < 1) {
            return;
        }
        //标记，从高指针开始，还是低指针（默认高指针）
        boolean flag = true;
        //记录指针的真实位置
        int i = start;
        int j = end;
        //默认中间值为低指针的第一个值
        int midValue = arr[i];
        while (true) {
            //高指针移动
            if (flag) {
                //如果列表右方的数据大于中间值，则向左移动
                if (arr[j] > midValue) {
                    j--;
                } else if (arr[j] < midValue) {
                    //如果小于，则覆盖最开始的低指针值，并且移动低指针，标志位改成从低指针开始移动
                    arr[i] = arr[j];
                    i++;
                    flag = false;
                }
            } else {
                //如果低指针数据小于中间值，则低指针向右移动
                if (arr[i] < midValue) {
                    i++;
                } else if (arr[i] > midValue) {
                    //如果低指针的值大于中间值，则覆盖高指针停留时的数据，并向左移动高指针。切换为高指针移动
                    arr[j] = arr[i];
                    j--;
                    flag = true;
                }
            }
            //当两个指针的位置相同时，则找到了中间值的位置，并退出循环
            if (i == j) {
                arr[i] = midValue;
                break;
            }
        }
        //然后在对左右两边的列表在进行快速排序
        quickSort(arr, start, i -1);
        quickSort(arr, i + 1, end);
    }

3、插入排序

整个区间被分为：有序区间、无序区间；每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 有序区间: [0, i)
            // 无序区间: [i, array.length)
            int v = array[i];
            // 无序区间的第一个数
            int j = i - 1;
            // 不写 array[j] == v 是保证排序的稳定性
            for (; j >= 0 && array[j] > v; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = v;
        }
    }

4、希尔排序

希尔排序是对插入排序的优化，基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序

    public static void shellSort(int[] arr) {
        //希尔排序（插入排序变种版）
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //i层循环控制步长
            for (int j = i; j < arr.length; j++) {
                //j控制无序端的起始位置
                for (int k = j; k > 0  && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
            //j,k为插入排序，不过步长为i
        }
    }

5、选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i; // 遍历的区间最小的值
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 找到当前遍历区间最小的值的索引
                min = j;
            }
        }
        if (min != i) {
            // 调换
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

6、堆排序

建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况

• 如果所有节点大于孩子节点值，那么这个堆叫做大根堆，堆的最大值在根节点。
• 如果所有节点小于孩子节点值，那么这个堆叫做小根堆，堆的最小值在根节点。

public static void swap(int arr[], int m, int n) {
    int team = arr[m];
    arr[m] = arr[n];
    arr[n] = team;
}

//下移交换 把当前节点有效变换成一个堆(小根)
public static void shiftDown(int arr[], int index, int len)//0 号位置不用
{
    int leftchild = index * 2 + 1;//左孩子
    int rightchild = index * 2 + 2;//右孩子
    if (leftchild >= len) {
        return;
    } else if (rightchild < len && arr[rightchild] < arr[index] && arr[rightchild] < arr[leftchild])//右孩子在范围内并且应该交换
    {
        swap(arr, index, rightchild);//交换节点值
        shiftDown(arr, rightchild, len);//可能会对孩子节点的堆有影响，向下重构
    } else if (arr[leftchild] < arr[index])//交换左孩子
    {
        swap(arr, index, leftchild);
        shiftDown(arr, leftchild, len);
    }
}

//将数组创建成堆
public static void creatHeap(int arr[]) {
    for (int i = arr.length / 2; i >= 0; i--) {
        shiftDown(arr, i, arr.length);
    }
}

public static void heapSort(int arr[]) {
    System.out.println("原始数组为         ：" + Arrays.toString(arr));
    int val[] = new int[arr.length]; //临时储存结果
    //step1建堆
    creatHeap(arr);
    System.out.println("建堆后的序列为  ：" + Arrays.toString(arr));
    //step2 进行n次取值建堆，每次取堆顶元素放到val数组中，最终结果即为一个递增排序的序列
    for (int i = 0; i < arr.length; i++) {
        val[i] = arr[0];//将堆顶放入结果中
        arr[0] = arr[arr.length - 1 - i];//删除堆顶元素，将末尾元素放到堆顶
        shiftDown(arr, 0, arr.length - i);//将这个堆调整为合法的小根堆，注意(逻辑上的)长度有变化
    }
    //数值克隆复制
    for (int i = 0; i < arr.length; i++) {
        arr[i] = val[i];
    }
    System.out.println("堆排序后的序列为:" + Arrays.toString(arr));

}

7、归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

public static void merge(int[] a, int s, int m, int e) {
    //初始化一个从起始s到终止e的一个数组
    int[] temp = new int[(e - s) + 1];
    //左起始指针
    int l = s;
    //右起始指针
    int r = m+1;
    int i = 0;
    //将s-e这段数据在逻辑上一分为二,l-m为一个左边的数组,r-e为一个右边的数组,两边都是有序的
    //从两边的第一个指针开始遍历,将其中小的那个值放在temp数组中
    while (l <= m && r <= e){
        if (a[l] < a[r]){
            temp[i++] = a[l++];
        }else{
            temp[i++] = a[r++];
        }
    }

    //将两个数组剩余的数放到temp中
    while (l <= m){
        temp[i++] = a[l++];
    }
    while (r <= e){
        temp[i++] = a[r++];
    }

    //将temp数组覆盖原数组
    for (int n = 0; n < temp.length; n++) {
        a[s+n] = temp[n];
    }

}

8、基数排序

基数排序是一种很容易理解但是比较难实现(优化)的算法。基数排序也称为卡片排序，基数排序的原理就是多次利用计数排序(计数排序是一种特殊的桶排序)，但是和前面的普通桶排序和计数排序有所区别的是，基数排序并不是将一个整体分配到一个桶中，而是将自身拆分成一个个组成的元素，每个元素分别顺序分配放入桶中、顺序收集，当从前往后或者从后往前每个位置都进行过这样顺序的分配、收集后，就获得了一个有序的数列。

public static void radixSort(int[] arr)//int 类型 从右往左
{
    List<Integer> bucket[] = new ArrayList[10];
    for (int i = 0; i < 10; i++) {
        bucket[i] = new ArrayList<Integer>();
    }
    //找到最大值
    int max = 0;//假设都是正数
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int divideNum = 1;//1 10 100 100……用来求对应位的数字
    while (max > 0) {//max 和num 控制
        for (int num : arr) {
            bucket[(num / divideNum) % 10].add(num);//分配 将对应位置的数字放到对应bucket中
        }
        divideNum *= 10;
        max /= 10;
        int idx = 0;
        //收集 重新捡起数据
        for (List<Integer> list : bucket) {
            for (int num : list) {
                arr[idx++] = num;
            }
            list.clear();//收集完需要清空留下次继续使用
        }
    }
}

9、桶排序

将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。 当然桶排序选择的方案跟具体的数据有关系，桶排序是一个比较广泛的概念，并且计数排序是一种特殊的桶排序，基数排序也是建立在桶排序的基础上。在数据分布均匀且每个桶元素趋近一个时间复杂度能达到O(n),但是如果数据范围较大且相对集中就不太适合使用桶排序。

public static void backetSort(int[] arr) {
    List[] buckets=new ArrayList[5];
    for(int i=0;i<buckets.length;i++)//初始化
    {
        buckets[i]=new ArrayList<Integer>();
    }
    for(int i=0;i<arr.length;i++)//将待排序序列放入对应桶中
    {
        int index=arr[i]/10;//对应的桶号
        buckets[index].add(arr[i]);
    }
    for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
    {
        buckets[i].sort(null);
        for(int j=0;j<buckets[i].size();j++)//顺便打印输出
        {
            System.out.print(buckets[i].get(j)+" ");
        }
    }
}

10、计数排序

计数排序是一种特殊的桶排序，每个桶的大小为1，每个桶不再用List表示，而通常用一个值用来计数。

在设计具体算法的时候，先找到最小值min，再找最大值max。然后创建这个区间大小的数组,从min的位置开始计数，这样就可以最大程度地压缩空间，提高空间的使用效率。

public static void countSort(int arr[]) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++)//找到max和min
    {
        if (arr[i] < min) {
            min = arr[i];
        }
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int count[] = new int[max - min + 1];//对元素进行计数
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }
    //排序取值
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i + min;//有min才是真正值
        }
    }
}