导读 这篇文章主要为大家介绍了Go语言数据结构之选择排序示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
选择排序

选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件。

思想:

对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头。

给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将:

  • 遍历一遍序列,寻找序列中的最小值。在 [i...n−1] 范围内找出最小值 minValue 的位置 minIndex,
  • 用当前位置的值交换最小值。第 i 项的值与交换 minIndex 的值交换,swap(nums[i],nums[minIndex])
  • 对所有元素重复上述过程,直到整个序列排序完成。将下限 iii 增加1,并重复步骤 1 直到 i=n−2。
  • 伪代码:

    func selectionSort(nums []int, length int) {
      for i := 0; i < length-1; i++ { // O(N)
        minValue = nums[minIdx] // O(N)
        swap(nums[i], nums[minIndex]); // O(1), X may be equal to L (no actual swap)
      }
    }
    动画演示

    Go 代码实现
    package main
    import "fmt"
    func main() {
      unsorted := []int{40, 13, 20, 8, 12, 10, 27}
      length := len(unsorted)
      selectionSort(unsorted, length)
      for i := 0; i < length; i++ {
        fmt.Printf("%d\t", unsorted[i])
      }
    }
    func selectionSort(nums []int, length int) {
      var minIdx int // 被选择的最小的值的位置
      for i := 0; i < length-1; i++ {
        minIdx = i
        // 每次循环的第一个元素为最小值保存
        var minValue = nums[minIdx]
        for j := i; j < length-1; j++ {
          if minValue > nums[j+1] {
            minValue = nums[j+1]
            minIdx = j + 1
          }
        }
        // 如果最小值的位置改变,将当前的最小值位置保存
        if i != minIdx {
          var temp = nums[i]
          nums[i] = nums[minIdx]
          nums[minIdx] = temp
        }
      }
    }

    运行结果为:

    [Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\选择排序\main.go"\
    8 10 12 13 20 27 40
    总结

    选择排序的优点:

  • 易于实现,容易理解
  • 原地排序(不需要额外的存储空间),即 空间复杂度为 O(1)O(1)O(1)
  • 缺点:

  • 扩展性较差
  • 时间复杂度为 O(n2)O(n^2)O(n2)
  • 稳定性:

  • 选择排序是不稳定的排序算法。
  • 以上就是Go语言数据结构之选择排序示例详解的详细内容

    原文来自:

    本文地址://q13zd.cn/go-java-seven.html编辑:向云艳,审核员:逄增宝

    Linux大全:

    Linux系统大全:

    红帽认证RHCE考试心得: