十大经典排序算法

简介

算法分类

算法分类.png

复杂度

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
时间/空间复杂度详解点击这里

以下找的图存在微小差异：

复杂度.png

n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存

一、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

动图演示

Bubble Sort.gif

代码实现

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成，最佳时间复杂度需要设置此标记。
        boolean flag = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j + 1] < arr[j]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
}

最佳情况： $T(n) = O(n)$ 最差情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(n^2)$

二、选择排序（Selection Sort）

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

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

动图演示

Selection Sort.gif

代码实现

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

算法分析

最佳情况： $T(n) = O(n^2)$ 最差情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(n^2)$
表现最稳定（是时间复杂度的稳定）的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

三、插入排序（Insertion Sort）

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

动图演示

Insertion Sort.gif

代码实现

public static void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 取出当前元素
        int current = arr[i + 1];
        // 上一个元素的坐标
        int preIndex = i;
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

最佳情况： $T(n) = O(n)$ 最坏情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(n^2)$

四、希尔排序（Shell Sort）

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法描述

希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

Shell Sort.gif

过程演示

shell sort.png

代码实现

public static void shellSort(int[] arr) {
    int gap = arr.length / 2;
    int temp;
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            temp = arr[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && arr[preIndex] > temp) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = temp;
        }
        gap /= 2;
    }
}

最佳情况： $T(n) = O(nlog_2n)$ 最坏情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(nlog_2n)$

增量序列如果取得不好，效率比直接插入排序还要低

image.png

针对此问题整理出了下面这些增量序列：Hibbard增量序列、Knuth增量序列、Sedgewick增量序列等等

Hibbard 增量序列

Hibbard增量序列的通项公式为： $𝐷_𝑘=2^𝑘−1$
Hibbard增量序列的递推公式为： $D_1=1,D_i=2∗D_{i−1}+1$
结果：{1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191...}
最坏时间复杂度为 $𝑂(𝑁^{3 \over 2})$ ；平均时间复杂度约为 $𝑂(𝑁^{5 \over 4})$

Sedgewick 增量序列

Sedgewick增量序列的通项公式为： $𝐷=9∗4^𝑖−9∗2^𝑖+1或4^𝑖−3∗2^𝑖+1$
结果：{1, 5, 19, 41, 109, 209, 505, 929, 2161...}
最坏时间复杂度为 $𝑂(𝑁^{4/3})$ ；平均时间复杂度约为 $𝑂(𝑁^{7/6})$

五、归并排序（Merge Sort）

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 $O(n logn)$ 的时间复杂度。代价是需要额外的内存空间。

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

算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

动图演示

Merge Sort.gif

代码实现

public static int[] mergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(mergeSort(left), mergeSort(right));
}

/**
 * 将两段排序好的数组合并为一个排序的数组
 */
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    // index新数组坐标，i左数组下标，j右数组下标
    for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        if (i == left.length) // 左边数组为空时候，直接遍历右边数组到新数组
            result[index] = right[j++];
        else if (j == right.length) // 右边数组为空时候，直接遍历左边数组到新数组
            result[index] = left[i++];
        else if (left[i] > right[j])
            result[index] = right[j++];
        else
            result[index] = left[i++];
    }
    return result;
}

最佳情况： $T(n) = O(nlogn)$ 最差情况： $T(n) = O(nlogn)$ 平均情况： $T(n) = O(nlogn)$

六、快速排序（Quick Sort）

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素(通过不同的方式挑选出基准值)，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序的优化是对基准值的选取

随机选择
取中位数，也就是取首、尾、中间数三个数的中位数做为基准
以下是选取首位作为基准值

动图演示

Quick Sort.gif

代码实现

两路快排，相同值分布两侧，防止一侧过多，导致递归两路悬殊差距过大

public static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
}

public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int midIndex = partition(array, low, high);
        // 递归划分划分左右子数组，让左右子数组有序
        quickSort(array, low, midIndex - 1);
        quickSort(array, midIndex + 1, high);
    }
}

public static int partition(int[] array, int low, int high) {
    // 设置起始值作为基准
    int index = low;
    int pivot = array[low];
    while (low < high) {
        // 从末尾从前遍历，先从后遍历防止当数组有序时候，从前遍历会一直找到结尾，会把末尾最大数替换到最开始
        while (low < high && array[high] >= pivot) {
            high--;
        }
        while (low < high && array[low] <= pivot) {
            low++;
        }
        // low,high调换位置
        swap(array, low, high);
    }
    // 基准值和中间位置替换
    arr[index] = arr[low];
    arr[low] = pivot;
    // 当low=high时候停止划分,返回基准值坐标
    return low;
}

private static void swap(int[] array, int i, int j) {
    if (i < j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

优化:两路快排,不用swap, 用直接赋值，两数交换涉及到第三个变量temp的操作，多了读写操作

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

当大量数据，且重复数多时，用三路快排，一路小于基准值，一路等于基准值，一路大于基准值

public static void quickSort2(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        int[] mid = partition4(arr, start, end);
        
        quickSort(arr, start, mid[0]);
        quickSort(arr, mid[1], end);
    }
}

public static int[] partition4(int[] arr, int left, int right) {
    int pivot = arr[left];
    int current = left;

    while (current <= right) {
        if (arr[current] == pivot) {
            current++;
        } else if (arr[current] < pivot) {
            swap(arr, current++, left++);
        } else {
            swap(arr, current, right--);
        }
    }
    // [left,right]闭区间都与基准值相等
    return new int[]{left - 1, right + 1};
}

public static void swap(int[] arr, int i1, int i2) {
    if (i1 != i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }
}

在每次都能平分数组的情况是最优的 $nlogn$
每次都找出最大或最小的数是最差的 $n^2$
最佳情况： $T(n) = O(nlogn)$ 最差情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(nlogn)$

七、堆排序（Heap Sort）

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

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

i为当前索引
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动图演示

Heap Sort.gif

代码实现

public static void heapSort(int[] arr) {
    int len = arr.length;

    // 构建大顶堆,从最后开始往上构建，节点大于叶子节点
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }

    // 调整堆结构+交换堆顶元素与末尾元素
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        adjustHeap(arr, 0, i);// 因下面有序所以从上往下比较
    }
}

/**
 * 调整使之成为最大堆
 */
public static void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];//先取出当前元素i

    for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {//从i节点的左子节点开始，也就是2i+1处开始
        if (k + 1 < len && arr[k] < arr[k + 1]) {//如果左子节点小于右子节点，k指向右子节点
            k++;
        }
        if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp;//将temp值放到最终的位置
}

/**
 * 交换元素
 */
public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

最佳情况： $T(n) = O(nlogn)$ 最差情况： $T(n) = O(nlogn)$ 平均情况： $T(n) = O(nlogn)$

八、计数排序（Counting Sort）

详情参考：https://www.cnblogs.com/xiaochuan94/p/11198610.html
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

动图演示

Counting Sort.gif

代码实现

public static int[] countingSort(int[] arr) {
    // 找出最大最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }

    // 计数数组，计算原始值在某个索引的数量，某些索引会无值
    int[] count = new int[max - min + 1];

    for (int value : arr) {
        // 原始值 - min = 索引
        count[value - min]++;
    }

    // 结果数组
    int[] result = new int[arr.length];
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            // 索引 + min = 原始值
            result[index++] = i + min;
            // 计数减1
            count[i]--;
        }
    }
    return result;
}

另一种方式：计量数组存储的是在数据在最终数组中的位置（索引+1）

public static int[] countingSort1(int[] arr) {
    // 找出最大最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }

    // 计数数组，计算原始值在某个索引的数量，某些索引会无值
    int[] count = new int[max - min + 1];

    for (int value : arr) {
        // 原始值 - min = 索引
        count[value - min]++;
    }

    // 计数数组变形，计算原始值存入新数组的最后索引位置 + 1,即新元素值是前面元素累加之和值 count[i+1]+=count[i]
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 结果数组
    int[] result = new int[arr.length];
    // 如果要稳定性，下面需要倒序遍历
    // for (int i = arr.length - 1; i >= 0; i--) {
    for (int i = 0; i < arr.length; i++) {
        // 原始值 - 最小值 = 索引值，count[索引]=在第几个位置
        result[count[arr[i] - min] - 1] = arr[i];
        // 计数索引值数-1，如果下个相同值进来就在前一位
        count[arr[i] - min]--;
    }
    return result;
}

算法分析

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

最佳情况： $T(n) = O(n+k)$ 最差情况： $T(n) = O(n+k)$ 平均情况： $T(n) = O(n+k)$

九、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

算法描述

人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
从不是空的桶里把排好序的数据拼接起来。

注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

图片演示

Bucket Sort.png

代码实现

public static int[] bucketSort(int[] arr) {
    // 找出最大最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }

    //例如：1,4,5,7,18,20,31,20,14,22
    //每个桶区间： 1-10,11-20,21-30,31--
    int bucketCount = (max - min) / arr.length + 1; // 4

    List<List<Integer>> bucketArr = new ArrayList<>(bucketCount);
    for (int i = 0; i < bucketCount; i++) {
        bucketArr.add(new ArrayList<>());
    }

    // 将元素放入桶
    for (int i = 0; i < arr.length; i++) {
        int num = (arr[i] - min) / arr.length;
        bucketArr.get(num).add(arr[i]);
    }

    // 桶内排序
    for (List<Integer> bucket : bucketArr) {
        // java排序采用多种方式，杠杠的
        Collections.sort(bucket);
    }

    int[] result = new int[arr.length];
    int index = 0;
    for (List<Integer> buckets : bucketArr) {
        for (Integer bucket : buckets) {
            result[index++] = bucket;
        }
    }
    return result;
}

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

最佳情况： $T(n) = O(n)$ 最差情况： $T(n) = O(n^2)$ 平均情况： $T(n) = O(n+k)$

十、基数排序（Radix Sort）

详情参考：https://blog.csdn.net/u014231646/article/details/80267468
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),n为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

Radix Sort.gif

代码实现

public static void radixSort(int[] arr) {

    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }

    // 求关键字个数，个、十、百...，需要算最大数的位数
    int maxDigit = 0;
    while (max > 0) {
        max /= 10;
        maxDigit++;
    }

    // 每位可能0~9，设置10个桶
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        buckets.add(new ArrayList<>());
    }

    for (int i = 0; i < maxDigit; i++) {
        // 先个位 x%10->再十位x%100/10->再百位x%1000/100...规律如下
        for (int j = 0; j < arr.length; j++) {
            int key = arr[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            buckets.get(key).add(arr[j]);
        }

        // 分配完后，将桶中元素依次复制回数组，移除桶中元素
        int index = 0;
        for (int j = 0; j < buckets.size(); j++) {
            List<Integer> bucket = buckets.get(j);
            for (int k = 0; k < bucket.size(); k++) {
                arr[index++] = bucket.get(k);
            }
            bucket.clear();
        }
    }
}

算法分析

最佳情况： $T(n) = O(n * k)$ 最差情况： $T(n) = O(n * k)$ 平均情况： $T(n) = O(n * k)$

基数排序有两种方法：
MSD 从高位开始进行排序 LSD 从低位开始进行排序

此篇文章网上借鉴复制过来，方便自己记忆，如有侵权请联系作者

最后编辑于：2020.12.11 17:09:03

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,544评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,430评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,764评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,193评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,216评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,182评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,063评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,917评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,329评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,543评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,722评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,425评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,019评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,671评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,825评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,729评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,614评论 2赞 353

十大经典排序算法

简介

算法分类

复杂度

一、冒泡排序（Bubble Sort）

算法描述

动图演示

代码实现

二、选择排序（Selection Sort）

算法描述

动图演示

代码实现

算法分析

三、插入排序（Insertion Sort）

算法描述

动图演示

代码实现

四、希尔排序（Shell Sort）

算法描述

动图演示

过程演示

代码实现

Hibbard 增量序列

Sedgewick 增量序列

五、归并排序（Merge Sort）

算法描述

动图演示

代码实现

六、快速排序（Quick Sort）

算法描述

动图演示

代码实现

七、堆排序（Heap Sort）

算法描述

动图演示

代码实现

八、计数排序（Counting Sort）

算法描述

动图演示

代码实现

算法分析

九、桶排序（Bucket Sort）

算法描述

图片演示

代码实现

算法分析

十、基数排序（Radix Sort）

算法描述

动图演示

代码实现

算法分析

推荐阅读更多精彩内容