“Liczenie Sort Java” Kod odpowiedzi

Liczenie Sort Java

import java.util.Arrays;

public class CountingSort {
	/*
	 * This code performs a Counting sort of
	 * a list of positive integer values.
	 * 
	 * Let n be size of the list to be sorted and
	 * m be the maximum value in the list
	 * 
	 * Time complexity: O(n)
	 * Space complexity: O(n+m)
	 * 
	 */
	public static void main(String[] args) {
		int[] arr = { 2, 4, 3, 1 };

		System.out.println(Arrays.toString(arr)); // [2, 4, 3, 1]
		int[] sortedArr = countingSort(arr);
		System.out.println(Arrays.toString(sortedArr)); // [1, 2, 3, 4]
	}
	private static int[] countingSort(int[] arr) {
		/*
		 * The counting sort method counts the number
		 * of occurrences of every element in arr.
		 * Then uses that information to sort these elements.
		 */
		int max = findMax(arr);
		if (max == Integer.MIN_VALUE) {
			return new int[] {};
		}
		int[] counts = new int[max + 1];
		for (int num : arr) {
			counts[num]++;
		}
		for (int idx = 1; idx < counts.length; idx++) {
			counts[idx] = counts[idx - 1] + counts[idx];
		}
		int[] sortedArray = new int[arr.length];
		int current, sortedIdx;
		for (int idx = arr.length - 1; idx >= 0; idx--) {
			current = arr[idx];
			counts[current]--;
			sortedIdx = counts[current];
			sortedArray[sortedIdx] = current;
		}
		return sortedArray;
	}
	private static int findMax(int[] arr) {
		int max = Integer.MIN_VALUE;
		for (int num : arr) {
			if (num > max) {
				max = num;
			}
		}
		return max;
		// or return Collections.max(Arrays.asList(arr));
	}
}
Wissam

Liczenie Sort Java

public static void CountingSort(int A[], int k) {//k is equal to A.length
        int[] B = new int[k + 1];
        int max = A[0];
        for (int i = 1; i < k; i++) {
            if (A[i] > max)
                max = A[i];
        }
        int[] C = new int[max + 1];
        for (int i = 0; i < max; ++i) {
            C[i] = 0;
        }
        for (int i = 0; i < k; i++) {
            C[A[i]]++;
        }
        for (int i = 1; i <= max; i++) {
            C[i] += C[i - 1];
        }
        for (int i = k - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]]--;
        }
        for (int i = 0; i < k; i++) {
            A[i] = B[i];
        }
    }
znarfbay

Odpowiedzi podobne do “Liczenie Sort Java”

Pytania podobne do “Liczenie Sort Java”

Więcej pokrewnych odpowiedzi na “Liczenie Sort Java” w Java

Przeglądaj popularne odpowiedzi na kod według języka

Przeglądaj inne języki kodu