算法快学笔记（三）：选择排序的原理与实现

亦凉 2022-04-03 10:08 159阅读 0赞

# 1. 原理介绍 #

选择排序是个简单的排序，思路主要通过多次遍历待排序的集合，每次弹出最大/小值并放入新的集合,直到原始集合为空。举个例子：

假设要对A=\[1,2,5,9,3\]按照升序的方式进行排序，步骤与结果如下

1.  从A中找出最大值，将其pop,并放入B中，执行后的结果如下:

A=[2,5,9,3]
    B=[1]

1.  重复执行第一部

A=[5,9,3]
    B=[1,2]

1.  重复执行第一部

A=[5,9]
    B=[1,2,3]

1.  重复执行第一部

A=[9]
    B=[1,2,3,5]

1.  重复执行第一部

A=[]
    B=[1,2,3,5,9]

1.  此时A为空，返回B

# 2. 运行时间分析 #

从上面的过程可以看出，要对A进行排序，必须要执行N轮操作，每一轮操作必须检查列表中的每个元素。随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一个。平均每次检查的元素数为1/2 × n， 因此运行时间为O(n × 1/2 × n),但大O表示法省略诸如1/2这样的常数，因此简单地写作O(n × n)或O(n^2)。

# 3. 代码实现 #

Go语言实现的过程如下：

// 对int数组的选择排序
    func SelectSort(items []int) []int {
    	result := make([]int,len(items))
    	for i:=0;i< len(result);i++{
    		tmpIndex := getMinItemIndex(&items)
    		result[i]=items[tmpIndex]
    		//从原始数组中删除掉被选择的元素
    		items = append(items[:tmpIndex], items[tmpIndex+1:]...)
    	}
    	return result
    }
    
    //获取一个数组中，最小元素的位置
    func getMinItemIndex(ints *[]int) int {
    	//默认假设第一个元素作为临时最小值
    	min := (*ints)[0]
    	smallestIndex :=0
    	for index,item := range *ints {
    		if item < min {
    			min = item
    			smallestIndex =index
    		}
    	}
    	return smallestIndex
    }

# 4. 总结 #

*  选择排序的时间复杂度为:O(n^2)