java排序算法代码,java 排序算法 收藏 0

堆排序实战：轻松实现高效排序，附详细Java代码

Hello，大家好！我是你们的小米，今天又来给大家分享干货啦！最近很多小伙伴们都对排序算法产生了浓厚的兴趣，继上次分享了“手写”之后，今天我们再来搞搞堆排（Heap Sort），带大家一起动手手写堆排算法吧！

堆排序是一种基于二叉堆（Binary Heap）这种数据结构的排序算法，属于选择排序的一种。堆排序的时间复杂度为 O(n log n)，在最坏的情况下依然表现稳定。和快速排序相比，它没有那样的递归深度问题，因此适合用在对稳定性要求高且空间不允许递归的场景下。

堆排序主要有两个步骤：

• 构建大顶堆（或小顶堆）：根据数组构建出一个大顶堆（父节点的值大于子节点），这样堆顶元素就是最大值。
• 交换堆顶元素与末尾元素并调整堆：将堆顶元素（最大值）与末尾元素交换，缩小堆的范围，重新调整堆。循环此过程，直到整个数组有序。

我们以大顶堆为例来讲解堆排序的核心原理。首先，我们将数组看成一棵完全二叉树，根节点为最大元素。通过堆调整（Heapify）操作，保持堆的结构特性。之后，我们将堆顶元素与最后一个元素交换，再对剩余元素重新调整成堆，最终完成排序。

• 构建堆：将无序数组调整成大顶堆。
• 排序：依次将堆顶元素与末尾元素交换，缩小堆的范围，并重新调整堆。

好啦，理论讲完了，接下来进入我们的实战环节。我们使用Java来手写一个堆排序算法吧！

上面的代码实现了堆排序的核心步骤。下面我来一步步讲解：

• 构建初始大顶堆：我们从数组的中间位置开始向前遍历（for (int i = n / 2 – 1; i >= 0; i–)），因为数组的后一半是叶子节点，不需要调整堆。通过调用 heapify 函数，将每一个非叶子节点调整成大顶堆。
• 堆的调整（heapify）：heapify 函数用于调整堆的结构。它接收三个参数：数组 arr、数组的长度 n 和当前节点的索引 i。该函数会比较当前节点、左子节点和右子节点的大小，确保父节点是最大值。如果发现子节点比父节点大，则交换节点，然后递归调用 heapify 函数对交换后的子树继续调整。
• 排序：构建好大顶堆后，开始排序。在每次循环中，将堆顶元素（最大值）与数组的最后一个元素交换，然后将剩余的元素重新调整为大顶堆。这个过程会一直进行到堆的范围缩小到只剩一个元素为止，整个数组最终有序。

堆排序的时间复杂度是 O(n log n)，这里的 n 是数组的大小。构建大顶堆的时间复杂度为 O(n)，每次调整堆的时间复杂度为 O(log n)，总共需要调整 n-1 次，所以总的时间复杂度为 O(n log n)。

堆排序是原地排序算法，也就是说它只需要常数个额外的空间，空间复杂度为 O(1)。这一点相较于更为优越，在最坏情况下的空间复杂度可能会达到 O(n)（因为递归深度过深）。

优点：

• 时间复杂度稳定：不管输入数组的状态如何，堆排序的时间复杂度总是 O(n log n)。
• 空间复杂度低：堆排序是原地排序，空间复杂度为 O(1)，比更节省空间。

缺点：

• 不稳定排序：堆排序是不稳定排序，相同元素的相对顺序可能会被改变。
• 不如快：尽管堆排序的时间复杂度和相同，但是堆排序的常数系数较大，实际运行速度往往比不上。

堆排序是一种比较实用的排序算法，特别适用于对稳定性要求高、递归深度限制较大、以及空间资源有限的场景。尽管它的实际表现可能不如，但它在一些特定情况下仍然是非常有价值的工具。

如果你是算法爱好者，推荐大家动手写一写堆排序，深入理解算法的原理！如果你有什么不懂的地方，欢迎在评论区留言哦，我会积极回复的！今天的分享就到这里啦，我们下次再见！

我是小米，一个喜欢分享技术的29岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！

Java常用的7大排序算法汇总

这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！

1.插入排序算法

插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortInsert(int[] array){

6. for(int i=1;i<array.length;i++){

7. int temp = array[i];

8. int j;

9. for(j=i-1;j >= 0 && temp< array[j]; j–){

10. array[j + 1] = array[j];

11. }

12. array[j + 1] = temp;

13. }

14. return array;

15. }

2.选择排序算法

选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortSelect(int[] arr){

6. for (int i = 0; i < arr.length; i++) {

7. int miniPost = i;

8. for (int m = i + 1; m < arr.length; m++) {

9. if (arr[m] < arr[miniPost]) {

10. miniPost = m;

11. }

12. }

13. if (arr[i] > arr[miniPost]) {

14. int temp;

15. temp = arr[i];

16. arr[i] = arr[miniPost];

17. arr[miniPost] = temp;

18. }

19. }

20. return arr;

21. }

3.冒泡排序算法

冒泡排序是將比較大的數字沉在最下面，较小的浮在上面

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortBubble(int[] array){

6. int temp;

7. // 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）

8. for(int i=0;i<array.length-1;i++){

9. for (int j = array.length – 1; j > i; j–) {

10. if (array[j] < array[j – 1]) {

11. temp = array[j];

12. array[j] = array[j – 1];

13. array[j – 1] = temp;

14. }

15. }

16. }

17. return array;

18. }

4.快速排序算法

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大。

可随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortQuick(int[] array){

6. return quickSort(array, 0, array.length-1);

7. }

8. private int quickSort(int[] arr, int low, int heigh) {

9. if (low < heigh) {

10. int division = partition(arr, low, heigh);

11. quickSort(arr, low, division – 1);

12. quickSort(arr, division + 1, heigh);

13. }

14. return arr;

15. }

16. // 分水岭,基位,左边的都比这个位置小,右边的都大

17. private int partition(int[] arr, int low, int heigh) {

18. int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录

19. while (low < heigh) { //从表的两端交替向中间扫描

20. while (low < heigh && arr[heigh] >= base) {

21. heigh–;

22. }

23. // base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大

24. swap(arr, heigh, low);

25. while (low < heigh && arr[low] <= base) {

26. low++;

27. }

28. // 遇到左边比base值大的了,换位置

29. swap(arr, heigh, low);

30. }

31. // now low = heigh;

32. return low;

33. }

34. private void swap(int[] arr, int a, int b) {

35. int temp;

36. temp = arr[a];

37. arr[a] = arr[b];

38. arr[b] = temp;

39. }

5.合并排序算法

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. private int sort(int[] nums, int low, int high) {

6. int mid = (low + high) / 2;

7. if (low < high) {

8. // 左边

9. sort(nums, low, mid);

10. // 右边

11. sort(nums, mid + 1, high);

12. // 左右归并

13. merge(nums, low, mid, high);

14. }

15. return nums;

16. }

17. private void merge(int[] nums, int low, int mid, int high) {

18. int temp = new int[high – low + 1];

19. int i = low;// 左指针

20. int j = mid + 1;// 右指针

21. int k = 0;

22. // 把较小的数先移到新数组中

23. while (i <= mid && j <= high) {

24. if (nums[i] < nums[j]) {

25. temp[k++] = nums[i++];

26. } else {

27. temp[k++] = nums[j++];

28. }

29. }

30. // 把左边剩余的数移入数组

31. while (i <= mid) {

32. temp[k++] = nums[i++];

33. }

34. // 把右边边剩余的数移入数组

35. while (j <= high) {

36. temp[k++] = nums[j++];

37. }

38. // 把新数组中的数覆盖nums数组

39. for (int k2 = 0; k2 < temp.length; k2++) {

40. nums[k2 + low] = temp[k2];

41. }

42. }

43. public int sortMerge(int[] array) {

44. return sort(array, 0, array.length – 1);

45. }

6.希尔排序算法

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组。

以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ， 则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序。

此时的数组已经基本上好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortShell(int[] array) {

6. // 取增量

7. int step = array.length / 2;

8. while (step >= 1) {

9. for (int i = step; i < array.length; i++) {

10. int temp = array[i];

11. int j = 0;

12. // 跟插入排序的区别就在这里

13. for (j = i – step; j >= 0 && temp < array[j]; j -= step) {

14. array[j + step] = array[j];

15. }

16. array[j + step] = temp;

17. }

18. step /= 2;

19. }

20. return array;

21. }

7.堆排序算法

本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换，剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortHeap(int[] array) {

6. buildHeap(array);// 构建堆

7. int n = array.length;

8. int i = 0;

9. for (i = n – 1; i >= 1; i–) {

10. swap(array, 0, i);

11. heapify(array, 0, i);

12. }

13. return array;

14. }

15. private void buildHeap(int[] array) {

16. int n = array.length;// 数组中元素的个数

17. for (int i = n / 2 – 1; i >= 0; i–)

18. heapify(array, i, n);

19. }

20. private void heapify(int[] A, int idx, int max) {

21. int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）

22. int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）

23. int largest = 0;// 寻找3个节点中最大值节点的下标

24. if (left < max && A[left] > A[idx])

25. largest = left;

26. else

27. largest = idx;

28. if (right < max && A[right] > A[largest])

29. largest = right;

30. if (largest != idx) {

31. swap(A, largest, idx);

32. heapify(A, largest, max);

33. }

34. }

35. }

36. // 建堆函数，认为【s，m】中只有 s

37. // 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================

38. public static void heapAdjust(int[] array, int s, int m) {

39. // 用0下标元素作为暂存单元

40. array[0] = array[s];

41. // 沿孩子较大的结点向下筛选

42. for (int j = 2 * s; j <= m; j *= 2) {

43. // 保证j为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界

44. if (j < m && array[j] < array[j + 1]) {

45. j++;

46. }

47. if (!(array[0] < array[j])) {

48. break;

49. }

50. // 若S位较小，应将较大孩子上移

51. array[s] = array[j];

52. // 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选

53. s = j;

54. }

55. // 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。

56. array[s] = array[0];

内容来源：Android开发中文站

最新的TIOBE指数显示，Java编程已经超过了20%的普及门槛，这意味着每五行源代码当中就有一行采用Java编写。这不是Java语言有史以来最高分，它曾在多年前和C与C++语言竞争当中失去了头把交椅，但现在可能已经卷土重来。

排序算法详解（java代码实现）

排序算法大致分为内部排序和外部排序两种

内部排序：待排序的记录全部放到内存中进行排序，时间复杂度也就等于比较的次数

外部排序：数据量很大，内存无法容纳，需要对外存进行访问再排序，把若干段数据一次读入内存使用内部排序的方法进行排序后写入外存，再将这若干个已经排序的数据进行归并，时间复杂度等于IO(访问外存)的次数

交换排序。属于比较简单直观的排序算法，以升序为例（从小到大），每次比较相邻的两个元素，如果左侧元素比右侧的大，则交换两个元素的位置，每次把循环中最大的元素放在循环的最后，像冒泡一样从小到最大。

1. 比较 a[j] 和 a[j+1]，如果 a[j] > a[j+1]，swap交换两个元素在数组中的位置
2. 让每一对相邻元素进行以上的比较，直到把最大的值放到比较的数组最后
3. 重复以上步骤n-1次

​ 总共需要比较次数(n为数组元素个数 n >= 1)：

\\[O(n)=(n-1)+(n-2)+\\cdots+1=\\frac{(n-1)*n}{2}\\\\ 取最高次幂O(n)=n^2 \\]

​ 如图，即使第二次循环已经排好序，但是程序不晓得，仍会继续循环进行排序，最后一次，只有两个元素进行排序比较，直接排序完成，排序次数 n-1。

​ 交换排序。选择一个基准值，将数组划分两个区域，左侧的值全部比右侧的值小，然后分别对两个区域继续进行区域的划分与排序，直到排序完成。

1. 从数组中按照一定的规则选择一个元素作为基准值
2. 把基准值与其他元素进行比较，将元素分成两部分，把所有比基准值小的值放在左侧，所有比基准值大的放在右侧。即进行区域划分
3. 通过递归上述操作，再次将左右两区域进行区域划分，完成排序

​ 对区域划分取特殊值，假设n为2的幂，每次都将n个数平均划分，所以第一次对一整个区域进行循环n次划分2个区域，第二次对两个区域分别进行循环\\(\\frac{n}{2}\\)次，共n次，划分4个区域，第三次对4个区域分别进行循环\\(\\frac{n}{4}\\)次，共计n次，以此类推，最后一次为第log2n次，划分的每个区域仅有一个元素。即：

\\[O(n)=n*log_2n \\]

​ 插入排序。每一次把一个待排序的记录，按照值的大小，插入到有序数组的合适位置。

​ 相当于把a[n]分割，先排序数组 a[0] ~ a[1]，再 a[0] ~ a[2]，直到 a[0] ~ a[n] 全部排序完成。

1. 第一个元素之前没有值，认为已经排序
2. 取下一个待排序元素，下标为 i，向前进行比较
3. 如果待排序元素比待比较元素小，则交换位置
4. 重复步骤3直到有一个元素等于或者小于待排序元素，此次内循环结束，a[0] ~ a[i]排序完成
5. 重复步骤2~4，直到最后一个元素

​ 认为第一元素已经排好序，从第二个元素开始向前比较，计算需要比较的次数：

\\[O(n) = 1+2+3+\\cdots+n-1= \\frac{(n-1)*n}{2}\\\\ 即O(n) = n^2 \\]

​ 插入排序。因为设计该算法的人叫Shell，所以叫希尔排序，又称缩小增量排序。思路上是将待排序序列分割成若干个子序列进行直接插入排序，并逐渐缩减少子序列个数，直到针对整体进行一次排序。

1. 设置一个递减增量序列 $t_1,t_2,\\cdots,t_k$，\\(t_k\\)为1
2. 按照增量个数k，整体上对序列进行k次排序
3. 每次排序，根据增量 t，将序列分割成 (数组长度 / \\(t_i\\)) 个子序列，对子序列分别进行直接插入排序，当增量为1时，对序列整体进行一次排序

​ 希尔排序的时间复杂度和增量的选择有关，证明的话我是不会，最坏时间复杂度是\\(O(n^2)\\)，当n在某个范围内时，可以达到\\(O(n^{1.3})\\)

​ 选择排序。从未排序序列中查找一个最小值，然后将该值放到已排序序列的末尾位置，循环下去，直到最后一个元素。

1. 从 a[i] 开始，i=0,1,2,…,n，在数组中找到最小值的下标，放到arr[i]，此时 a[0] ~ a[i] 有序，a[i+1] ~ a[n] 待排序
2. 待排序序列重复步骤1
3. 经过n-1次循环完成排序

​ 循环次数为n-1，n-2，n-3，\\(\\cdots\\)，1

\\[O(n) = (n-1)+(n-2)+\\cdots+1\\\\ O(n) = \\frac{1}{2}(n^2-n)\\\\ O(n) = n^2 \\]

​ 选择排序。将待排序列构造诚大根堆，根节点则为序列中最大元素，将该节点与最后一个值交换，把剩余的节点重新构建大根堆，继续进行交换，直到待排序列只剩下一个值。

​ 大根堆（大顶堆）：父节点一定大于两个子节点的值，即：arr[i] > arr[2i+1] && arr[i] > arr[2i+2]

​ 将大根堆映射到数组中示例：

1. 将待排序数组构建成大根堆（仍然是无序的），根节点则为数组最大值
2. 将根节点和最后一个节点进行交换，则最大值放到了数组尾部，此时 a[0] ~ a[n-1] 无序
3. 因为步骤2进行了节点交换，需要对 a[0] ~ a[n-1] 重新构建大根堆
4. 重复步骤 2，3 直到全部有序

1. 初始化大根堆

​ 设元素个数为 n，建堆的高度 \\(k=log_2(n+1)\\)，

​ 第 i 层的非叶子节点的最大操作（交换）次数为 k-i

​ 第 i 层的节点个数为 \\(2^{i-1}\\)

​ 所以第 i 层总共需要操作 \\((k-i)(2^{i-1})\\) 次，总共需要操作的次数为

\\[S = (k-1)*2^0 + (k-2)*2^{1}+(k-3)*2^2+\\cdots+(k-(k-1))*2^{k-1-1} \\]

​ 用 2S – S计算 S 的值:

\\[S = 2^1+2^2+\\cdots+2^{k-1}-(k-1)\\\\ S = 2^k-k-1 \\]

​ 将 \\(k=log_2{(n+1)}\\approx log_2n\\) 代入得

\\[O(n) = n – log_2n-1 \\\\取最高项O(n) = n \\]

​ 则初始化大根堆的时间复杂度 O(n) = n

2.重新调整堆

​ 根节点和待排序数组的最后一个元素 a[i] 交换之后，需要重新调整堆，最大调整次数 = a[i] 所在堆的层数 = \\(log_2i\\)，总共需要调整的次数 = \\((n-1)(log_2n)\\) ，所以调整堆的时间复杂度为

\\[O(n) = nlog_2n \\]

总的时间复杂度 \\(O(n) = n + nlog_2n = nlog_2n\\)

初始化大根堆：

循环取堆顶元素排序：建议自己画二叉树更明晰

完整动图：

​ 将两个及以上的有序表合并成一个有序表。以下为两路合并排序。

​ 采用分治法，把无序数组两两分割，分割数次，然后自下至上将两个子序列进行排序，然后合并成一个有序数组，逐渐向上进行两两合并，直到合并成一个有序数组。

1. 将数组从中间拆分为两个无序数组
2. 通过递归继续执行步骤 1
3. 通过两个指针指向两个数组的起始位置
4. 比较指针指向的两个元素，把较小的放入合并数组，移动指针向后
5. 重复步骤4直到某一个指针到达数组尾部，此时另一个数组的元素全部不小于合并数组元素
6. 将另一个数组的元素放入合并数组
7. 继续归并，直到剩下一个数组

​ 时间复杂度 = 两个数组归并排序的时间复杂度 + 重建大根堆的时间复杂度

​ $f(n) = 2f(\\frac{n}{2})+ n $

​ \\(n = \\frac{n}{2}\\) : : \\(f(\\frac{n}{2}) = 2f(\\frac{n}{4}) + \\frac{n}{4}\\)

​ \\(n=\\frac{n}{4}\\) : : \\(f(\\frac{n}{4})=2f(\\frac{n}{8}) + \\frac{n}{8}\\)

​ \\(\\cdots\\)

​ \\(n=\\frac{n}{2^{m-1}}\\) : : \\(f(\\frac{n}{2^{m-1}}) = 2f(\\frac{n}{2^m}) + \\frac{n}{2^{m-1}}\\)

​ 即：\\(f(n) = 2f(\\frac{n}{2}) + n\\)

​ \\(=2[2f(\\frac{n}{4} + \\frac{n}{4}) + n]\\) = $ 22f(\\frac{n}{22}) + 2n$

​ \\(=2^2[f(2f(\\frac{n}{8}) + \\frac{n}{4})] + 2n\\) = \\(2^3f(\\frac{n}{2^3}) + 3n\\)

​ \\(\\cdots\\)

​ \\(=2^mf(\\frac{n}{2^m}) + mn\\)

​ 当数组被分割成仅剩一个元素时，此时分割为\\(2^mf(1)+mn\\) 即： \\(\\frac{n}{2^m} = 1\\)

​ 则：\\(m = log_2n\\)

​ 代入得\\(f(n) = 2^{log_2n}f(1) + n * log_2n = n + nlog_2n\\)

​ 所以归并排序的时间复杂度为：

\\[O(n) = nlog_2n \\]

注：两个图不是同一个算法过程

​ 取得最大整数的位数，从个位开始进行比较放入新的数组，再收集起来，此时数组按照个位有序排列，再进位进行比较收集，以此类推，直到最高位比较完成，此时数组全部有序。

1. 取得数组最大数的位数
2. 根据数组元素个位数的大小放入不同的数组中
3. 按照顺序将数组中的元素收集起来，此时新的数组按数组元素的个位数有序
4. 数组元素进位（十位、百位…）按照该位的大小重复2、3
5. 直到按照最大位数进行元素收集后所有元素有序

​ 设n个数的最大值是k位数，需要的桶（收集元素的数组）为r个，进行一次遍历元素收集的时间复杂度为O(n+r)，总的时间复杂度就是O(k(n+r))，一般来说，n >> r 且 n >> k，所以可以认为基数排序的时间复杂度为O(n)，也可以认为事件复杂度为O(kn)。

小伙伴们有兴趣想了解内容和更多相关学习资料的请点赞收藏+评论转发+关注我，后面会有很多干货。

我有一些面试题、架构、设计类资料可以说是程序员面试必备！所有资料都整理到网盘了，需要的话欢迎下载！私信我回复【07】即可免费获取

原文出处：www.shaoqun.com/a/1745545.html

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com