# 1.冒泡排序(Bubble Sort)

1 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置 ✓ 执行完一轮后，最末尾那个元素就是最大的元素
2 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序

``````for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}
``````

## 冒泡排序 – 优化1

``````for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}

}
``````

## 冒泡排序 – 优化2

``````//最坏、平均时间复杂度:O(n2)  最好时间复杂度:O(n)
//空间复杂度:O(1)
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}
``````

#### golang 源码

``````package mysort

import (
"fmt"
"time"
)

type Sort struct {
Array     []int
CmpCount  int64
SwapCount int64
begin     int64
FuncType     string

}

func (this *Sort) SortArray(array []int)  {

this.Array = make([]int, len(array))
copy(this.Array, array)
this.begin = time.Now().UnixNano()

}
func (this *Sort) SortFunc() {
if this.Array == nil || len(this.Array) < 2 {
return
}
}
func (this *Sort) ComWithIndex(i1, i2 int) int {
this.CmpCount++
return this.Array[i1] - this.Array[i2]
}
func (this *Sort) ComWithValue(v1, v2 int) int {
this.CmpCount++
return v1 - v2
}
func (this *Sort) Swap(i1, i2 int) {
this.Array[i2], this.Array[i1] = this.Array[i1], this.Array[i2]
this.SwapCount++
}
func (this *Sort)ToString()  {
fmt.Println("排序数组大小", len(this.Array),"排序方法",this.FuncType,"比较次数",this.CmpCount,"交换次数",this.SwapCount,"耗时",(time.Now().UnixNano() - this.begin)/1e6,"ms")

}

``````
``````package mysort

type BubbleSort struct {
Sort
}

func (this *BubbleSort) SortArray(array []int) {
this.Sort.SortArray(array)
}
func (this *BubbleSort) SortFunc()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}

}
// 设置一个bool 的标志，判断是否进行过交换
func (this *BubbleSort) SortFunc1()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}

}

}
func (this *BubbleSort) SortFunc2()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}

}
``````
``````package main

import (
"fmt"
"iktolin.com/mysort"
"iktolin.com/struct/firstStudy/Heap"
"math/rand"
"sync"
"time"
)

func main() {

algorithm()

}
// 算法
func algorithm() {
wg := sync.WaitGroup{}
var array []int
rand.Seed(time.Now().UnixNano())
for i := 0; i < 100000; i++ {
x := rand.Intn(10209023)
array = append(array, x)

}

//fmt.Println("排序前",array)
//// 时间复杂度 O(n2)
go func(array []int, w *sync.WaitGroup) {
bubbleSort := mysort.BubbleSort{}
bubbleSort.SortArray(array)
bubbleSort.SortFunc()
bubbleSort.ToString()
w.Done()
}(array, &wg)

//fmt.Println(array)
// 使用bool 值判断是否进行过排序，适用于原来就是排好序的
go func(array []int, w *sync.WaitGroup) {
bubbleSort1 := mysort.BubbleSort{}
bubbleSort1.SortArray(array)
bubbleSort1.SortFunc1()
bubbleSort1.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
bubbleSort2 := mysort.BubbleSort{}
bubbleSort2.SortArray(array)
bubbleSort2.SortFunc2()
bubbleSort2.ToString()
w.Done()
}(array, &wg)
// 使用bool 值判断是否进行过排序，适用于其中有局部排好序的

go func(array []int, w *sync.WaitGroup) {
slect := mysort.SelectionSort{}
slect.SortArray(array)
slect.SortFunc()
slect.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
heap := mysort.HeapSort{}
heap.SortArray(array)
heap.SortFunc()
heap.ToString()
w.Done()
}(array, &wg)
go func(array []int, w *sync.WaitGroup) {
insertion := mysort.InsertionSort{}
insertion.SortArray(array)
insertion.SortFunc()
insertion.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
merge := mysort.MergeSort{}
merge.SortArray(array)
merge.SortFunc()
merge.ToString()
w.Done()
}(array, &wg)

wg.Wait()
//排序数组大小 100000 排序方法 归并排序 比较次数 1536231 交换次数 0 耗时 18 ms
//排序数组大小 100000 排序方法 堆排序 比较次数 1509851 交换次数 99999 耗时 21 ms
//排序数组大小 100000 排序方法 插入排序 比较次数 0 交换次数 0 耗时 4613 ms
//排序数组大小 100000 排序方法 选择排序 比较次数 4999950000 交换次数 99999 耗时 13306 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999418601 交换次数 2506933128 耗时 22555 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999950000 交换次数 2506933128 耗时 23048 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999880994 交换次数 2506933128 耗时 24453 ms

}

``````

# 2.选择排序（Selection Sort）

1. 从序列中找出最大的那个元素，然后与最末尾的元素交换位置 执行完一轮后，最末尾的那个元素就是最大的元素

2. 忽略 1 中曾经找到的最大元素，重复执行步骤 1

``````for end := len(this.Array) - 1; end > 0; end-- {
max := 0
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
max = begin
}
}
this.Swap(max, end)
}
``````

//选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
//最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于不稳定排序

### src

``````package mysort

type SelectionSort struct {
Sort
}

//1 从序列中找出最大的那个元素，然后与最末尾的元素交换位置 执行完一轮后，最末尾的那个元素就是最大的元素
//2 忽略 1 中曾经找到的最大元素，重复执行步骤 1

//选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
//最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于不稳定排序
func (this *SelectionSort) SortFunc() {
this.Sort.SortFunc()

for end := len(this.Array) - 1; end > 0; end-- {
max := 0
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
max = begin
}
}
this.Swap(max, end)
}

}
``````
``````package main

import (
"fmt"
"iktolin.com/mysort"
"math/rand"
"time"
)

func main()  {
var array []int
rand.Seed(time.Now().UnixNano())
for i := 0; i < 40; i++ {
x := rand.Intn(100)
array = append(array, x)

}

fmt.Println("排序前",array)
// 时间复杂度 O(n2)
bubbleSort := mysort.BubbleSort{}
bubbleSort.SortArray(array)
bubbleSort.SortFunc()
bubbleSort.ToString()
//fmt.Println(array)
// 使用bool 值判断是否进行过排序，适用于原来就是排好序的
bubbleSort1 := mysort.BubbleSort{}
bubbleSort1.SortArray(array)
bubbleSort1.SortFunc1()
bubbleSort1.ToString()
// 使用bool 值判断是否进行过排序，适用于其中有局部排好序的
bubbleSort2 := mysort.BubbleSort{}
bubbleSort2.SortArray(array)
bubbleSort2.SortFunc2()
bubbleSort2.ToString()

slect :=mysort.SelectionSort{}
slect.SortArray(array)
slect.SortFunc()
slect.ToString()
}
//排序前 [68 23 47 62 33 4 97 49 46 20 25 24 77 88 66 16 6 44 98 11 70 68 30 5 29 46 12 96 31 27 60 24 76 21 19 44 94 46 82 77]
//排序比较次数 780 排序交换次数 369
//排序比较次数 725 排序交换次数 369
//排序比较次数 643 排序交换次数 369
//排序比较次数 780 排序交换次数 39
``````

# 3.选择排序的优化方案（堆排序）

``````package mysort

type HeapSort struct {
Sort
size int
}

// 对数据进行原地建堆
//将建立好的堆的root最后的位置交换位置，然后将size -- 然后将0号位置进行下滤操作
//siftdown 直到堆的值为1
// 选最值使用堆来操作
// 第一个叶子节点是size 的一半 所以第一个非叶子节点 是 (size >> 1) -1
func (this *HeapSort) SortFunc() {
this.size = len(this.Array)
for i := (this.size >> 1) - 1; i >= 0; i-- {
this.siftDown(i)
}
for this.size > 1 {
this.Swap(0, this.size-1)
this.size--
this.siftDown(0)
}

}
func (this *HeapSort) siftDown(index int) {
v := this.Array[index]
half := (this.size >> 1)
// 1.找其左右子节点 找到最大的子节点开始交换数值
for index < half {
// 1.index 只有左节点
// index 有左右子节点
//默认和左边进行比较
childIndex := (index << 1) + 1
childValue := this.Array[childIndex]
rightIndex := childIndex + 1
if rightIndex < this.size && this.Array[rightIndex] > childValue {
childIndex = rightIndex
childValue = this.Array[childIndex]
}
if v >= childValue {
break
}
this.Array[index] = childValue
index = childIndex

}
this.Array[index] = v
// 在99999 比较情况下 选择排序和堆排序
//排序结果 无 排序比较次数 4999950000 排序交换次数 99999 耗时 10019693000
//排序结果 无 排序比较次数 0 排序交换次数 99999 耗时 12014000
}
``````

# 4.二分搜索

``````package mysort

type Binarysearch struct {
Data []int
}
// 前提数组是要有序的
//查找v在有序数组array中的位置
func (this *Binarysearch) IndexOf(v int) (index int) {
if this.Data == nil || len(this.Data) == 0 {
return -1
}
begin := 0
end := len(this.Data)
for begin < end {
mid := (begin + end) >> 1
if this.Data[mid] > v {
end = mid
} else if this.Data[mid] < v {
begin = mid + 1
} else {
index = mid
return
}

}
return -1
}
//查找v在有序数组array中待插入位置
func (this *Binarysearch) Find(v int) (index int) {
if this.Data == nil || len(this.Data) == 0 {
return -1
}
begin := 0
end := len(this.Data)
for begin < end {
mid := (begin + end) >> 1
if this.Data[mid] > v {
end = mid
} else if this.Data[mid] < v {
begin = mid + 1
}

}
return begin
}
``````

# 5.插入排序

``````package mysort

type InsertionSort struct {
Sort
Binarysearch

}
//插入排序(Insertion Sort)
//插入排序非常类似于扑克牌的排序
//执行流程
//1 在执行过程中，插入排序会将序列分为2部分
//头部是已经排好序的，尾部是待排序的
//2 从头开始扫描每一个元素
//每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
func (this *InsertionSort) SortFunc() {
this.SortFunc2()

}
//
func (this *InsertionSort) SortFunc0() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
current := begin
for current > 0 {
if this.ComWithIndex(current,current -1) < 0 {
this.Swap(current,current-1)
}
current --
}
}
}
// 优化 将交换改为挪动
// 先将代插入的元素备份，然后挪动比其大的元素
// 将待插入的元素放到这个位置
func (this *InsertionSort) SortFunc1() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
current := begin
beginV := this.Array[begin]
for current > 0 && this.ComWithValue(beginV,this.Array[current -1])< 0{
this.Array[current]=this.Array[current -1]
current --
}
this.Array[current] = beginV

}
}
// 使用二分查找
func (this *InsertionSort) SortFunc2() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
beginV := this.Array[begin]
this.Data = this.Array
index := this.Find(begin)
for i := begin; i > index ; i-- {
this.Array[i]=this.Array[i -1]
}
this.Array[index] = beginV

}
}
``````

# 6.归并排序

1. 不断地将当前序列平均分割成2个子序列 (分割)
直到不能再分割(序列中只剩1个元素)
2. 不断地将2个子序列合并成一个有序序列 (合并)
直到最终只剩下1个有序序列
``````package mysort

type MergeSort struct {
leftArray []int
Sort
}

func (this *MergeSort) SortFunc() {
this.leftArray = make([]int, len(this.Array)>>1)
this.sort(0, len(this.Array))
}

// [begin,end)
func (this *MergeSort) sort(begin, end int) {
if end-begin < 2 {
return
}

mid := (begin + end) >> 1
this.sort(begin, mid)
this.sort(mid, end)
this.merge(begin, mid, end)

}

// 将 【begin mid) 和 [mid end)
func (this *MergeSort) merge(begin, mid, end int) {
li, le := 0, mid-begin
ri, re := mid, end
ai := begin
// 备份左边数组  将 [begin,mid) 备份出来
for i := li; i < le; i++ {
this.leftArray[i] = this.Array[begin+i]
}
//如果左边还没有结束，如果右边结束的话，那么就不用管任何事情了
for li < le {
if ri < re && this.ComWithValue(this.Array[ri], this.leftArray[li]) < 0 {
this.Array[ai] = this.Array[ri]
ai++
ri++
} else {
this.Array[ai] = this.leftArray[li]
ai++
li++
}
}
}
//排序数组大小 1000000 排序方法 堆排序 排序比较次数 18388630 排序交换次数 999999 耗时 191247000
//排序数组大小 1000000 排序方法 归并排序 排序比较次数 18670630 排序交换次数 0 耗时 135949000

``````

# 总结时间耗时

``````//排序数组大小 100000 排序方法 归并排序 比较次数 1536231 交换次数 0 耗时 18 ms
//排序数组大小 100000 排序方法 堆排序 比较次数 1509851 交换次数 99999 耗时 21 ms
//排序数组大小 100000 排序方法 插入排序 比较次数 0 交换次数 0 耗时 4613 ms
//排序数组大小 100000 排序方法 选择排序 比较次数 4999950000 交换次数 99999 耗时 13306 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999418601 交换次数 2506933128 耗时 22555 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999950000 交换次数 2506933128 耗时 23048 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999880994 交换次数 2506933128 耗时 24453 ms
``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

# 1.冒泡排序(Bubble Sort)

1 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置 ✓ 执行完一轮后，最末尾那个元素就是最大的元素
2 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序

``````for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}
``````

## 冒泡排序 – 优化1

``````for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}

}
``````

## 冒泡排序 – 优化2

``````//最坏、平均时间复杂度:O(n2)  最好时间复杂度:O(n)
//空间复杂度:O(1)
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}
``````

#### golang 源码

``````package mysort

import (
"fmt"
"time"
)

type Sort struct {
Array     []int
CmpCount  int64
SwapCount int64
begin     int64
FuncType     string

}

func (this *Sort) SortArray(array []int)  {

this.Array = make([]int, len(array))
copy(this.Array, array)
this.begin = time.Now().UnixNano()

}
func (this *Sort) SortFunc() {
if this.Array == nil || len(this.Array) < 2 {
return
}
}
func (this *Sort) ComWithIndex(i1, i2 int) int {
this.CmpCount++
return this.Array[i1] - this.Array[i2]
}
func (this *Sort) ComWithValue(v1, v2 int) int {
this.CmpCount++
return v1 - v2
}
func (this *Sort) Swap(i1, i2 int) {
this.Array[i2], this.Array[i1] = this.Array[i1], this.Array[i2]
this.SwapCount++
}
func (this *Sort)ToString()  {
fmt.Println("排序数组大小", len(this.Array),"排序方法",this.FuncType,"比较次数",this.CmpCount,"交换次数",this.SwapCount,"耗时",(time.Now().UnixNano() - this.begin)/1e6,"ms")

}

``````
``````package mysort

type BubbleSort struct {
Sort
}

func (this *BubbleSort) SortArray(array []int) {
this.Sort.SortArray(array)
}
func (this *BubbleSort) SortFunc()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}

}
// 设置一个bool 的标志，判断是否进行过交换
func (this *BubbleSort) SortFunc1()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}

}

}
func (this *BubbleSort) SortFunc2()  {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}

}
``````
``````package main

import (
"fmt"
"iktolin.com/mysort"
"iktolin.com/struct/firstStudy/Heap"
"math/rand"
"sync"
"time"
)

func main() {

algorithm()

}
// 算法
func algorithm() {
wg := sync.WaitGroup{}
var array []int
rand.Seed(time.Now().UnixNano())
for i := 0; i < 100000; i++ {
x := rand.Intn(10209023)
array = append(array, x)

}

//fmt.Println("排序前",array)
//// 时间复杂度 O(n2)
go func(array []int, w *sync.WaitGroup) {
bubbleSort := mysort.BubbleSort{}
bubbleSort.SortArray(array)
bubbleSort.SortFunc()
bubbleSort.ToString()
w.Done()
}(array, &wg)

//fmt.Println(array)
// 使用bool 值判断是否进行过排序，适用于原来就是排好序的
go func(array []int, w *sync.WaitGroup) {
bubbleSort1 := mysort.BubbleSort{}
bubbleSort1.SortArray(array)
bubbleSort1.SortFunc1()
bubbleSort1.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
bubbleSort2 := mysort.BubbleSort{}
bubbleSort2.SortArray(array)
bubbleSort2.SortFunc2()
bubbleSort2.ToString()
w.Done()
}(array, &wg)
// 使用bool 值判断是否进行过排序，适用于其中有局部排好序的

go func(array []int, w *sync.WaitGroup) {
slect := mysort.SelectionSort{}
slect.SortArray(array)
slect.SortFunc()
slect.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
heap := mysort.HeapSort{}
heap.SortArray(array)
heap.SortFunc()
heap.ToString()
w.Done()
}(array, &wg)
go func(array []int, w *sync.WaitGroup) {
insertion := mysort.InsertionSort{}
insertion.SortArray(array)
insertion.SortFunc()
insertion.ToString()
w.Done()
}(array, &wg)

go func(array []int, w *sync.WaitGroup) {
merge := mysort.MergeSort{}
merge.SortArray(array)
merge.SortFunc()
merge.ToString()
w.Done()
}(array, &wg)

wg.Wait()
//排序数组大小 100000 排序方法 归并排序 比较次数 1536231 交换次数 0 耗时 18 ms
//排序数组大小 100000 排序方法 堆排序 比较次数 1509851 交换次数 99999 耗时 21 ms
//排序数组大小 100000 排序方法 插入排序 比较次数 0 交换次数 0 耗时 4613 ms
//排序数组大小 100000 排序方法 选择排序 比较次数 4999950000 交换次数 99999 耗时 13306 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999418601 交换次数 2506933128 耗时 22555 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999950000 交换次数 2506933128 耗时 23048 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999880994 交换次数 2506933128 耗时 24453 ms

}

``````

# 2.选择排序（Selection Sort）

1. 从序列中找出最大的那个元素，然后与最末尾的元素交换位置 执行完一轮后，最末尾的那个元素就是最大的元素

2. 忽略 1 中曾经找到的最大元素，重复执行步骤 1

``````for end := len(this.Array) - 1; end > 0; end-- {
max := 0
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
max = begin
}
}
this.Swap(max, end)
}
``````

//选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
//最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于不稳定排序

### src

``````package mysort

type SelectionSort struct {
Sort
}

//1 从序列中找出最大的那个元素，然后与最末尾的元素交换位置 执行完一轮后，最末尾的那个元素就是最大的元素
//2 忽略 1 中曾经找到的最大元素，重复执行步骤 1

//选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
//最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于不稳定排序
func (this *SelectionSort) SortFunc() {
this.Sort.SortFunc()

for end := len(this.Array) - 1; end > 0; end-- {
max := 0
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
max = begin
}
}
this.Swap(max, end)
}

}
``````
``````package main

import (
"fmt"
"iktolin.com/mysort"
"math/rand"
"time"
)

func main()  {
var array []int
rand.Seed(time.Now().UnixNano())
for i := 0; i < 40; i++ {
x := rand.Intn(100)
array = append(array, x)

}

fmt.Println("排序前",array)
// 时间复杂度 O(n2)
bubbleSort := mysort.BubbleSort{}
bubbleSort.SortArray(array)
bubbleSort.SortFunc()
bubbleSort.ToString()
//fmt.Println(array)
// 使用bool 值判断是否进行过排序，适用于原来就是排好序的
bubbleSort1 := mysort.BubbleSort{}
bubbleSort1.SortArray(array)
bubbleSort1.SortFunc1()
bubbleSort1.ToString()
// 使用bool 值判断是否进行过排序，适用于其中有局部排好序的
bubbleSort2 := mysort.BubbleSort{}
bubbleSort2.SortArray(array)
bubbleSort2.SortFunc2()
bubbleSort2.ToString()

slect :=mysort.SelectionSort{}
slect.SortArray(array)
slect.SortFunc()
slect.ToString()
}
//排序前 [68 23 47 62 33 4 97 49 46 20 25 24 77 88 66 16 6 44 98 11 70 68 30 5 29 46 12 96 31 27 60 24 76 21 19 44 94 46 82 77]
//排序比较次数 780 排序交换次数 369
//排序比较次数 725 排序交换次数 369
//排序比较次数 643 排序交换次数 369
//排序比较次数 780 排序交换次数 39
``````

# 3.选择排序的优化方案（堆排序）

``````package mysort

type HeapSort struct {
Sort
size int
}

// 对数据进行原地建堆
//将建立好的堆的root最后的位置交换位置，然后将size -- 然后将0号位置进行下滤操作
//siftdown 直到堆的值为1
// 选最值使用堆来操作
// 第一个叶子节点是size 的一半 所以第一个非叶子节点 是 (size >> 1) -1
func (this *HeapSort) SortFunc() {
this.size = len(this.Array)
for i := (this.size >> 1) - 1; i >= 0; i-- {
this.siftDown(i)
}
for this.size > 1 {
this.Swap(0, this.size-1)
this.size--
this.siftDown(0)
}

}
func (this *HeapSort) siftDown(index int) {
v := this.Array[index]
half := (this.size >> 1)
// 1.找其左右子节点 找到最大的子节点开始交换数值
for index < half {
// 1.index 只有左节点
// index 有左右子节点
//默认和左边进行比较
childIndex := (index << 1) + 1
childValue := this.Array[childIndex]
rightIndex := childIndex + 1
if rightIndex < this.size && this.Array[rightIndex] > childValue {
childIndex = rightIndex
childValue = this.Array[childIndex]
}
if v >= childValue {
break
}
this.Array[index] = childValue
index = childIndex

}
this.Array[index] = v
// 在99999 比较情况下 选择排序和堆排序
//排序结果 无 排序比较次数 4999950000 排序交换次数 99999 耗时 10019693000
//排序结果 无 排序比较次数 0 排序交换次数 99999 耗时 12014000
}
``````

# 4.二分搜索

``````package mysort

type Binarysearch struct {
Data []int
}
// 前提数组是要有序的
//查找v在有序数组array中的位置
func (this *Binarysearch) IndexOf(v int) (index int) {
if this.Data == nil || len(this.Data) == 0 {
return -1
}
begin := 0
end := len(this.Data)
for begin < end {
mid := (begin + end) >> 1
if this.Data[mid] > v {
end = mid
} else if this.Data[mid] < v {
begin = mid + 1
} else {
index = mid
return
}

}
return -1
}
//查找v在有序数组array中待插入位置
func (this *Binarysearch) Find(v int) (index int) {
if this.Data == nil || len(this.Data) == 0 {
return -1
}
begin := 0
end := len(this.Data)
for begin < end {
mid := (begin + end) >> 1
if this.Data[mid] > v {
end = mid
} else if this.Data[mid] < v {
begin = mid + 1
}

}
return begin
}
``````

# 5.插入排序

``````package mysort

type InsertionSort struct {
Sort
Binarysearch

}
//插入排序(Insertion Sort)
//插入排序非常类似于扑克牌的排序
//执行流程
//1 在执行过程中，插入排序会将序列分为2部分
//头部是已经排好序的，尾部是待排序的
//2 从头开始扫描每一个元素
//每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
func (this *InsertionSort) SortFunc() {
this.SortFunc2()

}
//
func (this *InsertionSort) SortFunc0() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
current := begin
for current > 0 {
if this.ComWithIndex(current,current -1) < 0 {
this.Swap(current,current-1)
}
current --
}
}
}
// 优化 将交换改为挪动
// 先将代插入的元素备份，然后挪动比其大的元素
// 将待插入的元素放到这个位置
func (this *InsertionSort) SortFunc1() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
current := begin
beginV := this.Array[begin]
for current > 0 && this.ComWithValue(beginV,this.Array[current -1])< 0{
this.Array[current]=this.Array[current -1]
current --
}
this.Array[current] = beginV

}
}
// 使用二分查找
func (this *InsertionSort) SortFunc2() {
for begin := 1; begin < len(this.Array); begin++ {
// 找合适的位置然后将数放进去
beginV := this.Array[begin]
this.Data = this.Array
index := this.Find(begin)
for i := begin; i > index ; i-- {
this.Array[i]=this.Array[i -1]
}
this.Array[index] = beginV

}
}
``````

# 6.归并排序

1. 不断地将当前序列平均分割成2个子序列 (分割)
直到不能再分割(序列中只剩1个元素)
2. 不断地将2个子序列合并成一个有序序列 (合并)
直到最终只剩下1个有序序列
``````package mysort

type MergeSort struct {
leftArray []int
Sort
}

func (this *MergeSort) SortFunc() {
this.leftArray = make([]int, len(this.Array)>>1)
this.sort(0, len(this.Array))
}

// [begin,end)
func (this *MergeSort) sort(begin, end int) {
if end-begin < 2 {
return
}

mid := (begin + end) >> 1
this.sort(begin, mid)
this.sort(mid, end)
this.merge(begin, mid, end)

}

// 将 【begin mid) 和 [mid end)
func (this *MergeSort) merge(begin, mid, end int) {
li, le := 0, mid-begin
ri, re := mid, end
ai := begin
// 备份左边数组  将 [begin,mid) 备份出来
for i := li; i < le; i++ {
this.leftArray[i] = this.Array[begin+i]
}
//如果左边还没有结束，如果右边结束的话，那么就不用管任何事情了
for li < le {
if ri < re && this.ComWithValue(this.Array[ri], this.leftArray[li]) < 0 {
this.Array[ai] = this.Array[ri]
ai++
ri++
} else {
this.Array[ai] = this.leftArray[li]
ai++
li++
}
}
}
//排序数组大小 1000000 排序方法 堆排序 排序比较次数 18388630 排序交换次数 999999 耗时 191247000
//排序数组大小 1000000 排序方法 归并排序 排序比较次数 18670630 排序交换次数 0 耗时 135949000

``````

# 总结时间耗时

``````//排序数组大小 100000 排序方法 归并排序 比较次数 1536231 交换次数 0 耗时 18 ms
//排序数组大小 100000 排序方法 堆排序 比较次数 1509851 交换次数 99999 耗时 21 ms
//排序数组大小 100000 排序方法 插入排序 比较次数 0 交换次数 0 耗时 4613 ms
//排序数组大小 100000 排序方法 选择排序 比较次数 4999950000 交换次数 99999 耗时 13306 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999418601 交换次数 2506933128 耗时 22555 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999950000 交换次数 2506933128 耗时 23048 ms
//排序数组大小 100000 排序方法 冒泡排序 比较次数 4999880994 交换次数 2506933128 耗时 24453 ms
``````