JS Sorting Algorithm

Top ten classic sorting algorithms

Sorting algorithm is one of the most basic algorithms in "Data Structures and Algorithms".

Sorting algorithms can be divided into internal sorting and external sorting. Internal sorting is to sort data records in memory, while external sorting is because the sorted data is very large and cannot accommodate all the sorted records at one time. During the sorting process, external memory needs to be accessed. Common internal sorting algorithms include: insertion sort, Hill sort, selection sort, bubble sort, merge sort, quick sort, heap sort, radix sort, etc. Summarize it with a picture:

Regarding time complexity :

1. Square order (O(n2)) sorting Various types of simple sorting: direct insertion, direct selection and bubble sort.
2. Linear logarithmic order (O(nlog2n)) sorting quick sort, heap sort and merge sort;
3. O(n1+§)) sorting, § is a constant between 0 and 1. Hill sort
4. Linear order (O(n)) sorting radix sorting, in addition to bucket and bin sorting.

Regarding stability :

Stable sorting algorithms: bubble sort, insertion sort, merge sort and radix sort.

Not stable sorting algorithms: selection sort, quick sort, Hill sort, heap sort.

Glossary :

n : data size

k : the number of "buckets"

In-place : occupies constant memory and does not occupy additional memory

Out-place : takes up additional memory

Stability : The order of two equal key values ​​after sorting is the same as their order before sorting.

---

GitBook content outline

1. bubble sort
2. selection sort
3. insertion sort
4. Hill sort
5. merge sort
6. Quick sort
7. Heap sort
8. counting sort
9. bucket sort
10. Radix sort

---

The content of this book comes almost entirely from the Internet.

Open source project address: https://github.com/hustcc/JS-Sorting-Algorithm, organized by hustcc.

GitBook online reading address: https://sort.hust.cc/.

This project uses lint-md to check the format of Chinese Markdown files. Be sure to ensure that the Markdown format is correct before submitting the PR.