Python之选择排序

偏执的太偏执、 2022-02-20 08:45 166阅读 0赞

**选择排序：**  
首先从待排序的数据中选出最小（或最大）的一个元素，放在已排序序列的末尾，然后再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾，以此类推，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

**示例：**

# 查找数组中最小元素，并返回对应索引
    def findSmallest(arr):
    	smallest = arr[0]									#初始对比值及索引
    	smallest_index = 0
    	chang = len(arr)
    	for i in range(1, chang):
    		if arr[i] < smallest:
    			smallest = arr[i] 							#对最小值及索引重新赋值
    			smallest_index = i
    	return smallest_index

**选择排序一：**

def selectionSort(arr):
    	newArr = []
    	chang = len(arr)
    	for i in range(chang):
    		smallest_index = findSmallest(arr)				#获取最小值索引
    		newArr.append(arr.pop(smallest_index))			#删除arr中指定索引smallest_index的值并将删除的值添加到newArr中
    	return newArr
    
    arr = [5, 3, 2, 7, 9]
    print(selectionSort(arr))

**结果为：**

[2, 3, 5, 7, 9]

**选择排序二：**

def selectionSort2(alist):
    	n = len(alist) - 1 									#此处减1可减少下方遍历时重复计算
    	for fillslot in range(n, 0, -1):					#共需遍历n次，因1个元素是不需要再遍历的
    		positionOfMax = 0 								#初始化最大元素索引为0
    		for location in range(1, fillslot + 1):			#循环遍历获取本轮最大元素索引
    			if alist[location] > alist[positionOfMax]:	#若当前元素大于初始化最大元素，则
    				positionOfMax = location 				#更新最大元素索引为当前索引
    		alist[fillslot], alist[positionOfMax] = alist[positionOfMax], alist[fillslot]	#交换位置
     
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    selectionSort2(alist)
    print(alist)

**结果为：**

[17, 20, 26, 31, 44, 54, 55, 77, 93]