20231119 - 排序02

筒排序

• 若需排序的数据在一个可定范围内 (尽量别太大, 一般只能排序整数), 我们可以用 数组 index 和数量一一对应, 可将各元素放入对应 index 后按序输出各数值方可得到有序数列
• 缺点: 内存消耗异常大, 兼容性不佳
• 优点: 如果各数据差值大, 排序速度较 冒泡排序 会快很多
• 实现 (屎山)

  /*
    不支持负数
    要支持可以在比较前加上 abs(0-<min>) (min 为所给数据最小值, min <= 0)
  */
  #include <iostream>
  #include <climits>
  
  using namespace std;
  
  int get_max(int array[], int length) {
      int _max = INT_MIN;
      for (int i=0; i < length; i++) {
          if (array[i] > _max) {
              _max = array[i];
          }
      }
      
      return _max;
  }
  
  int main() {
      int n;
      cin >> n;
      int array[n];
      for (int i=0; i < n; i++) {
          cin >> array[i];
      }
      
      // 主要部分
      const int MAX_LENGTH = get_max(array, n);
      int barrels[MAX_LENGTH];
      // 全部初始化为 0
      for (int i=0; i < MAX_LENGTH; i++) {
          barrels[i] = 0;
      }
  
      for (int i=0; i < n; i++) {
          barrels[array[i]-1] = array[i];
      }
  
      // 输出
      for (int i=0; i < MAX_LENGTH; i++) {
          int item = barrels[i];
          if (item) {
              cout << item << ", ";
          }
      }
  }