Bucket Сортировка или сортировка арраиста объектов на основе Id?

Question

Я слышал о Bucket Sorting. Может ли кто-нибудь объяснить, как он дает лучшую производительность при сортировке миллионов записей? Есть ли какой-либо алгоритм с n*log(n) или O(n) ?

У меня есть 1000 объектов-сотрудников каждый объект-сотрудник имеет идентификатор, имя, свойства зарплаты. Я добавил эти объекты в ArrayList Я хочу, чтобы sort эти объекты на основе свойства id. Там в любом случае? Без использования метода Collections.sort(). Рассматриваемые ниже решения, пожалуйста, кто-нибудь поможет, который дает лучшую производительность?

Благодаря

Answer 1

Без коллекций.сортировать():

Сначала реализовать Comparable<Employee> в классе Empoloyee и переопределить compareTo

@Override 
public int compareTo(Employee o) { 

    return this.id.compareTo(o.id); 
} 

Пройди свой несортированный список TreeSet и получить set (отсортированы по идентификатору), а затем создать new List с этим set

List<Employee> list=new ArrayList<Employee>(); 
    list.add(new Employee(1, "A", Double.parseDouble("50"))); 
    list.add(new Employee(22, "B", Double.parseDouble("11"))); 
    list.add(new Employee(3, "C", Double.parseDouble("222"))); 
    list.add(new Employee(34, "D", Double.parseDouble("4"))); 

    SortedSet<Employee> set=new TreeSet<Employee>(list); 

    List<Employee> l=new ArrayList<Employee>(); 
    l.addAll(set); 

    System.out.println(l); 

OutPut: Отсортировано по ID без Collections.sort()

[Employee [id=1, name=A, price=50.0], Employee [id=3, name=C, price=222.0], Employee [id=22, name=B, price=11.0], Employee [id=34, name=D, price=4.0]] 

Edit:

класс Employee:

class Employee implements Comparable<Employee>{ 

Integer id; 
String name; 
Double price; 
     ------- 

} 

Answer 2

My requirement is not to use Collections.sort() method 

В этом случае вам необходимо использовать некоторый существующий способ сортировки. Если коллекция статична (добавлено больше элементов), я могу порекомендовать использовать либо сортировку, либо сортировку слиянием. Если будут добавлены элементы, возможно, наилучшим способом будет выборка из heapsorting или двоичной сортировки.

Answer 3

Вы можете использовать этот код для сортировки списка:

Collections.sort(list, new Comparator() { 
    public int compare(Object a, Object b) { 
     Employee ea = (Employee) a; 
     Employee eb = (Employee) b; 
     return ea.getID() - eb.getID(); 
    } 
} 

Это использует Collections.sort для сортировки списка с настраиваемым компаратора, который сравнивает идентификаторы.

Если вы не можете использовать Collections.sort, то, конечно же, ваш учитель рассказал вам, как сортировать список? Возможно, он заплатит, чтобы обратить внимание на лекции.

Answer 4

public class Employee implements Comparable<Employee> { 

private int id; 
private String name; 
private String salary ; 

public int compareTo(Employee val) { 
     if(id>val.id){ 
     return 1; 
    }else if(id<val.id){ 
     return -1; 
    } else { 
     return 0; 
    } 
} 

//getter and setters here 
} 

и теперь вы можете создать список

List<Employee> emp= new ArrayList<Employee>(); 

Теперь вы можете использовать

Collections.sort(emp); 

сортировать по идентификатору

Answer 5

The ArrayList может хранить элемент в ArrayFormat. Если вы идентифицируете сотрудника-пользователя по id, вы можете использовать класс HashTable, который использует пару ключей и значений, в противном случае вы можете реализовать свой класс, используя интерфейс Comparable.

public class Employee implements Comparable<Employee> { 

    private String id; 
    private String name; 
    private int salary ; 

    public int compareTo(Employee val) { 
     return id.compareTo(val.id); 
    } 

    // getter and setters here... 

    List<Employee> emp = new ArrayList<Employee>(); 
    Collections.sort(emp); 

Answer 6

сначала преобразовать его в список вашего класса:

List<Employee> list = new List<Employee>(arraylist); 

var sorted = list.OrderBy(o => o.id).ToList();