Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to achieve counting and sorting in C++". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Counting and sorting

Counting sorting is a non-comparative sorting algorithm.

Advantages:

When sorting integers in a certain range, the time complexity of counting sorting is faster than any comparison sorting algorithm, because the theoretical upper and lower limit of sorting time complexity based on comparison is O (N*log (N)).

Disadvantages:

Counting sorting is a method of sacrificing space for time, and when K is large enough, O (K) > O (N*log (N)), it is not as efficient as the comparative sorting algorithm. And can only be used to sort unsigned shaping.

Time complexity:

O (K) when O (N) K is large enough.

Space complexity:

O (maximum-minimum)

Performance:

Counting sort is a stable sort.

Code implementation:

# include # include # include using namespace std; / / count sort, suitable for unsigned shaping void CountSort (int* a, size_t size) {assert (a); size_t max = a [0]; size_t min = a [0]; for (size_t I = 0; I)

Max) {max = a [I];} if (a [I] < min) {min = a [I];}} size_t range = max-min + 1; / / the array range to be opened size_t* count = new size_ t [range]; memset (count, 0, sizeof (size_t) * range) / / initialize to 0 / / count the number of occurrences of each number for (size_t I = 0; I < size; + + I) / / take the number from the original array, which is size {count [a [I]-min] + +;} / / write back to the original array size_t index = 0; for (size_t I = 0; I < range) + + I) / / read from the open array with the size of range {while (count [I] -) {a [index++] = I + min;}} delete [] count;} void Print (int* a, size_t size) {for (size_t I = 0; I < size; + + I) {cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.