选择排序python——数据结构2_numbers.sort()

选择排序

将无序列表变为有序列表
每次从列表中找到最大/最小的元素，依次放入新列表中

时间复杂度

每次查找最小元素时，所需要的时间都为O(n)，共需查找n次，则需要的总时间位O(n×n)，即O(n²)
【n+(n-1)+(n-2)+…+2+1 = (1+n)*n/2 = n²/2+n/2】

时间复杂度：O(n²)
实质：将大的元素往后调，从小到大排序
原理：
选择排序有两层循环

• 第一层大循环：将列表中最小的数换到第一位，每循环一次列表长度从前往后减少一位
• 第二层小循环：在第一层循环里，实现将最小的数换到第一位，固定第一位i，j按位向后移动，若numbers[i]大于numbers[j]则交换
  选择排序所得到的结果即为使用函数numbers.sort()所得结果

numbers=[5,18,9,11,1]
numbers.sort()
1
2

#选择排序
numbers=[5,18,9,11,1]
for i in range(len(numbers)):
    for j in range(i+1,len(numbers)):
        if numbers[i] > numbers[j]:
            numbers[i],numbers[j]=numbers[j],numbers[i]     #快速交换
            print(numbers)
    print('------------------->',i)
1
2
3
4
5
6
7
8

#python实现代码
def findSmallest(arr):			#找到最小元素
	smallest = arr[0]
	smallest_index = 0
	for i in range(1, len(arr)):	#起始元素为零号元素
		if arr[i] < smallest:
			smallest = arr[i]
			smallest_index = i
	return smallest_index		#返回最小元素索引

def selectionSort(arr):
	newArr = []					#新建空列表
	for i in range(len(arr)):
		smallest = findSmallest(arr)	#找到最小元素
		newArr.append(arr.pop(smallest))	#将最小元素pop出加入新列表
	return newArr					#返回有序新列表

print selectionSort([9, 10, 1, 6, 13])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18