The basic idea

Counting sort is a non-comparison based sorting algorithm, is a space for time algorithm, is to determine the location of the element by the value of the element, suitable for sorting non-negative integers

Algorithm description

  • Find the element with the largest value in the array and call it Max
  • Create a new array count, Max plus 1, whose elements default to 0
  • Iterate over the elements in the original array, using the elements in the original array as the index of the count array, and the number of occurrences of the elements in the original array as the value of the elements in the count array.
  • Create the result array result, starting index index
  • Each time, the value of the element in count is reduced by 1 until the value of the element is not greater than 0. The remaining elements in count are processed in turn
  • Returns the result array result

demo

Code implementation

public static void sort(int[] array) { int temp = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > temp) { temp = array[i]; } } int[] tempArray = new int[temp + 1]; for (int i = 0; i < array.length; i++) { tempArray[array[i]]++; } int tempIndex = 0; for (int i = 0; i < tempArray.length; i++) { for (int j = 1; j <= tempArray[i]; j++) { array[tempIndex++] = i; }}}Copy the code

Time complexity

K represents the number of digits in the number Best case: O(n+k) Worst case: O(n+k) Average case: O(n+k)

Spatial complexity

Assuming that each keyword in n records is between 0 and K-1, then the space complexity is n+O(k).

Advantages and Disadvantages

  • Advantages: simple implementation, faster than any comparison sort
  • Disadvantages: limited scope (non-negative integers), useful for sorting integers of a small order of magnitude, which may cause stack overflows

Test records

To be added

The source code

Insertion sort is not currently used in open source frameworks or the JDK