参考链接：https://www.pdai.tech/md/algorithm/alg-sort-overview.html

image.png
重点关注快速排序，希尔排序，归并排序

交换排序

冒泡排序（Bulle Sort）

介绍

它会遍历数列长度-1次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾。采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

代码

public int[] sortArrayBubble(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    return nums;
}

快速排序（Quick Sort）

介绍

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码

/**
 * 快速排序
 * @param l 数组的左边界
 * @param r 数组的右边界
 */
public void sortArrayQuick(int[] a, int l, int r) {
    if (l < r) {
        int i = l;
        int j = r;
        int x = a[i];
        while (i < j) {//数据分成两块
            while (i < j && a[j] > x) j--; // 从右向左找第一个小于x的数
            if (i < j) a[i++] = a[j];
            while (i < j && a[i] < x) i++; // 从左向右找第一个大于x的数
            if (i < j) a[j--] = a[i];
        }
        a[i] = x;       //定位基数
        sortArrayQuick(a, l, i - 1); //递归调用
        sortArrayQuick(a, i + 1, r); //* 递归调用
    }
}

插入排序

插入排序（Insert Sort）

介绍

直接插入排序(Straight Insertion Sort)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

代码

//插入排序
public static void sortArrayInsert(int[] array) {
    int i, j, k;
    for (i = 1; i < array.length; i++) {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (array[j] < array[i])
                break;
        //如找到了一个合适的位置
        if (j != i - 1) {
            //将比a[i]大的数据向后移
            int temp = array[i];
            for (k = i - 1; k > j; k--)
                array[k + 1] = array[k];
            //将a[i]放到正确位置上
            array[k + 1] = temp;
        }
    }

希尔排序（Shell Sort）

介绍

希尔排序实质上是一种分组插入方法。对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

代码

//希尔排序
int n = array.length;
// gap为步长，每次减为原来的一半。
for (int gap = n / 2; gap > 0; gap /= 2) {
    // 共gap个组，对每一组都执行直接插入排序
    for (int i = 0; i < gap; i++) {
        for (int j = i + gap; j < n; j += gap) {
            // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
            if (array[j] < array[j - gap]) {
                int tmp = array[j];
                int k = j - gap;
                while (k >= 0 && array[k] > tmp) {
                    array[k + gap] = array[k];
                    k -= gap;
                }
                array[k + gap] = tmp;
            }
        }
    }
}

选择排序

简单选择排序（Selection Sort）

介绍

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

代码

//选择排序
public static void sortArraySelect(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int min = i;
        // 找出"array[i+1] ... array[n]"之间的最小元素，并赋值给min。
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[min])
                min = j;
        }
        // 若min!=i，则交换 array[i] 和 array[min]。
        // 交换之后，保证了array[0] ... array[i] 之间的元素是有序的。
        if (min != i) {
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }
    }
}

堆排序(Heap Sort)

介绍

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

代码

/*
 * (最大)堆的向下调整算法
 *
 * 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
 */
public static void maxHeapDown(int[] a, int start, int end) {
    int c = start;            // 当前(current)节点的位置
    int l = 2*c + 1;        // 左(left)孩子的位置
    int tmp = a[c];            // 当前(current)节点的大小

    for (; l <= end; c=l,l=2*l+1) {
        // "l"是左孩子，"l+1"是右孩子
        if ( l < end && a[l] < a[l+1])
            l++;        // 左右两孩子中选择较大者，即m_heap[l+1]
        if (tmp >= a[l])
            break;        // 调整结束
        else {            // 交换值
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 * 堆排序(从小到大)
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
public static void heapSortAsc(int[] a, int n) {
    int i,tmp;

    // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
    for (i = n / 2 - 1; i >= 0; i--)
        maxHeapDown(a, i, n-1);

    // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for (i = n - 1; i > 0; i--) {
        // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
        // 即，保证a[i-1]是a[0...i-1]中的最大值。
        maxHeapDown(a, 0, i-1);
    }
}

/*
 * (最小)堆的向下调整算法
 *
 * 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
 */
public static void minHeapDown(int[] a, int start, int end) {
    int c = start;            // 当前(current)节点的位置
    int l = 2*c + 1;        // 左(left)孩子的位置
    int tmp = a[c];            // 当前(current)节点的大小

    for (; l <= end; c=l,l=2*l+1) {
        // "l"是左孩子，"l+1"是右孩子
        if ( l < end && a[l] > a[l+1])
            l++;        // 左右两孩子中选择较小者
        if (tmp <= a[l])
            break;        // 调整结束
        else {            // 交换值
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 * 堆排序(从大到小)
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
public static void heapSortDesc(int[] a, int n) {
    int i,tmp;

    // 从(n/2-1) --> 0逐次遍历每。遍历之后，得到的数组实际上是一个最小堆。
    for (i = n / 2 - 1; i >= 0; i--)
        minHeapDown(a, i, n-1);

    // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for (i = n - 1; i > 0; i--) {
        // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。
        // 即，保证a[i-1]是a[0...i-1]中的最小值。
        minHeapDown(a, 0, i-1);
    }
}

归并排序(Merge Sort)

介绍

将两个的有序数列合并成一个有序数列，我们称之为"归并"。归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

/*
 * 将一个数组中的两个相邻有序区间合并成一个
 *
 * 参数说明:
 *     a -- 包含两个有序区间的数组
 *     start -- 第1个有序区间的起始地址。
 *     mid   -- 第1个有序区间的结束地址。也是第2个有序区间的起始地址。
 *     end   -- 第2个有序区间的结束地址。
 */
public static void merge(int[] a, int start, int mid, int end) {
    int[] tmp = new int[end-start+1];    // tmp是汇总2个有序区的临时区域
    int i = start;            // 第1个有序区的索引
    int j = mid + 1;        // 第2个有序区的索引
    int k = 0;                // 临时区域的索引

    //全部存在tmp中，并且排序
    while(i <= mid && j <= end) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i <= mid)
        tmp[k++] = a[i++];

    while(j <= end)
        tmp[k++] = a[j++];

    // 将排序后的元素，全部都整合到数组a中。
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];
}

/*
 * 归并排序(从上往下)
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     start -- 数组的起始地址
 *     endi -- 数组的结束地址
 */
public static void mergeSortUp2Down(int[] a, int start, int end) {
    if(a==null || start >= end)
        return ;

    int mid = (end + start)/2;
    mergeSortUp2Down(a, start, mid); // 递归排序a[start...mid]
    mergeSortUp2Down(a, mid+1, end); // 递归排序a[mid+1...end]

    // a[start...mid] 和 a[mid...end]是两个有序空间，
    // 将它们排序成一个有序空间a[start...end]
    merge(a, start, mid, end);
}

/*
 * 对数组a做若干次合并: 数组a的总长度为len，将它分为若干个长度为gap的子数组；
 *             将"每2个相邻的子数组" 进行合并排序。
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     len -- 数组的长度
 *     gap -- 子数组的长度
 */
public static void mergeGroups(int[] a, int len, int gap) {
    int i;
    int twolen = 2 * gap;    // 两个相邻的子数组的长度

    // 将"每2个相邻的子数组" 进行合并排序。
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
        merge(a, i, i+gap-1, i+2*gap-1);

    // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。
    // 将该子数组合并到已排序的数组中。
    if ( i+gap-1 < len-1)
        merge(a, i, i + gap - 1, len - 1);
}

/*
 * 归并排序(从下往上)
 *
 * 参数说明:
 *     a -- 待排序的数组
 */
public static void mergeSortDown2Up(int[] a) {
    if (a==null)
        return ;

    for(int n = 1; n < a.length; n*=2)
        mergeGroups(a, a.length, n);
}

代码

桶排序（Bucket Sort）

介绍

桶排序(Bucket Sort)的原理很简单，将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

代码

/*
 * 桶排序
 *
 * 参数说明:
 *     a -- 待排序数组
 *     max -- 数组a中最大值的范围
 */
public static void bucketSort(int[] a, int max) {
    int[] buckets;

    if (a == null || max < 1)
        return;

    // 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
    buckets = new int[max];

    // 1. 计数
    for (int i = 0; i < a.length; i++)
        buckets[a[i]]++;

    // 2. 排序
    for (int i = 0, j = 0; i < max; i++) {
        while ((buckets[i]--) > 0) {
            a[j++] = i;
        }
    }
}

基数排序（Radix Sort）

介绍

将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是: 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

代码

/*
 * 获取数组a中最大值
 *
 * 参数说明:
 *     a -- 数组
 *     n -- 数组长度
 */
private static int getMax(int[] a) {
    int max;

    max = a[0];
    for (int i = 1; i < a.length; i++)
        if (a[i] > max)
            max = a[i];

    return max;
}

/*
 * 对数组按照"某个位数"进行排序(桶排序)
 *
 * 参数说明:
 *     a -- 数组
 *     exp -- 指数。对数组a按照该指数进行排序。
 *
 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
 *    (01) 当exp=1表示按照"个位"对数组a进行排序
 *    (02) 当exp=10表示按照"十位"对数组a进行排序
 *    (03) 当exp=100表示按照"百位"对数组a进行排序
 *    ...
 */
private static void countSort(int[] a, int exp) {
    //int output[a.length];    // 存储"被排序数据"的临时数组
    int[] output = new int[a.length];    // 存储"被排序数据"的临时数组
    int[] buckets = new int[10];

    // 将数据出现的次数存储在buckets[]中
    for (int i = 0; i < a.length; i++)
        buckets[(a[i] / exp) % 10]++;

    // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
    for (int i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];

    // 将数据存储到临时数组output[]中
    for (int i = a.length - 1; i >= 0; i--) {
        output[buckets[(a[i] / exp) % 10] - 1] = a[i];
        buckets[(a[i] / exp) % 10]--;
    }

    // 将排序好的数据赋值给a[]
    for (int i = 0; i < a.length; i++)
        a[i] = output[i];

    output = null;
    buckets = null;
}

/*
 * 基数排序
 *
 * 参数说明:
 *     a -- 数组
 */
public static void radixSort(int[] a) {
    int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    int max = getMax(a);    // 数组a中的最大值

    // 从个位开始，对数组a按"指数"进行排序
    for (exp = 1; max / exp > 0; exp *= 10)
        countSort(a, exp);
}