Sorting & Searching

Sorting algorithm is an algorithm that arranges a specific set of data in a certain order. There are many kinds of sorting algorithms, and their properties are mostly different.

Stability refers to whether the relative order of equal elements changes after sorting.

An algorithm with the characteristic of stability will maintain the relative order of records that originally have equal key values. That is, if a sorting algorithm is stable, when there are two records R and S with equal key values, and in the original list R appears before S, R will also appear before S in the sorted list.

Radix sort, counting sort, insertion sort, bubble sort, and merge sort are stable sorts.

Selection sort, heap sort, quick sort, and Hill sort are not stable sorts.

Search is to enumerate the state space and find the optimal solution by exhausting all possibilities, or counting the number of legal solutions.

There are many ways to optimize search, such as reducing the state space, changing the search order, pruning, etc.

Search is the basis for some advanced algorithms. In OI, pure search is often a way to get partial points, but there are very few questions that can get full marks through pure search.