| 排序算法 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) |
O(n^2) |
O(n) |
O(1) |
内部排序 | 稳定 |
| 选择排序 | O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
内部排序 | 不稳定 |
| 插入排序 | O(n^2) |
O(n^2) |
O(n) |
O(1) |
内部排序 | 稳定 |
| 希尔排序 | O(nlog²n) |
O(nlogn) |
O(n^2) |
O(1) |
内部排序 | 不稳定 |
| 归并排序 | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
外部排序 | 稳定 |
| 快速排序 | O(nlogn) |
O(nlogn) |
O(n^2) |
O(logn) |
内部排序 | 不稳定 |
| 堆排序 | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
内部排序 | 不稳定 |
| 计数排序 | O(n+k) |
O(n+k) |
O(n+k) |
O(k) |
外部排序 | 稳定 |
| 桶排序 | O(n+k) |
O(n+k) |
O(n^2) |
O(n+k) |
外部排序 | 稳定 |
| 基数排序 | O(n*k) |
O(n*k) |
O(n*k) |
O(n+k) |
外部排序 | 稳定 |
nums都是切片传递
冒泡
func sort(nums []int) {
for i := 0; i < len(nums) - 1; i++ {
for j := 0; j < n-1-i; j++ {
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1],nums[j]
}
}
}
}
选择
func sort(nums []int) {
for i := 0; i < n; i ++ {
minIndex := i
for j = i+1; j < n; j++ {
if nums[j] < nums[minIndex] {
minIndex = j
}
}
if minIndex != i {
nums[i], nums[minIndex] = nums[minIndex], nums[i]
}
}
}
与冒泡排序相比,选择排序每次找到后面最小的 与当前位置交换
插入排序
func sort(nums []int) {
n := len(nums)
for i:=1; i < n; i++ {
key := nums[i]
j := i-1
for j >= 0 && nums[j] > key {
nums[j+1] = nums[j]
j--
}
nums[j+1] = nums[j]
}
}
希尔排序
func sort(nums []int) {
n := len(nums)
gap := n/2
for gap > 0 {
for i := gap;i < n; i++ {
key := nums[i]
j := i
for j >= gap && nums[j-gap] > key {
nums[j] = nums[j-gap]
j-=gap
}
nums[j] = key
}
gap /= 2
}
}
插入排序的改进版
举个例子
[1,2,5,4,3,5,6,7,5,3,1]
11个元素 gap初始值为5
1, 5, 1
2, 6
5, 7
4, 5
3, 3
之后gap更新为2
1, 5, 3, 6, 5, 5
2, 4, 1, 7, 3
最后更新为1的时候排序完成 一句话总结的话,就是分组的插入排序
归并排序
func merge(left, right []int) []int {
res := []int{}
i, j := 0,0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
res = append(res, left[i])
i++
}else {
res = append(res, right[i])
j++
}
}
res =append(res, left[i:]...)
res = append(res, right[j:]...)
return res
}
func mergeSort(arr []int) []int {
if len(arr) <= 1{
return arr
}
mid = len(arr)/2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
return merge(left, right)
}
分治法
快速排序
func partition (arr []int, low, high int) int {
mid := low + (high - low) / 2
pivotC := []int{arr[low], arr[mid], arr[high]}
sort.Ints(pivotC)
pivot := pivotC[1]
if pivot == arr[low] {
arr[low], arr[high] = arr[high],arr[low]
}else if pivot == arr[mid] {
arr[mid], arr[high] = arr[high], arr[mid]
}
//把枢纽移动到末尾
i := low - 1
for j := low; j < high; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
}
func quickSort(arr []int, low, high int) {
if low < high {
pi := partition(arr, low, high)
quickSort(arr, low, pi -1)
quickSort(arr, pi+ 1 , high)
}
}
堆排序
func heapSort(arr []int) {
n := len(arr)
for i := n/2-1; i >= 0; i-- {
heapify(arr, n, i)
}
for i :=n-1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
func heapify(arr []int, n, i int) {
largest := i
left := 2*i +1
right := 2*i +2
if left < n && arr[left] > arr[largest] {
largest = left
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr,n, largest)
}
}
计数排序
func sort (arr []int) {
maxVal := 0
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
count := make([]int, maxVal+1)
for _, num := range arr {
count[num]++
}
idx := 0
for i := 0; i <= maxVal; i++ {
for count[i] > 0 {
arr[idx] = i
idx++
count[i]--
}
}
}
桶排序
func sort(arr []int) {
if len(arr) == 0 {
return
}
minVal, maxVal := arr[0], arr[0]
for _, num := range arr {
if num < minVal {
minVal = num
}
if num > maxVal {
maxVal = num
}
}
if maxVal == minVal {
return
}
//找到最大值和最小值
bucketCount := int(math.Sqrt(float64(len(arr))))
buckets := make([][]int, bucketCount)
for _, num := range arr {
// 计算每个元素应该放在哪个桶
ratio := float64(num-minVal) / float64(maxVal-minVal)
index := int(ratio * float64(bucketCount))
if index == bucketCount {
index--
}
buckets[index] = append(buckets[index], num)
}
index := 0
for i := 0; i < bucketCount; i++ {
// 对每个桶内部进行排序
sort.Ints(buckets[i])
for _, num := range buckets[i] {
arr[index] = num
index++
}
}
}
基数排序
func radixSort(arr []int) {
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
exp := 1
for maxVal/exp > 0 {
countingSort(arr, exp)
exp *= 10
}
}
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
digit := (arr[i]/exp)%10
count[digit]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n-1; i >= 0; i-- {
digit := (arr[i]/exp)%10
output[count[digit]-1] = arr[i]
count[digit]--
}
copy(arr,output)
}