学习回顾算法（选择排序）

向右看齐 2022-06-05 06:46 123阅读 0赞

## 前言 ##

选择排序比冒泡排序算法时间上要优秀一点，主要在于冒泡算法每次比较都要交换位置，而选择排序通过记录最大或最下位置的索引，最后只交换一次位置就可以了。

**选择排序算法原理**  
每一次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，知道全部待排序的数据排完。

例子：  
待排序的初始序列为：49、38、65、97、49、13、27、76  
排序过程如下  
![选择排序][SouthEast]

**算法分析**  
（1）时间复杂度  
如果各个元素的初始状态是正序的，一次扫描即可完成排序，所需比较的次数C和记录移动次数M都达到了最小值.C=n-1，M=0。这时候冒泡排序最好的时间复杂度为O（n）。  
如果各个元素是反序的，需要进行n-1此排序。每次排序要进行n-i次元素值的比较（1<=i<=n-1），且每次比较都需要移动记录三次来达到交换位置。这种情况下，比较和移动次数达到最大值： M=n\*(n-1)/2, C == M.  
综上，冒泡排序的平均时间复杂度是O(n^2)。

（2）空间复杂度  
冒泡排序在排序过程中只需要一个临时变量进行两个元素两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。

（3）稳定性  
由于选择排序每次都会将待排序元素列表中最小或最大的元素和排序列表交换。所以选择排序是一种不稳定的排序。

## 算法实现 ##

1、golang实现

package main
    
    import (
        "fmt"
    )
    
    func selectSort(values []int) {
        Len := len(values)
        var mixvalue int
        var mixindex int
        for i := 0; i < Len-1; i++ {
            mixvalue = values[i]
            for j := i; j < Len; j++ {
                if values[j] < mixvalue {
                    mixvalue = values[j]
                    mixindex = j
                }
            }
            values[i], values[mixindex] = values[mixindex], values[i]
        }
    }
    
    func main() {
        values := []int{
       49, 38, 65, 97, 49, 13, 27, 76}
        fmt.Println(values)
        selectSort(values)
        fmt.Println(values)
        return
    }

结果

[49 38 65 97 49 13 27 76]
    [13 27 38 49 49 65 76 97]

[SouthEast]: /images/20220605/2ddec75eebb548698bbcdd151a91cf8d.png