10万个整型数字排序

Question

一个整型数组，里面有10万个元素，不使用库函数，如何进行递增排序？
面试的时候遇到的这么一个问题，讲真，我当时答不上来。后面想了想，觉得可能是用指针实现的，不过，我还是想不清楚，特此请教各位大神解惑，谢谢

Answer 1

用占位法思想，首先创建一个10万的数组a[100000]，每个元素初始值置为0，然后再循环你这10万个数，每个数x，更新a数组的值a[x] + 1. 然后循环a数组，每个index就循环输出多少a[index]次。有个前提条件就是这10万个数最大不能大于100000.

public static void sortArray(Integer[] data) {
    // init result array
    Integer[] result = new Integer[100001];
    for(int i = 1; i <= 100000; i++) {
        result[i] = 0;
    }
        
    //get result data
    for(int i = 0; i < data.length; i++) {
        result[data[i]] += 1;
    }
        
    // print sort result
    for(int i = 1; i < result.length; i++) {
        for(int j = 0; j < result[i]; j++) {
            System.out.println(i);
        }
    }
        
}

Answer 2

数不多内存完全盛的下。鉴于都是整数，用基数排序吧，可自行百度。

Answer 3

链接描述