08.计数排序

归并排序

• 1.基本思想
• 2.排序过程
• 3.代码实现
• 4.如何优化
• 5.复杂度
• 6.使用场景

1.基本思想

• 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

2.排序过程

• 
  image

3.代码实现

• 代码如下所示

  public int[] sort(int[] sourceArray) throws Exception {
      // 对 arr 进行拷贝，不改变参数内容
      int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  
      int maxValue = getMaxValue(arr);
  
      return countingSort(arr, maxValue);
  }
  
  private int[] countingSort(int[] arr, int maxValue) {
      int bucketLen = maxValue + 1;
      int[] bucket = new int[bucketLen];
  
      for (int value : arr) {
          bucket[value]++;
      }
  
      int sortedIndex = 0;
      for (int j = 0; j < bucketLen; j++) {
          while (bucket[j] > 0) {
              arr[sortedIndex++] = j;
              bucket[j]--;
          }
      }
      return arr;
  }
  
  private int getMaxValue(int[] arr) {
      int maxValue = arr[0];
      for (int value : arr) {
          if (maxValue < value) {
              maxValue = value;
          }
      }
      return maxValue;
  }

4.如何优化

• 可以直接看桶排序