devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法的空间复杂度和时间复杂度

作者：菜鸟追梦旅行 | 2024-04-28 08:30:41

赞

踩

排序算法的空间复杂度和时间复杂度

基数排序算法：

一、排序算法的时间复杂度和空间复杂度

排序算法

平均时间复杂度

最坏时间复杂度

最好时间复杂度

平均空间复杂度

最差空间复杂度

稳定性

冒泡排序

 O(n²)

O(n)

O(1)

✅

直接选择排序

O(n²)

O(1)

❌

直接插入排序

O(n²)

O(n)

O(1)

✅

快速排序

O(nlogn)

O(n²)

同平均

O(logn)

O(n)❌

堆排序

O(nlogn)

O(1)

❌

归并排序

O(nlogn)

O(n)

✅

希尔排序

O(nlogn)

O(n²)同平均

O(1)

❌

计数排序

O(n+k)

O(n+k)

✅

基数排序

O(N*M) 

O(M)

✅

注：

1 归并排序可以通过手摇算法将空间复杂度降到O(1)，但是时间复杂度会提高。

2 基数排序时间复杂度为O(N*M)，其中N为数据个数，M为数据位数。

1.1 复杂度辅助记忆

  1. 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
  2. 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

1.2 稳定性辅助记忆

  • 稳定性记忆-“快希选堆”（快牺牲稳定性） 
  • 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

二、理解时间复杂度

2.1 常数阶O(1)

  1. int i = 1;
  2. int j = 2;
  3. ++i;
  4. j++;
  5. int m = i + j;

 2.2 对数阶O(logN)

  1. int i = 1;
  2. while(i<n)
  3. {
  4.     i = i * 2;
  5. }

2.3 线性阶O(n)

  1. for(i=0; i<=n; i++)
  2. {
  3.    System.out.println("hello");
  4. }

2.4 线性对数阶O(nlogN)

  1. for(m=1; m<n; m++)
  2. {
  3.     i = 1;
  4.     while(i<n)
  5.     {
  6.         i = i * 2;
  7.     }
  8. }

2.5 平方阶O(n^2)

  1.  
  2. for(x=1; i<=n; x++)
  3. {
  4.    for(i=1; i<=n; i++)
  5.     {
  6.        System.out.println("hello");
  7.     }
  8. }

2.6 K次方阶O(n^k)

  1.     for(i=0; i<=n; i++)
  2.         {
  3.             for(j=0; i<=n; i++)
  4.             {
  5.                 for(k=0; i<=n; i++)
  6.                 {
  7.                     System.out.println("hello");
  8.                 }
  9.             }
  10.         }
  11.  
  12.  
  13. // k = 3 , n ^ 3

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

三、空间复杂度

3.1 常数阶O(1) —— 原地排序

只用到 temp 这么一个辅助空间

原地排序算法，就是空间复杂度为O(1)的算法，不牵涉额外得到其他空间~

  1.     private static void swap(int[] nums, int i, int j) {
  2.         int temp = nums[i];
  3.         nums[i] = nums[j];
  4.         nums[j] = temp;
  5.     }

2.2 对数阶O(logN)

2.3 线性阶O(n)

  1.         int[] newArray = new int[nums.length];
  2.         for (int i = 0; i < nums.length; i++) {
  3.             newArray[i] = nums[i];
  4.         }

四、排序算法

4.1 冒泡排序

（思路：大的往后放）

4.1.1 代码

  1.     public static void bubbleSort(int[] arr) {
  2.         // 第一个 for 属于轮次，不参与对比
  3.         for (int i = 0; i < arr.length - 1; i++) {
  4.             // 第二个 for 进行元素逐个对比
  5.             for (int j = 0; j < arr.length - 1 - i; j++) {
  6.                 if (arr[j] > arr[j + 1]) {
  7.                     swap(arr, j, j + 1);
  8.                 }
  9.             }
  10.         }
  11.     }

4.1.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N^2  (因为就算你内部循环只对比，不交换元素，也是一样是N）

稳定性：稳定的 （大于的才换，小于等于的不交换）

  1.     // { 0,1,2,3,4}
  2.     private static void bubbleSort(int[] nums) {
  3.         for (int i = 0; i < nums.length; i++) {
  4.             boolean isChange = false;
  5.             for (int j = 0; j < nums.length - 1 - i; j++) {
  6.                 if (nums[j] > nums[j + 1]) {
  7.                     swap(nums, j, j + 1);
  8.                     isChange = true;
  9.                 }
  10.             }
  11.             if(!isChange){
  12.                 return;
  13.             }
  14.         }
  15.     }

改进后的代码，最佳时间复杂度： N  （因为假如第一轮对比就没有任何元素交换，那么可以直接退出，也就是只有一次外循环）

4.2 选择排序

（思路：最小的放最前）

4.2.1 代码

  1. private static void selectSort(int[] nums) {
  2.         for (int i = 0; i < nums.length; i++) {
  3.             int minIndex = i;
  4.             for (int j = i + 1; j < nums.length; j++) {
  5.                 if (nums[j] < nums[minIndex]) {
  6.                     minIndex = j;
  7.                 }
  8.             }
  9.             swap(nums,minIndex,i);
  10.         }
  11.     }

4.2.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N^2  

稳定性：不稳定的 

4.3 直接插入排序

（思路：往排序好的数组中，找到合适的位置插进去）


4.3.1 代码

找插入位置 + 移动，两步走

  1. public static void insertSort(int[] arr){
  2.         for (int i = 1; i < arr.length; i++) {
  3.             // 准备插入的元素
  4.             int insertNum = arr[i];
  5.             int insertIndex = i;
  6.             // 挨个对比，找到要插入的位置
  7.             for (int j = i - 1; j >= 0; j--) {
  8.                 if(insertNum >= arr[j]){
  9.                     break;
  10.                 }
  11.                 insertIndex = j;
  12.             }
  13.  
  14.             // 挨个往后移动 ，下面这个可以优化到上述for循环中
  15.             if(insertIndex != i){
  16.                 for (int j = i; j > insertIndex ; j--) {
  17.                     arr[j] = arr[j-1];
  18.                 }
  19.                 arr[insertIndex] = insertNum;
  20.             }
  21.         }
  22.     }

简洁版本~

  1. private static void insertSort(int[] nums) {
  2.         for (int i = 1; i < nums.length; i++) {
  3.             int temp = nums[i];
  4.             int j = i - 1;
  5.             for (; j >= 0 && temp < nums[j]; j--) {
  6.                 nums[j + 1] = nums[j];
  7.             }
  8.             nums[j + 1] = temp;
  9.         }
  10.     }

判断轮次思路版本~

  1.   private static void insertSort(int[] array) {
  2.         // length - 1 轮比较，每一轮都将下一个元素插入到已排序的序列中。
  3.         for (int i = 0; i < array.length - 1; i++) {
  4.             int j = i + 1;
  5.             int temp = array[j];
  6.             for (; j > 0 && temp < array[j - 1]; j--) {
  7.                 // 将大于 temp 的元素向右移动。
  8.                 array[j] = array[j - 1];
  9.             }
  10.             array[j] = temp;
  11.         }
  12.     }

4.3.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N  (因为你不进入内部循环。 [1,2,3,4,5]）

稳定性：稳定的 

4.4 快速排序

（思路：利用数字target，把数组切成两边，左边比 target大，后边比 target小）

4.4.1 代码

  1. /**
  2.  * 快速排序算法
  3.  * @param nums 待排序的数组
  4.  * @param beginIndex 排序起始索引
  5.  * @param endIndex 排序结束索引
  6.  */
  7. private static void quickSort(int[] nums, int beginIndex, int endIndex) {
  8.     if (beginIndex >= endIndex) {
  9.         return; // 递归终止条件：当开始索引大于等于结束索引时，表示已经完成排序
  10.     }
  11.     int mid = getMid(nums, beginIndex, endIndex); // 获取中间索引，用于分割数组
  12.     quickSort(nums, beginIndex, mid - 1); // 对中间索引左侧的数组进行快速排序
  13.     quickSort(nums, mid + 1, endIndex); // 对中间索引右侧的数组进行快速排序
  14. }
  15.  
  16. /**
  17.  * 获取分区中的中间元素的索引
  18.  * @param nums 待排序的数组
  19.  * @param beginIndex 分区的起始索引
  20.  * @param endIndex 分区的结束索引
  21.  * @return 中间元素的索引
  22.  */
  23. private static int getMid(int[] nums, int beginIndex, int endIndex) {
  24.     int target = nums[beginIndex]; // 以数组的起始元素作为基准值
  25.     int left = beginIndex;
  26.     int right = endIndex;
  27.     boolean right2left = true; // 标识位，表示当前从右往左搜索
  28.     while (right > left) {
  29.         if (right2left) {
  30.             while (right > left && nums[right] > target) {
  31.                 right--;
  32.             }
  33.             if (right > left) {
  34.                 nums[left] = nums[right]; // 当右侧元素较大时，将右侧元素移到插入位置
  35.                 right2left = false; // 切换为从左往右搜索
  36.             }
  37.         } else {
  38.             while (right > left && nums[left] < target) {
  39.                 left++;
  40.             }
  41.             if (right > left) {
  42.                 nums[right] = nums[left]; // 当左侧元素较小时，将左侧元素移到插入位置
  43.                 right2left = true; // 切换为从右往左搜索
  44.             }
  45.         }
  46.     }
  47.     nums[left] = target; // 将基准值放入插入位置，完成一轮交换
  48.     return left;
  49. }

4.4.2 复杂度

时间复杂度： N Log N （每个元素找到中间位置的，需要 LogN 时间，N个元素就是NLogN）

最差时间复杂度：N ^ 2  （ 比如正序数组 [1,2,3,4,5] ）

空间复杂度：Log N （递归调用，需要栈空间）

最差空间复杂度：N 

  1. 空间复杂度剖析：
  2.  
  3. 正常情况是： o(logN)
  4.             xxxxx
  5.              / \
  6.             /   \
  7.            /     \
  8.           /       \
  9.          xx        xx
  10.         / \        / \
  11.        /   \      /   \
  12.       /     \    /     \   
  13.      x      ()  x       ()
  14.  
  15. 最坏情况是：o(n)
  16.  
  17.               xxxxx
  18.                / \
  19.               /   \
  20.              /     \
  21.             /       \
  22.           xxxx      ()
  23.           / \ 
  24.          /   \
  25.         /     \
  26.       xxx     ()
  27.       / \ 
  28.      /   \ 
  29.     xx    ()
  30.    / \ 
  31.   /   \ 
  32.  x    ()

归树的深度是 logN，每层递归需要的时间是O(n)，所以总的时间复杂度是O(nlogn)。

然而，在极端情况（ 比如正序数组 [1,2,3,4] ）下，如果每次分区总是产生一个极度不平衡的划分，例如每次都将一个元素与其余元素分开，那么递归树将变得非常深。

为了避免极端情况，使得时间复杂度能一直是 N log(N) ， 可以随机化处理，也就是每次拿到数组排序之前，先把第一个元素和后续的随机一个元素交换。

  1. import java.util.Random;
  2.  
  3. private static void quickSort(int[] nums, int beginIndex, int endIndex) {
  4.     if (beginIndex >= endIndex) {
  5.         return;
  6.     }
  7.  
  8.     // 在排序前随机选择一个元素与起始元素交换
  9.     randomize(nums, beginIndex, endIndex);
  10.  
  11.     int mid = getMid(nums, beginIndex, endIndex);
  12.     quickSort(nums, beginIndex, mid - 1);
  13.     quickSort(nums, mid + 1, endIndex);
  14. }
  15.  
  16. // 随机化处理
  17. private static void randomize(int[] nums, int beginIndex, int endIndex) {
  18.     Random rand = new Random();
  19.     int randomIndex = beginIndex + rand.nextInt(endIndex - beginIndex + 1);
  20.     swap(nums, beginIndex, randomIndex);
  21. }
  22.  
  23. // 交换数组中的两个元素
  24. private static void swap(int[] nums, int i, int j) {
  25.     int temp = nums[i];
  26.     nums[i] = nums[j];
  27.     nums[j] = temp;
  28. }

稳定性：不稳定的 

4.4.3 相关面试题

1、奇偶分割

给你一个数组，奇数放左边，偶数放右边，不要求排序

  1. public static void main(String[] args) {
  2.         // 题目，把奇数放左边，偶尔放右边
  3.         // 思路：快速排序，交换元素
  4.         int[] array = {13, 100, 17, 12, 25, 0,1,6};
  5.         quickSort(array, 0, array.length - 1);
  6.         System.out.println(JSON.toJSONString(array));
  7.  
  8.     }
  9.  
  10.     private static void quickSort(int[] array, int beginIndex, int endIndex) {
  11.         if (beginIndex >= endIndex) {
  12.             return;
  13.         }
  14.         int mid = getMid(array, beginIndex, endIndex);
  15.     }
  16.  
  17.     private static int getMid(int[] array, int beginIndex, int endIndex) {
  18.         int left = beginIndex;
  19.         int right = endIndex;
  20.         int temp = array[beginIndex];
  21.  
  22.         boolean right2Left = true;
  23.         while (left < right) {
  24.             if (right2Left) {
  25.                 // 如果是偶数
  26.                 if (array[right] % 2 == 0) {
  27.                     right--;
  28.                 } else {
  29.                     array[left++] = array[right];
  30.                     right2Left = false;
  31.                 }
  32.             } else {
  33.                 // 如果是奇数
  34.                 if (array[left] % 2 != 0) {
  35.                     left++;
  36.                 } else {
  37.                     array[right--] = array[left];
  38.                     right2Left = true;
  39.                 }
  40.             }
  41.         }
  42.         array[left] = temp;
  43.         return left;
  44.     }

这个方法的时间复杂度是O(N），空间复杂度是 O(1），不稳定

下面这个方法的时间复杂度是O(N），空间复杂度是 O(N），稳定

  1. public static void main(String[] args) {
  2.         // 题目，把奇数放左边，偶尔放右边
  3.         // 思路：找到偶数的个数，然后奇数从0开始，偶数从oddCount开始放置元素（需要多一个int数组的辅助空间，所以空间复杂度是 n
  4.         int[] array = {13, 100, 17, 12, 25, 0, 1, 6, 5, 5};
  5.  
  6.         int[] arrayNew = new int[array.length];
  7.  
  8.         int oddCount = 0;
  9.         for (int i = 0; i < array.length; i++) {
  10.             if (array[i] % 2 != 0) {
  11.                 oddCount++;
  12.             }
  13.         }
  14.         System.out.println(oddCount);
  15.         // 奇数的下标
  16.         int oddIndex = 0;
  17.         // 偶数的下标
  18.         int evenIndex = oddCount;
  19.         for (int i = 0; i < array.length; i++) {
  20.             if (array[i] % 2 != 0) {
  21.                 arrayNew[oddIndex++] = array[i];
  22.             }else {
  23.                 arrayNew[evenIndex++] = array[i];
  24.             }
  25.  
  26.         }
  27.         System.out.println(JSON.toJSONString(arrayNew));
  28.     }

4.5 堆排序

（思路：最大放上面，然后与最后元素交换，继续建堆）

4.5.1 代码

  1. /**
  2.  * 堆排序算法
  3.  * @param nums 待排序的数组
  4.  * @param beginIndex 排序的起始索引
  5.  * @param endIndex 排序的结束索引
  6.  */
  7. private static void heapSort(int[] nums, int beginIndex, int endIndex) {
  8.     if (beginIndex >= endIndex) {
  9.         return; // 当开始索引大于等于结束索引时，排序完成
  10.     }
  11.     for (int i = endIndex; i >= beginIndex; i--) {
  12.         createHeap(nums, i); // 构建最大堆
  13.         swap(nums, 0, i); // 将最大元素移到数组末尾
  14.     }
  15. }
  16.  
  17. /**
  18.  * 构建最大堆
  19.  * @param nums 待构建的数组
  20.  * @param endIndex 当前堆的结束索引
  21.  */
  22. private static void createHeap(int[] nums, int endIndex) {
  23.     int lastFatherIndex = (endIndex - 1) / 2;
  24.     for (int i = lastFatherIndex; i >= 0; i--) {
  25.         int biggestIndex = i;
  26.         int leftChildIndex = i * 2 + 1;
  27.         int rightChildIndex = i * 2 + 2;
  28.  
  29.         // left孩子节点存在，并且左孩子的value比较大
  30.         if (leftChildIndex <= endIndex && nums[biggestIndex] < nums[leftChildIndex]) {
  31.             biggestIndex = leftChildIndex;
  32.         }
  33.         // right孩子节点存在，并且right孩子的value比较大
  34.         if (rightChildIndex <= endIndex && nums[biggestIndex] < nums[rightChildIndex]) {
  35.             biggestIndex = rightChildIndex;
  36.         }
  37.         swap(nums, biggestIndex, i); // 调整堆，确保最大元素位于堆顶
  38.     }
  39. }
  40.  
  41. /**
  42.  * 交换数组中两个元素的位置
  43.  * @param nums 数组
  44.  * @param i 索引1
  45.  * @param j 索引2
  46.  */
  47. private static void swap(int[] nums, int i, int j) {
  48.     int temp = nums[i];
  49.     nums[i] = nums[j];
  50.     nums[j] = temp;
  51. }

4.5.2 复杂度

时间复杂度： N Log N （每个元素都要构建1次堆，需要 LogN 时间，N个元素就是NLogN，任何情况下都一样）

空间复杂度：1 （原地排序）

最差时间复杂度：N ^ 2  （ 比如正序数组 [1,2,3,4,5] ）

稳定性：不稳定的 

4.6 归并排序

递归思路，左右两边排序好了，就已经排序好了

4.6.1 代码

  1. // 归并排序的主方法
  2. private static void mergeSort(int[] nums, int beginIndex, int endIndex) {
  3.     // 如果起始索引大于等于结束索引，表示只有一个元素或没有元素，不需要排序
  4.     if (beginIndex >= endIndex) {
  5.         return;
  6.     }
  7.     
  8.     // 计算数组的中间索引
  9.     int mid = beginIndex + (endIndex - beginIndex) / 2;
  10.     
  11.     // 递归排序左半部分
  12.     mergeSort(nums, beginIndex, mid);
  13.     
  14.     // 递归排序右半部分
  15.     mergeSort(nums, mid + 1, endIndex);
  16.     
  17.     // 合并左右两部分
  18.     merge(nums, beginIndex, mid, endIndex);
  19. }
  20.  
  21. // 合并函数，用于将左右两部分合并成一个有序的数组
  22. private static void merge(int[] nums, int beginIndex, int mid, int endIndex) {
  23.     int left = beginIndex;
  24.     int right = mid + 1;
  25.     int[] newArrays = new int[endIndex - beginIndex + 1];
  26.     int newArraysIndex = 0;
  27.  
  28.     // 比较左右两部分的元素，将较小的元素放入新数组
  29.     while (left <= mid && right <= endIndex) {
  30.         newArrays[newArraysIndex++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
  31.     }
  32.  
  33.     // 将剩余的左半部分元素复制到新数组
  34.     while (left <= mid) {
  35.         newArrays[newArraysIndex++] = nums[left++];
  36.     }
  37.  
  38.     // 将剩余的右半部分元素复制到新数组
  39.     while (right <= endIndex) {
  40.         newArrays[newArraysIndex++] = nums[right++];
  41.     }
  42.  
  43.     // 将合并后的新数组复制回原数组
  44.     for (int i = 0; i < newArrays.length; i++) {
  45.         nums[beginIndex + i] = newArrays[i];
  46.     }
  47. }

4.6.2 复杂度

时间复杂度： N Log N （每个元素都要递归，需要 LogN 时间，N个元素就是NLogN，任何情况下都一样）

空间复杂度：N

稳定性：稳定的 

 4.7 希尔排序

思路：直接插入排序的升级版（分段式插入排序）

4.7.1 代码

  1. private static void quickSort(int[] nums) {
  2. //        int gap = nums.length / 2;
  3. //        while (gap > 0) {
  4.         for (int i = 1; i < nums.length; i++) {
  5.             int temp = nums[i];
  6.             int j;
  7.             for (j = i - 1; j >= 0 && temp < nums[j]; j--) {
  8.                 nums[j + 1] = nums[j];
  9.             }
  10.             nums[j + 1] = temp;
  11.         }
  12. //        gap = gap / 2;
  13. //        }
  14.     }
  15.  
  16.     // 把上面的快速排序改成shell排序，只需要把间隔1 改成gap
  17.     private static void shellSort(int[] nums) {
  18.         int gap = nums.length / 2;
  19.         while (gap > 0) {
  20.             for (int i = gap; i < nums.length; i++) {
  21.                 int temp = nums[i];
  22.                 int j;
  23.                 for (j = i - gap; j >= 0 && temp < nums[j]; j = j - gap) {
  24.                     nums[j + gap] = nums[j];// 如果当前元素比待插入元素大，将当前元素向后移动
  25.                 }
  26.                 nums[j + gap] = temp; // 因为上边 j=j-gap退出的时候，j已经被剪掉1次了，可能小于0了
  27.             }
  28.             gap = gap / 2;
  29.         }
  30.     }

4.7.2 复杂度

时间复杂度： N Log N 

空间复杂度：1

稳定性：不稳定的 

 4.8 计数排序

前提：

1、数组规模不大，比如统计中国各个年龄的人数（因为年龄顶多就是0-150岁）

4.8.2 代码

  1. public static void main(String[] args) {
  2.     int[] nums = {10, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 2, 8, 3, 4, 1, 2, 3, 4};
  3.     int[] ageCount = new int[200];
  4.     for (int i = 0; i < nums.length; i++) {
  5.         ageCount[nums[i]]++;
  6.     }
  7.     for (int i = 1; i < ageCount.length; i++) {
  8.         int count = ageCount[i];
  9.         for (int j = 0; j < count; j++) {
  10.             System.out.print(i + ",");
  11.         }
  12.     }
  13. }

4.8.2 复杂度

时间复杂度： N  （N是数组长度）

空间复杂度：K

稳定性：稳定的 

 4.9 基数排序

4.9.1 代码

如何取到指定位置的数字？

  1.     public static void main(String[] args) {
  2.         int number = 1234;
  3.         // 1234 如何取到个位数 4，1234 % 10 = 4 ，4/1 = 4
  4.         // 1234 如何取到十位数 3，1234 % 100 = 34 ，34/10 = 3
  5.         // 1234 如何取到百位数 2，1234 % 1000 = 234 ，234/100 = 2
  6.         // 1234 如何取到千位数 1，1234 % 10000 = 1234 ，234/1000 = 1
  7.         for (int i = 0; i < getDigitLength(number); i++) {
  8.             int num = (int) (number % Math.pow(10, i + 1) / Math.pow(10, i));
  9.             System.out.println(num);
  10.         }
  11.     }
  12.  
  13.     // 1 就是1位数
  14.     // 10 就是2位数
  15.     // 100 就是3位数
  16.     // 1000 就是4位数
  17.     public static int getDigitLength(int number) {
  18.         int length = 1;
  19.         while (number / 10 > 0) { // 100
  20.             length++;
  21.             number = number / 10;
  22.         }
  23.         return length;
  24.     }

基数排序算法：

  1. public static void main(String[] args) {
  2.  
  3.         int[] array = {13, 100, 17, 12, 25};
  4.         Map<Integer, List<Integer>> bucketMap = new HashMap<>();
  5.         for (int i = 0; i < 10; i++) {
  6.             bucketMap.put(i, new ArrayList<>());
  7.         }
  8.  
  9.         int maxDigitLength = 0;
  10.         for (int i = 0; i < array.length; i++) {
  11.             maxDigitLength = getDigitLength(array[i]) > maxDigitLength ? getDigitLength(array[i]) : maxDigitLength;
  12.         }
  13.         for (int i = 0; i < maxDigitLength; i++) { // 从后往前取数值
  14.             for (int j = 0; j < array.length; j++) {
  15.                 int iValue = (int) (array[j] % Math.pow(10, i + 1) / Math.pow(10, i));
  16.                 bucketMap.get(iValue).add(array[j]); // 入桶
  17.             }
  18.  
  19.             int arrayIndex = 0;
  20.             for (int j = 0; j < 10; j++) {
  21.                 List<Integer> bucketList = bucketMap.get(j);
  22.                 for (Integer num: bucketList) {
  23.                     array[arrayIndex++] = num; //倒出来
  24.                 }
  25.                 map.get(j).clear(); // 清空桶
  26.             }
  27.             System.out.println(JSON.toJSONString(array));
  28.  
  29.         }
  30.     }
  31.  
  32.  
  33.     // 1 就是1位数
  34.     // 10 就是2位数
  35.     // 100 就是3位数
  36.     // 1000 就是4位数
  37.     public static int getDigitLength(int number) {
  38.         int length = 1;
  39.         while (number / 10 > 0) { // 100
  40.             length++;
  41.             number = number / 10;
  42.         }
  43.         return length;
  44.     }

基数排序算法：（又抽空手写了一遍）

  1.  public static void radixSort(int[] array) {
  2.         if (array == null || array.length < 2) {
  3.             return; // 检查数组是否不需要排序
  4.         }
  5.  
  6.         int maxDigitLength = 0;
  7.         // 计算最大位数
  8.         for (int i = 0; i < array.length; i++) {
  9.             maxDigitLength = Math.max(maxDigitLength, getDigitLength(array[i]));
  10.         }
  11.  
  12.         List<List<Integer>> bucketList = Lists.newArrayList();
  13.         for (int i = 0; i < 10; i++) {
  14.             bucketList.add(Lists.newArrayList());
  15.         }
  16.         // 按每位数进行分配和收集
  17.         // 比如最大的数字是1234，那么最长是4位，也就是倒入倒出4次即可
  18.         for (int i = 0; i < maxDigitLength; i++) {
  19.             // 分配元素到桶
  20.             for (int j = 0; j < array.length; j++) {
  21.                 // 根据指定下标，给出对应数字
  22.                 int bucketIndex = getBucketIndex(array[j], i);
  23.                 bucketList.get(bucketIndex).add(array[j]);
  24.             }
  25.             System.out.println("i -> " + i + ",\n after sort" + JSON.toJSONString(bucketList));
  26.             // 倒出来
  27.             int newIndex = 0;
  28.             for (List<Integer> bucketInnerNumberList: bucketList) {
  29.                 for (Integer number: bucketInnerNumberList) {
  30.                     array[newIndex++] = number;
  31.                 }
  32.                 // 清空数组
  33.                 bucketInnerNumberList.clear();
  34.             }
  35.         }
  36.     }
  37.  
  38.     /**
  39.      * 根据指定下标，给出对应数字
  40.      * @param number     1234
  41.      * @param digitIndex 0 return 4,1 return 3,2 return 2, 3 return 1
  42.      */
  43.     private static int getBucketIndex(int number, int digitIndex) {
  44.         // 1234
  45.         // 0 return 4
  46.         // 1 return 3
  47.         // 2 return 2
  48.         // 3 return 1
  49.         int result = 0;
  50.         for (int i = 0; i <= digitIndex; i++) {
  51.             result = number % 10;
  52.             number = number / 10;
  53.         }
  54.         return result;
  55.     }
  56.  
  57.     /**
  58.      * 获取数字位数
  59.      */
  60.     public static int getDigitLength(int number) {
  61.         // 1234 -> 4
  62.         // 123 -> 3
  63.         // 12 -> 2
  64.         // 1 -> 1
  65.         int result = 1;
  66.         while (number / 10 != 0) {
  67.             result++;
  68.             number /= 10;
  69.         }
  70.         return result;
  71.     }

4.9.2 复杂度

时间复杂度： N * d  （N是数组长度，d是最大位数，对于整数排序的话，d = log N 级别，因此整体是 N Log N）

空间复杂度：N

稳定性：稳定的 

4.9.3 使用场景

基数排序是一种非比较型整数排序算法，其工作原理是按照低位先排序，然后收集；再按照高位排序，然后再收集；以此类推，直到最高位。有时也可以采用相反的顺序，即按照高位先排序。它是这样的一种排序算法，对于每一位使用稳定的排序算法来排序，常见的是使用计数排序或桶排序。

基数排序的使用场景包括：

  1. 大量数据：当数据量大，并且数据的范围并不是很大时，基数排序是非常有效的。

  2. 固定长度的数据：基数排序对固定长度的数据排序非常高效，比如电话号码、身份证号码等。

  3. 整数和字符串排序：基数排序适用于整数排序，也可以用于字符串或其他数据类型，只要这些数据类型可以被分解成有序的元素片段，例如通过ASCII值。

  4. 稳定排序需求：由于基数排序是稳定的，所以当需要保持相同元素的原始顺序时，基数排序非常有用。

相比于计数排序，基数排序的区别主要在于：

  1. 处理的数据类型：计数排序只能用于整数排序，且适用于较小范围的整数。基数排序可以用于任何可以分解成位的数据类型，包括整数和字符串。

  2. 效率：对于小范围的整数，计数排序可能比基数排序更有效率，因为它只需要一次遍历数据即可完成排序。但是对于大范围或多位数的数据，基数排序通常更优，因为它可以在线性时间内处理更大范围的数值。

  3. 内存使用：计数排序在处理大范围数值时可能会消耗大量内存，因为它需要一个足够大的计数数组来存储每个数值的出现次数。基数排序则通过逐位处理数据来避免这个问题。

  4. 稳定性：虽然计数排序本身是稳定的，但基数排序必须使用稳定的排序算法作为子过程来保证整体排序的稳定性。

总的来说，基数排序是一种快速且稳定的排序方法，适用于大量数据和多位数的数据排序。然而，它对内存的需求相对较高，并且比较复杂，因此通常在特定条件下使用时最为高效。

假如使用基数排序处理大量手机号码，那么时间复杂度是多少？

基数排序的时间复杂度通常表示为 O(kN)，其中 N 是排序元素的个数（在这个例子中是手机号码的个数），k 是元素的统计特性，通常取决于这些元素的最大位数。

对于手机号码，假设我们考虑的是一个国家的标准手机号码长度，通常这个长度是固定的。例如，如果我们考虑一个国家，它的手机号码是10位数的，那么我们可以认为 k 是常数，即 k = 10。

在这种情况下，由于 k 是一个固定的值，基数排序处理这些手机号码的时间复杂度可以简化为 O(N)。也就是说，它可以在线性时间内完成排序。这是基于假设内部使用的稳定排序算法（比如计数排序）也是线性的。

然而，实际的时间复杂度还受到其他因素的影响，比如使用的稳定排序算法的复杂度、手机号码的分布情况、以及在实际操作中对桶（或计数数组）的处理效率等。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/501329
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号