Messy knowledge points

Sort

Sorting method	Time complexity （ Average ）	The complexity of the event （ The worst ）	The complexity of the event （ best )	Spatial complexity
Insertion sort	O(n^2)	O(n^2)	O(n)	O(1)
Shell Sort	O(2^1.3)	O(n^2)	O(n)	O(1)
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)
Heap sort	O(nlogN)	O(nlogN)	O(nlogN)	O(1)
Bubble sort	O(n^2)	O(n^2)	O(n)	O(1)
Quick sort	O(nlogN)	O(n^2)	O(nlogN)	O(nlogN)
Merge sort	O(nlogN)	O(nlogN)	O(nlogN)	O(n)
Radix sorting	O(n+k)	O(n+k)	O(n+k)	O(n+k)
Bucket sort	O(n+k)	O(n^2)	O(n)	O(N+K)
Radix sorting	O(n*k)	O(n*k)	O(n*k)	O(n*k)

Sort	stability
Insertion sort	Stable
Shell Sort	unstable
Selection sort	unstable
Heap sort	unstable
Bubble sort	Stable
Quick sort	unstable
Merge sort	Stable
Count sorting	Stable
Bucket sort	Stable
Radix sorting