Question

期末考试完了，老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学，这5个同学分别考了5分、3分、5分、2分和8分，哎考得真是惨不忍睹（满分是10 分）。接下来将分数进行从大到小排序，排序后是8 5 5 3 2。

输入输出

[Input Example]

  1. 10
  2. 5
  3. 5 3 5 2 8
  5. 1000
  6. 10
  7. 8 100 50 22 15 6 1 1000 999 0

[Output Example]

  1. 8 5 5 3 2 
  2. 1000 999 100 50 22 15 8 6 1 0

解析

image.png
image.png

solution

  1. import java.util.Scanner;
  3. public class Bucket_Sort {
  4.     static int N, M;
  5.     static int[] book;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         N = sc.nextInt();
  10.         M = sc.nextInt();
  11.         book = new int[N+1];
  13.         for(int i=0; i<M; i++){
  14.             book[sc.nextInt()]++;
  15.         }
  16.         sc.close();
  18.         for(int i=N; i>=0; i--) {
  19.             for(int j=0; j<book[i]; j++) {
  20.                 System.out.print(i + " ");
  21.             }
  22.         }
  23.     }
  24. }
  1. #include <stdio.h>
  3. int main() {
  4.     int book[1001] = {0};
  5.     int N, index;
  6.     scanf("%d");    //丢弃掉java用于初始化数组长度的参数
  7.     scanf("%d", &N);
  8.     for(int i=0; i<N; i++) {
  9.         scanf("%d", &index);
  10.         book[index]++;
  11.     }
  12.     for(int i=1000; i>=0; i--) {
  13.         for(int j=0; j<book[i]; j++) {
  14.             printf("%d ", i);
  15.         }
  16.     }
  18.     getchar();getchar();
  19.     return 0;
  20. }

时空复杂度

N为数据的个数，M为桶的个数即数据的范围
桶排序的时间复杂度为O(N+M)

问题

现在分别有5 个人的名字和分数：huhu 5 分、haha 3 分、xixi 5 分、hengheng 2 分和gaoshou 8 分。请按照分数从高到低，输出他们的名字。即应该输出gaoshou、huhu、xixi、haha、hengheng。如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输出的也仅仅是分数，但没有对人本身进行排序。也就是说，我们现在并不知道排序后的分数原本对应着哪一个人