Go经典算法之 冒泡排序 选择排序 快速排序 归并排序
【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 + 1for 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]
}
}
推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 太平之莲
- 闲杂“细雨”
- 七年之痒之后
- 深入理解Go之generate
- 由浅入深理解AOP
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 生活随笔｜好天气下的意外之喜
- 感恩之旅第75天
- python学习之|python学习之 实现QQ自动发送消息