基于Go语言实现选择排序算法及优化

目录
  • 选择排序
  • 图片演示
  • 普通算法
  • 优化算法
  • 小结

选择排序

选择排序是一种简单的比较排序算法,它的算法思路是首先从数组中寻找最小(大)的元素,然后放到数组中的第一位,接下来继续从未排序的元素中寻找最小(大)元素,然后放到已排序元素的末尾,依次类推,直到所有元素被排序。

图片演示

普通算法

import "fmt"

func main() {
    nums := [8]int{8, 2, 3, 1, 6, 5, 7, 4}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}

func SelectionSort(nums [8]int) {
    for i := 0; i < len(nums)-1; i++ {
        minPos := i
        for j := i + 1; j < len(nums); j++ {
            if nums[minPos] > nums[j] {
                    minPos = j
            }
        }
        nums[i], nums[minPos] = nums[minPos], nums[i]
        fmt.Printf("第 %d 轮后:%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组:", nums)
}

执行结果:

原数组: [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后:[1 2 3 8 6 5 7 4]
第 2 轮后:[1 2 3 8 6 5 7 4]
第 3 轮后:[1 2 3 8 6 5 7 4]
第 4 轮后:[1 2 3 4 6 5 7 8]
第 5 轮后:[1 2 3 4 5 6 7 8]
第 6 轮后:[1 2 3 4 5 6 7 8]
第 7 轮后:[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组: [1 2 3 4 5 6 7 8]

  • 升序排序。
  • 使用 i 变量表示最小元素的待放位置。
  • minPos 变量记录最小元素的的下标值,默认为 i
  • 通过变量 j 去寻找最小元素,ji + 1 的位置开始寻找。
  • 找到比 nums[minPos] 还小的元素,则将 j 的下标值赋给 minPos
  • 一轮下来,将最小元素的位置 minPosi 的位置互换,然后继续下一轮寻找,直到所有元素都被排序。
  • 该算法的时间复杂度为 O(N²)。

优化算法

普通算法是寻找最小值或最大值,然后放到指定位置。优化算法的改进点是同时寻找最小值和最大值。

import (
    "fmt"
)

func main() {
    nums := [4]int{3, 1, 4, 2}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}

func SelectionSort(nums [4]int) {
    for left, right := 0, len(nums)-1; left <= right; {
        minPos := left
        maxPos := left
        for i := left + 1; i <= right; i++ {
            if nums[minPos] > nums[i] {
                minPos = i
            }
            if nums[maxPos] < nums[i] {
                maxPos = i
            }
        }
        nums[left], nums[minPos] = nums[minPos], nums[left]
        // 如果最大值刚好是在 left,待放最小值的位置,那么最大值就会被换走,所以需要判断一下
        if maxPos == left {
            maxPos = minPos
        }
        nums[right], nums[maxPos] = nums[maxPos], nums[right]
        fmt.Printf("第 %d 轮后:%v\n", left+1, nums)
        left++
        right--
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组:", nums)
}

执行结果:

原数组: [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后:[1 2 3 4 6 5 7 8]
第 2 轮后:[1 2 3 4 6 5 7 8]
第 3 轮后:[1 2 3 4 5 6 7 8]
第 4 轮后:[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组: [1 2 3 4 5 6 7 8]

  • left 变量表示待放最小值的位置,right 变量表示待放最大值的位置。minPos 记录最小值的下标值,maxPos 记录最大值的下标值,通过变量 i 去寻找最小值和最大值,寻找完毕后将它们进行交换。
  • 有一个注意的地方是,如果最大值刚好是在 left ,待放最小值的位置,那么最大值就会被换到 minPos 的位置,所以需要判断一下,纠正下标值。
  • 从执行结果来看,优化后的算法效率快了一倍,但是时间复杂度仍为 O(N²)。

小结

本文简单介绍了什么是选择排序,然后通过图片的方式演示选择排序的过程,接下来是实现 O(N²) 时间复杂度的算法,最后优化算法,从结果来看,优化后的算法效率快了一倍,但是时间复杂度仍为 O(N²)。

以上就是基于Go语言实现选择排序算法及优化的详细内容,更多关于Go语言选择排序算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • Go语言数据结构之选择排序示例详解

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序 冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码 代码如下:

  • 基于Go语言实现选择排序算法及优化

    目录 选择排序 图片演示 普通算法 优化算法 小结 选择排序 选择排序是一种简单的比较排序算法,它的算法思路是首先从数组中寻找最小(大)的元素,然后放到数组中的第一位,接下来继续从未排序的元素中寻找最小(大)元素,然后放到已排序元素的末尾,依次类推,直到所有元素被排序. 图片演示 普通算法 import "fmt" func main() { nums := [8]int{8, 2, 3, 1, 6, 5, 7, 4} fmt.Println("原数组:", num

  • C语言直接选择排序算法详解

    目录 1. 直接选择排序介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度 1.4 空间复杂度 1.5 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 直接选择排序介绍 1.1 定义 直接选择排序是指每次都从剩余数据中选出最大或者最小的,将其排在已经排好的有序表后面. 1.2 基本原理 每次从无序表中选择最小(或最大)元素,将其作为首元素,知道所有元素排完为止.将一个有n个元素的数组从小到大排序,第一次从R[0] ~ R[n-1]中选取最小值,与R[0]交换,第二次从R[

  • C语言选择排序算法及实例代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

  • C语言实现经典排序算法的示例代码

    目录 一.冒泡排序 1.原理 2.实现 3.算法分析 二.选择排序 1.原理 2.实现 3.算法分析 三.插入排序 1.原理 2.实现 3.算法分析 四.希尔排序 1.原理 2.实现 3.算法分析 总结 一.冒泡排序 1.原理 从数组的头开始不断比较相邻两个数的大小,不断将较大的数右移,一个循环后,最大数移至最后一位,无序数组规模减一.不断重复前面动作,知道数组完全有序. 2.实现 void swap(int* a, int* b) { int temp = *a; *a = *b; *b =

  • Go语言实现常用排序算法的示例代码

    目录 冒泡排序 快速排序 选择排序 插入排序 排序算法是在生活中随处可见,也是算法基础,因为其实现代码较短,应用较常见.所以在面试中经常会问到排序算法及其相关的问题,可以说是每个程序员都必须得掌握的了.为了方便大家学习,花了一天的时间用Go语言实现一下常用的算法且整理了一下,如有需要可以参考. 冒泡排序 思路:从前往后对相邻的两个元素依次进行比较,让较大的数往下沉,较小的网上冒,即每当两个相邻的元素比较后发现他们的排序要求相反时,就将它们互换. 时间复杂度:O(N^2) 空间复杂度:O(1) f

  • PHP简单选择排序算法实例

    简单的选择排序算法:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换 复制代码 代码如下: <?php     class Sort{         /**          * 简单的选择排序          *          * @param unknown_type $arr          */         public function selectSort(&$arr) {            

  • python选择排序算法实例总结

    本文实例总结了python选择排序算法.分享给大家供大家参考.具体如下: 代码1: def ssort(V): #V is the list to be sorted j = 0 #j is the "current" ordered position, starting with the first one in the list while j != len(V): #this is the replacing that ends when it reaches the end o

  • java实现选择排序算法

    java实现选择排序算法 public static void selectSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } Sort.swap(array, i, min);//交换i和min } } 选择排序

  • JavaScript实现的选择排序算法实例分析

    本文实例讲述了JavaScript实现的选择排序算法.分享给大家供大家参考,具体如下: 简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较.检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续.这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序. 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-

随机推荐