关于golang:Go经典算法之-冒泡排序-选择排序-快速排序-归并排序

以下是几种经典的排序算法

// 抉择排序 O(n^2)
func selectSort(nums []int) []int {for i := 0; i < len(nums)-1; i++ {for j := i + 1; j < len(nums); j++ {if nums[i] > nums[j] {nums[i], nums[j] = nums[j], nums[i]
            }
        }
    }
    return nums
}

// 冒泡排序  O(n^2)
func buSort(nums []int) []int {for i := 0; i < len(nums)-1; i++ {for j := 0; j < len(nums)-1-i; j++ {if nums[j] > nums[j+1] {nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
    return nums
}

// 疾速排序 nlog2n
func quickSort(nums []int, begin int, end int) {
    if begin >= end {return}
    pivot := partition(nums, begin, end)
    quickSort(nums, begin, pivot-1)
    quickSort(nums, pivot+1, end)
}

func partition(nums []int, begin int, end int) int {
    var pivot = end
    var current = begin
    for i := begin; i < end; i++ {if nums[i] < nums[pivot] {nums[i], nums[current] = nums[current], nums[i]
            current++
        }
    }
    nums[current], nums[pivot] = nums[pivot], nums[current]
    return current
}


// 归并排序   nlog2n
func mergeSort(nums []int, begin int, end int) {
    if begin >= end {return}
    mid := (begin + end)>>1
    mergeSort(nums, begin, mid)
    mergeSort(nums, mid+1, end)
    merge(nums, begin, mid, end)
}

func merge(nums []int, begin int, mid int, end int) {var temp []int
    var i, j = begin, mid + 1

    for i <= mid && j <= end {if nums[i] >= nums[j] {temp = append(temp, nums[j])
            j++
        } else {temp = append(temp, nums[i])
            i++
        }
    }
    if i <= mid {temp = append(temp, nums[i:mid+1]...)
    }
    if j <= end {temp = append(temp, nums[j:end+1]...)
    }
    for i := 0; i < len(temp); i++ {nums[begin+i] = temp[i]
    }
}