这些基础的算法真是容易忘，一段时间不写细节就不会处理了。在此记录一下。

1、初级的桶排序

如需要对10以内的数进行排序，可以先初始化一个长度为10的数组。然后遍历，遍历到哪个数就将数组对应的下标加1，如遍历到3，则a[3]++。整个遍历结束后，再通过输出数组即可得到有序数据。需要注意的是，a[i]是多少则需要打印多少次。
这种算法相当于是用下标记录数据，用值记录次数。

该算法的优点是快速，其时间复杂度是O(n)。但是该算法的缺点是占用过多的空间，如果需要对10000个数排序，那么需要申请长度10000数组来存储，相当于用空间换时间。

参考代码如下：

/**
 * 简单的桶排序（实际的桶排序要比这个复杂）
 * @param a 待排序的数组
 */
public static void bucketSort(int[] a) {
    // 先定义桶
    int[] tong = new int[10];      // 假设a数组存放的是10以内的数据，故需要定义10个桶
    for (int i = 0; i < tong.length; i++) {
        tong[i] = 0;   // 初始化桶中的每一位数 （假设待排序的数中不存在-1）
    }

    // 遍历待排数据，将数据放入到相应的桶中
    for (int i = 0; i < a.length; i++) {
        tong[a[i]]++;
    }

    // 输出桶中的数据，即已经排序好的数据
    for (int i = 0; i < tong.length; i++) {
        // 只打印存放了数据的桶
        if (tong[i] != 0) {
            for (int j = 0; j < tong[i]; j++) {
                // 在某个桶的位置上重复了几次，那么就打印多少次
                System.out.print(i + ",");
            }
        }
    }
}

2、冒泡排序

冒泡排序的思想是通过依次比较相邻的两个数的，如果顺序不对，则进行调换。在每一真趟的的冒泡的过程中，只能将一个数归位。在对n个数排序中，只需将n-1归位即可。故排序n个的数只需要n-1趟。该算法的优点是理解及实现难度不在，但是时间复杂度为O(n2)。

参考代码如下：

/**
 * 冒泡排序
 * @param a
 */
public static void bubbleSort(int[] a) {
    // 将一个元素依次与其他元素比较，冒泡到最后为一趟
    // n个元素只需要将n - 1个数归位，即需要n - 1趟

    int count = a.length - 1;   // 需要比较的次数
    for (int i = 1; i <= count; i++) {

        boolean hasSwap = false;    // 当前趟有没有发生交换，这样可以优化一下冒泡排序算法。

        // 第i趟时，只需比较count-i+1次，因为乘余的数已经排好序了。
        for (int j = 0; j <= count - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = tmp;
                hasSwap = true;
            }
        }

        // 如果没有发生过交换，则说明已经排好序了
        if (!hasSwap) {
            System.out.println("第" + i + "趟排序已经排好的，结束排序");
            break;
        }
    }

    /**
     * 冒泡时间复杂度推导：
     * 第一趟要迭代 n - 1次
     * 第二趟      n - 2次
     *
     *
     * 第n-1趟，   1次
     * 累积求和即是 (n - 1) + (n - 2) + (n - 3) + ..... + 1;
     * n (n - 1） / 2
     * 故时间复杂度是： O(n2)
     */
}

3、快速排序

快速排序是一种基于二分的思想。由于其比较是跳跃式的，故比冒泡排序要快很多，但是最差的情况下等同于冒泡排序。

参考代码如下：

/**
 * 快速排序
 *
 * @param a
 * @param left 排序的范围 左起点
 * @param right 右起点
 */
public static void quickSort(int[] a, int left, int right) {
    // 递归停止条件
    if (left > right) {
        return;
    }

    int i = left;
    int j = right;
    int temp = a[left];    // 选定第一个元素为基准元素

    while (i < j) {
        // 因为基准元素是最左边的，故首先要从最右边开始找到一个比基准元素小的元素，j为其索引。顺序很重要。同时这里是a[j] >= temp,不能掉了等号。
        while (a[j] >= temp && i < j) {
            j--;
        }

        // 从左边开始找到一个比基准元素大的元素,i为其索引
        while (a[i] <= temp && i < j) {
            i++;
        }

        // 当i与j没有相遇时才交换，相遇时则表明此次基准数已经归位
        if (i < j) {
            // 交换i和j的位置
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    // i 与 j 相遇后将基准元素与i处的互换
    a[left] = a[i];
    a[i] = temp;

    // 将基准元素左边的排序
    quickSort(a, left, i - 1);
    // 同上，将基准元素右边的排序
    quickSort(a, j + 1, right);
}

4、插入排序

for (int i = 0; i < nums.length; i++) {
	// 当前值与前一个相比， 始终记住这个。 
    int j = i - 1;
    int tmp = nums[i];

    while (j >= 0 && tmp < nums[j]) {
    	// j往后挪动，因为j + 1 = i，当前值已经保存在tmp了，故无需担心nums[j + 1]的值被覆盖。 
        nums[j + 1] = nums[j];
        j--;
    }
	
	// 找到相应的位置挺好入
    nums[j + 1] = tmp;
}

5、Shell排序

fun shellSort(a: IntArray) {

        var size = a.size
        var gap = size / 2     // 初始gap为数组长度的一半
        while (gap > 0) {

            // 如下代码的思想为插入排序思想
            for (i in gap until size) {
                var tmp = a[i]
                var j = i - gap // 如果此时j小于0，则会跳过while循环。a[j+gap]即为a[i]
                while (j >= 0 && a[j] > tmp) {
                    a[j + gap] = a[j]
                    j -= gap
                }
                a[j + gap] = tmp
            }

            gap /= 2    // gap每次减半
        }
    }