Algorithmic classification (compare and non-compare)

Nonlinear time comparison sorting: The relative order of elements is determined by comparison. Since its time complexity cannot exceed O(nlogn), it is called nonlinear time comparison sorting

Linear time non-comparison sort: It does not determine the relative order between elements by comparison. It can break the lower time limit of comparison sort and run in linear time. Therefore, it is called linear time non-comparison sort

<img src=””></img>

Sort algorithm evaluation criteria

Time complexity

Time complexity is divided into: worst time complexity, average time complexity, best time complexity. The main measure is 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

Stable means that the relative relationship between elements with the same Key value in the sequence remains 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 are considered to be the same. However, for complex data types, where the data has the same key, the data may not be identical. For example, a Student class with two attributes, Name and Score, sorted by Score will make the relative relationship between elements with the same key value meaningful.

Summing up is the sorting of the same value of the data to maintain the same relative position in the original order

The sorting

All sorting operations are done in memory and are 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 sorting is done by data transfers between disk and memory

Summary of each sorting algorithm

<img src=””></img>

Noun interpretation:

N: Data size (that is, the length of the sequence)

K: Number of buckets

In-place: Constant memory, no extra memory

Out-place: Use extra memory

Resources: Ten classic sorting algorithms worth collecting


  • 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 in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】…
  • [3D city modeling using three. JS (Zhuhai City)]