Basic concept and classification of sorting

What is sequencing

Sorting is a problem we often face in our life . When students do exercises, they will be arranged from low to high ; When the teacher checks the attendance in class , Students will be called in the order of student numbers ; When admitted to the college entrance examination , Will be admitted in descending order according to the total score . What is the strict definition of sorting ?

Sort ： Arrange a set of disordered data in order according to a certain law . namely , Arrange the unordered sequence into an ordered sequence ( From small to large or from large to small ) Arithmetic .
If the data node participating in sorting contains multiple data fields , Then the sorting is often for one of the domains .

Classification of sorting methods

By data storage medium

By data storage medium , It can be divided into internal sort and external sort （ File sorting ）.

• Internal sorting ： The amount of data to be sorted is small , The data is in memory , There is no need to exchange data between internal and external memory .
• External sorting ： A large amount of data needs to be sorted , Data in external storage .

When sorting externally , You need to transfer data into memory in batches to sort , Intermediate results should be put into external storage in time . Obviously, external sorting is much more complicated than internal sorting .

Inner sorting is in the whole process of sorting , All records to be sorted are placed in memory . External sorting is due to too many records , You can't put it in memory at the same time , The whole sorting process needs to exchange data between internal and external storage for many times .

According to the number of comparators

According to the comparison number , It can be divided into serial sort and parallel sort .

• Serial sort ： Single processor （ Compare a pair of elements at the same time ）.
• Parallel sorting ： Multiprocessor （ More pairs of elements at the same time ）.

According to the main operation

According to the main operation , It can be divided into comparison sort and cardinality sort .

• Compare sort ： By comparison , Such as insertion sort 、 Selection sort 、 Merge, sort, etc .
• Radix sorting ： Do not compare element sizes , The ordered position of an element is determined only by its value .

Press auxiliary space

Press auxiliary space , It can be divided into in place sorting and non in place sorting .

• In situ sorting ： Auxiliary space usage bit O(1) Sorting method of , That is, the auxiliary space occupied has nothing to do with the amount of data participating in sorting .
• Not in place ： The amount of auxiliary space exceeds O(1) Sorting method of .

In addition to the time performance of the sorting algorithm , Another major criterion for evaluating sorting algorithms is the auxiliary storage space needed to execute the algorithms . The auxiliary storage space is in addition to the storage space occupied by the storage to be sorted , Other storage space needed to execute the algorithm .

According to the stability

According to the stability , It can be divided into stable sort and unstable sort .

• Stable sequencing ： An element that can make any number equal , After sorting, the relative order remains unchanged .
• Unstable ordering ： Not a stable sort .

Throughout the sorting process , If there is a jumping exchange of data , The sorting algorithm is unstable ; without , Then the sorting algorithm is stable .
For example, in direct insertion sorting , Exchanging data will only exchange between adjacent elements , So it's stable .
In simple selection sorting , The exchange of elements is no longer possible between adjacent elements , So it's not stable .

The stability of sorting is only meaningful to the sorting of structure type data . for example ：
n Student information （ Student number , full name , Chinese language and literature , mathematics , English , Total score ）.

1. Sort by math scores from high to low
2. Sort by total score from high to low
3. With the same total score , Those with high math scores are in the front

The stability of sorting method cannot measure the advantages and disadvantages of a sorting algorithm

By nature

By nature , It can be divided into natural sorting and unnatural sorting .

• Natural ordering ： The more ordered the sorted data is , The faster the sorting, the faster the sorting method .
• Unnatural sorting ： It's not a natural way to sort .