Я написал простую программу, которая выполняет сортировку за O (n). Это очень неэффективно с памятью, но дело не в этом.
Он использует принцип, лежащий в основе HashMap
для сортировки:
public class NLogNBreak {
public static class LinkedListBack {
public LinkedListBack(int val){
first = new Node();
first.val = val;
}
public Node first = null;
public void insert(int i){
Node n = new Node();
n.val = i;
n.next = first;
first = n;
}
}
private static class Node {
public Node next = null;
public int val;
}
//max > in[i] > 0
public static LinkedListBack[] sorted(int[] in, int max){
LinkedListBack[] ar = new LinkedListBack[max + 1];
for (int i = 0; i < in.length; i++) {
int val = in[i];
if(ar[val] == null){
ar[val] = new LinkedListBack(val);
} else {
ar[val].insert(val);
}
}
return ar;
}
}
Это считается своего рода O (n), даже если оно возвращает результат в забавном формате?