算法快学笔记(三):选择排序的原理与实现

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)
最新回复(0)
Google XML地图百度 XML地图Google txt地图百度 txt地图17社