preface
This is the fourth day of my participation in the August More text Challenge. For details, see: August More Text Challenge
The top ten sorts are: bubble sort, selection sort, insertion sort, Hill sort, merge sort, quicksort (quicksort), bucket sort, count sort, radix sort, and heap sort.
The top ten rankings fall into two broad categories:
- Comparison sorting: the relative order of elements is determined by comparison. Because its time complexity cannot break through O(nlogn), it is also called nonlinear time comparison sorting.
- Non-comparison sorting: It determines the relative order of elements without comparison. It can break the lower bound of comparison-based sorting and run in linear time. Therefore, it is also called linear time non-comparison sorting.
Time/space complexity
Common time/space complexities are:
- The O (1)
- O (n)
- O (n2n n2 ^ 2)
- O (nlogn)
- Order n log2log to the 2log2n.
- O (n + k)
- O (k)
The time complexity of the ten sorting algorithms is as follows:
| Sorting algorithm | Mean time complexity | Optimal time complexity | Worst time complexity | Spatial complexity | The stability of | Sort in place |
|---|---|---|---|---|---|---|
| Bubble sort | O ( ) |
O (n) | O ( ) |
The O (1) | stable | In situ |
| Selection sort | O ( ) |
O ( ) |
O ( ) |
The O (1) | unsteady | In situ |
| Insertion sort | O ( ) |
O (n) | O ( ) |
The O (1) | stable | In situ |
| Hill sorting | O (nlogn) | O (n N) |
O (n N) |
The O (1) | unstable | In situ |
| Merge sort | O (nlogn) | O (nlogn) | O (nlogn) | O (n) | stable | The in situ |
| Quick sort | O (nlogn) | O (nlogn) | O ( ) |
O (logn) | Stable/unstable | In situ |
| Bucket sort | O (n + k) | O (n + k) | O ( ) |
O (n + k) | stable | The in situ |
| Count sorting | O (n + k) | O (n + k) | O (n + k) | O (k) | stable | The in situ |
| Radix sort | O (n * k) | O (n * k) | O (n * k) | O (n + k) | stable | The in situ |
| Heap sort | O (nlogn) | O (nlogn) | O (nlogn) | The O (1) | unstable | In situ |
Sorting based
1. Time complexity, space complexity, and big O notation are not covered here
2. Linear time and nonlinear time: Linear time can be understood as a linear function with an exponent of 1, such as O(n); Nonlinear time can be understood as a nonlinear function with an exponent not one, such as O(n2).
3. Stable and unstable sorting:
- 3.1 Stable sorting: when a=b, a is before b, and a is still before B after sorting
- 3.2 Unstable sorting: when a=b, a is before B, and a may be after B after sorting
4. In-place sorting and non-in-place sorting: In-place sorting is to compare and exchange the original sorting data without applying for extra space. The reverse is true when sorting in place.