比较排序（英语：Comparison sort）是排序算法的一种，通过一个抽象的内容比较操作（通常是“小于或等于”操作）来确定两个元素中哪个应该放在序列前面。 –wiki
冒泡排序
func (b *BubbleSort) Sort(input []int) []int {
l := len(input)
for i := l - 1; i > 0; i-- {
for j := 0; j < i; j++ {
if input[j] > input[j+1] {
input[j], input[j+1] = input[j+1], input[j]
}
}
}
return input
}
选择排序
func (i SelectSort) Sort(input []int) []int {
l := len(input)
for i := l - 1; i > 0; i-- {
maxIndex := i
for j := 0; j < i; j++ {
if input[j] > input[maxIndex] {
maxIndex = j
}
}
input[maxIndex], input[i] = input[i], input[maxIndex]
}
return input
}
插入排序
func (i InsertSort) Sort(input []int) []int {
l := len(input)
for i := 1; i < l; i++ {
j := i - 1
// 取出即将插入的值
key := input[i]
// 从有序的最后一个开始，如果>key则将其赋值给后一个位置(值本身已经被缓存)
for j >= 0 && input[j] > key {
input[j+1] = input[j]
j--
}
input[j+1] = key
}
return input
}
快速排序
使用二分的思想可以将时间复杂度降低到nlogn
type QuickSort struct{}
func (s QuickSort) Sort(nums []int) []int {
if len(nums) < 2 {
return nums
}
mid := s.partition(nums, len(nums)/2)
s.Sort(nums[:mid])
s.Sort(nums[mid+1:])
return nums
}
func (s QuickSort) partition(nums []int, pivot int) int {
n := len(nums)
pivotValue := nums[pivot]
nums[pivot], nums[n-1] = nums[n-1], nums[pivot]
storeIndex := 0
for i := 0; i < n; i++ {
if nums[i] < pivotValue {
nums[i], nums[storeIndex] = nums[storeIndex], nums[i]
storeIndex++
}
}
nums[n-1], nums[storeIndex] = nums[storeIndex], nums[n-1]
return storeIndex
}
归并排序
归并的缺点是需要使用额外的空间，优点是每一路的归并可以并发完成，而且不需要将所有数据都加载到内存中
func (s MergeSort) subSort(input []int, reg []int) {
l := len(input)
if l <= 1 {
return
}
mid := l / 2
//对左右两部分进行归并排序
s.subSort(input[:mid], reg[:mid])
s.subSort(input[mid:], reg[mid:])
i, j, k := 0, mid, 0
// 如果有一路已经处理完，则退出循环
for i < mid && j < l {
//将较小的值放到临时数组中
if input[i] < input[j] {
reg[k] = input[i]
k++
i++
} else {
reg[k] = input[j]
k++
j++
}
}
//将未归并完的一路直接连接到数组之后
for i < mid {
reg[k] = input[i]
i++
k++
}
for j < l {
reg[k] = input[j]
j++
k++
}
//将临时数组的值拷贝
copy(input, reg)
}
希尔排序
shellsort是对插入排序的优化，原理在于
- 插入排序在排序几乎有序的数据时，效率高
- 普通插入排序，每一个数据在一次操作中只能移动一步到最终位置
func (i ShellSort) Sort(input []int) []int {
l := len(input)
for gap := l / 2; gap > 0; gap /= 2 {
for j := gap; j < l; j++ {
tmp := input[j]
k := j - gap
for ; k >= 0 && input[k] > tmp; k -= gap {
input[k+gap] = input[k]
}
input[k+gap] = tmp
}
}
return input
}
堆排序
type HeapSort struct{}
// O(nlogn) 不稳定
func (s HeapSort) Sort(input []int) []int {
//建堆(最大堆)
s.createHeap(input)
for i := len(input) - 1; i > 0; i-- {
//将堆顶数据(最大值)移动到最终位置，并用堆最后一个元素填补
input[0], input[i] = input[i], input[0]
//调整堆
s.shiftDown(input[:i], 0)
}
return input
}
// 建堆操作
func (s HeapSort) createHeap(input []int) {
l := len(input)
for i := l/2 - 1; i >= 0; i-- {
s.shiftDown(input, i)
}
}
// 使得堆重新有序
func (s HeapSort) shiftDown(heap []int, index int) {
l := len(heap)
// father
f := index
// child
c := index*2 + 1
for c < l {
//如果右儿子存在，且大于左儿子
if c+1 < l && heap[c+1] > heap[c] {
c++
}
//如果孩子比父亲大，当前值下移
if heap[f] < heap[c] {
heap[f], heap[c] = heap[c], heap[f]
f = c
c = c*2 + 1
} else {
return
}
}
// 可以实现一个不交换的版本
// 可以理解为，为一个元素寻找一个正确的位置(空穴)，算法模拟了空穴下移的过程
}
并发快排
type ConcurrentQSort struct{}
func (s ConcurrentQSort) Sort(nums []int) []int {
n := len(nums)
if n < 2 {
return nums
}
mid := s.partition(nums, n/2)
// 如果待排序数组比较小，则直接使用快排，防止使用过多的go routine
// 在生成、调度、销毁上花费大量时间
if n < 512 {
s.Sort(nums[:mid])
s.Sort(nums[mid+1:])
} else {
// 使用WaitGroup，等待子协程处理结束
wg := sync.WaitGroup{}
wg.Add(2)
go func() {
s.Sort(nums[:mid])
wg.Done()
}()
go func() {
s.Sort(nums[mid+1:])
wg.Done()
}()
wg.Wait()
}
return nums
}
func (s ConcurrentQSort) partition(nums []int, pivot int) int {
// 同快排
}
完整的测试代码在github