排序算法-归并排序、堆排序、插入排序、选择排序、冒泡排序 golang

作者说明：郭玉乐 yulekwok@gmail.com

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

如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数

//最坏、平均时间复杂度: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)
    wg.Add(7)
    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
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,937评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,503评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,712评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,668评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,677评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,601评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,975评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,637评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,881评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,387评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,971评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2赞 342

推荐阅读更多精彩内容