Упражнения на Java: алгоритм CountingSort

Алгоритм сортировки Java: упражнение 12 с решением

Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма CountingSort.

Согласно Википедии "В компьютерных науках сортировка подсчета - это алгоритм сортировки коллекции объектов по ключам, которые являются маленькими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количества объектов, у которых есть каждый отдельный ключ значение и использование арифметики по этим подсчетам для определения позиций каждого значения ключа в выходной последовательности. Время его выполнения линейно по количеству элементов и разности между максимальным и минимальным значениями ключа, поэтому оно подходит только для непосредственного использования в ситуациях, когда изменение в ключах не намного больше, чем количество элементов. Однако оно часто используется в качестве подпрограммы в другом алгоритме сортировки, основанном на сортировке, который может обрабатывать большие ключи более эффективно ».

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

Пример решения:

Java-код:

import java.util.Arrays;
class countingSort {
    void countingSort(int[] nums, int min, int max){
	  int[] ctr = new int[max - min + 1];
	  for(int number : nums){
		ctr[number - min]++;
    	}
	  int z= 0;
	  for(int i= min;i <= max;i++){
		 while(ctr[i - min] > 0){
		 	nums[z]= i;
		 	z++;
			ctr[i - min]--;
		   }
	   }
  }
  
    // Method to test above
    public static void main(String args[])
    {
        countingSort ob = new countingSort();
        int nums[] = {7, -5, 3, 2, 1, 0, 45};
        int minValue = -5, maxValue = 45;
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(nums));
        ob.countingSort(nums,minValue,maxValue);
        System.out.println("Sorted Array");
        System.out.println(Arrays.toString(nums));
    }
}

Пример вывода:

 Оригинальный массив:
[7, -5, 3, 2, 1, 0, 45]
Сортированный массив
[-5, 0, 1, 2, 3, 7, 45] 

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущая: Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма CombSort.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел, используя алгоритм сортировки Gnome.