Algorithmic classification (compare and non-compare)

Nonlinear time comparison sorting: the relative order of elements is determined by comparison. Because its time complexity cannot break through O(nlogn), it is called nonlinear time comparison sorting

Linear time noncomparison sorting: It does not determine the relative order of elements by comparison. It can break the time lower bound of comparison-based sorting and run in linear time, so it is called linear time noncomparison sorting

Evaluation criteria for sorting algorithms

Time complexity

Time complexity is divided into worst time complexity, average time complexity, and best time complexity. It mainly reflects the number of times the program was executed

Spatial complexity

A measure of the amount of storage space temporarily occupied by an algorithm while it is running

The stability of

Stability means that for elements in a sequence with the same Key value, their relative relationships remain the same before and after sorting. For a basic data type like int, stability is basically meaningless because its key is the element itself, and two elements with the same key can be considered the same. But for complex data types where the data has the same key, the data may not be the same, such as a Student class that has two attributes, Name and Score, sorted by Score, where the relative relationship between elements with the same key makes sense. Summary is to keep the relative position of the same value of data unchanged in the original order after sorting

The sorting

All sorting is done in memory, which is suitable for cases where the data size is not particularly large

External sort

Because the data is too large, the data is placed on disk, and the sort can be done through the data transfer between disk and memory

Summary of sorting algorithms

Noun explanation:

N: Data size (i.e., the length of the sequence)

K: Indicates the number of buckets

In-place: Occupies constant memory but does not occupy extra memory

Out-of-place: Occupies extra memory

Resources: Top 10 classic sorting algorithms worth collecting

additional

  • This article is published through multiple platforms of “we media” and will not be maintained after publication. If you have any objection to the content, you can discuss it on GitHub below

  • Continuous maintenance/update 500+ github.com/noxussj/Int…

  • 3D city modeling using three.js (Zhuhai