Counting sorting and stability of sorting

What we said earlier is to sort by comparison , This time I'll talk about non comparative sorting . then , Summarize the sorting .

1. Count sorting

1.1 The basic idea

thought ： Counting sorting is also called pigeon nest principle , It is a variant application of hash direct addressing method . Operation steps ：
1. Count the number of occurrences of the same element
2. According to the statistical results, the sequence is recycled into the original sequence
Let's take an example ：

In this set of data , The largest number we can see is 10, So we define a subscript to 10 Array of , And assign all the contents in the array to 0.

then , We traverse the original array , How many times does a value appear , Its mapping position is ++ A few times .

This is what happens after mapping , Then we assign the original array from small to large .

This mapping is also called absolute mapping , But if the data is particularly large , Then absolute mapping will waste space . For example, the following set of data ：

If absolute mapping is used for this set of data, the previous 1000 There will be a waste of space . here , We need to use relative mapping . How to use relative mapping ？
We need to find the smallest and largest data , Then subtracting is the size of the mapping array .
From the above set of data , The biggest thing is 5000, The smallest is 1000, Subtraction is 4000, So we need to define 4001 Space .

here ,0 It stands for 1000,4000 It stands for 5000. here , Mapping according to relative position .1500 Namely 500,3700 Namely 2700,1800 Namely 800,2100 Namely 1100.

1.2 Concrete realization

That's the basic idea , We need to implement it ：

Here we need to focus on the two parts of counting and sorting , Implementation is not difficult .
here , We need to think about one more question ： How about negative numbers ？

Absolute mapping , We don't have to think about , Surely not , How about relative mapping ？
ad locum , The biggest thing is 2100, The smallest is -5000, Then we need to define 2100-(-5000)=7100.

ad locum ,1000 It stands for 6000,-1500 It stands for 3500,-3700 It stands for 1300,1800 It stands for 6800.
When counting 6000,3500,1300,6800 Location ++, When sorting returns the original array , Add... To these positions -5000, Is the original data , So negative numbers are OK . So let's verify that ：

Count sorting , We can see that it applies to the data in the scope set , It is also possible to have negative numbers in an array . But other types don't work , Like floating point 、 Strings and so on .

1.3 Complexity

First , There is nothing to say about spatial complexity , Is the extra space ：O(range)
Time complexity , Let's talk about ：
The first two cycles are both n, There is nothing to say , The main last cycle may be a problem ：

Inside while loop , When all the numbers have been subtracted , It's in the original array n, Outside for The number of times the loop is executed is range Time . The two cycles have nothing to do with each other , therefore , The total number of times the two loops are executed is n+range, At large O The time complexity in the progressive representation of is O(n+range)

2. stability

2.1 What is stability

You may think that stability refers to the fluctuation of performance , But it's not like that .

stability ： Assume in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , The relative order of these records remains the same , In the original sequence ,r[i]=r[j], And r[i] stay r[j] Before , In the sorted sequence ,r[i] Still in r[j] Before , We call this sort algorithm stable ; Otherwise it is called unstable .

for instance ：

For example, in an array , There are two identical numbers . Blue 10 In the red 10 front .

After sorting out , Blue 10 Still in red 10 front , That means it is stable , Otherwise, it will be unstable .

2.2 Which sort is stable

Which sort is stable , Let's analyze ：

Direct insert sort , According to our thoughts ： We insert the small one forward , Large and equal immobility . therefore , We can think of it as stable .

Shell Sort , It's unstable , Because the same data may be divided into different gap Group .

For example, this set of data , Blue 3 Will be indexed to 2 The location of , Red 3 Will be indexed to 1 The location of . The relative positions of the two are different , It's unstable .

Selection sort , It's unstable . Let's look at this set of data ：

We chose the smallest 1, And the leftmost 3 swapping .

You'll find two 3 The relative position has changed . So it's not stable .

Heap sort , It's unstable . We can see from the following data ：

Two 8 The relative position of has changed .

Bubble sort , It's stable . Because bubbling is a comparison between two , The big ones move back , Small and equal do not move .

Quick sort , It's unstable . because , Every election key When it is uncertain , It may select the first number in the middle .

Merge sort , It's stable . Let's take an example ：

From the example above , If we go blue first , It's stable .

Next, I will attach a sort complexity diagram ：