вопрос о подсчете сортировки

Question

привет, я написал следующий код, который печатает элементы в отсортированном порядке, только одна большая проблема заключается в том, что он использует два дополнительных массива вот мой код

public  class occurance{
public static   final  int n=5;


public static void main(String[]args){
// n  is  maximum possible  value  what it should be in array suppose n=5 then array may be

int  a[]=new int[]{3,4,4,2,1,3,5};// as   u see all elements are less or equal to n
//create array a.length*n

int b[]=new int[a.length*n];
int c[]=new int[b.length];
 for (int i=0;i<b.length;i++){
  b[i]=0;
  c[i]=0;
}

  for (int i=0;i<a.length;i++){

   if (b[a[i]]==1){
  c[a[i]]=1;
}
 else{
 b[a[i]]=1;
}
}
 for (int i=0;i<b.length;i++){
   if (b[i]==1) {
   System.out.println(i);
}
  if (c[i]==1){
  System.out.println(i);
}
}





}
}
//
1
2
3
3
4
4
5   
1.i have two question what is complexity of this  algorithm?i  mean running time
2. how put this elements into other array  with sorted order? thanks

Answer 1

Алгоритм, как указано выше, работает в O (n), где n - размер массива a.

Однако я даже сомневаюсь, что он работает правильно.

Итак, вот псевдокод-реализация подсчета сортировки. Он принимает массив a целых чисел и сохраняет отсортированные значения в массиве целых чисел b. a и b должны быть одинаковой длины.

void countingSort(int[] a, int[] b){
 // first of all: count occurences
 int[] occ = new int[a.length];
 for (int i = 0; i<a.length; ++i){
  occ[i]=0;
 }
 for (int i = 0; i<a.length; ++i){
  occ[a[i]] = occ[a[i]] + 1;
 }
 // second: put the elements in order into b
 int s = 0;
 for (int i = 0; i<a.length; ++i){
  // how often did element i occur?
  for (int j = 0; j<occ[i]; ++j){
   b[s] = i;
   s = s + 1;
  }
 }
}

Надеюсь, я не сделал ничего страшного.