选择排序:
时间复杂度 O(n**2)
没有办法知道当前轮是否已经达到排序要求, 但是可以知道极值是否在目标索引位置上
遍历次数 1,...,n-1 之和 n(n-1)/2
对比冒泡法: 减少了交换次数, 提高了效率, 性能略好
方法三, 四实际上降低的是平均时间复杂度
方法一:
- nums = [1, 2, 6, 7, 8, 9, 3, 4, 5]
- for i in range(len(nums)):
- maxindex = i
- for j in range(i + 1, len(nums)):
- if nums[j] <nums[maxindex]:
- maxindex = j
- if i != maxindex:
- nums[i], nums[maxindex] = nums[maxindex], nums[i]
- print(nums)
方法二 (基于方法一的优化):
优化点: 内循环一次遍历同时取出最大, 最小值 放在两端
- nums = [7, 19, 15, 12, 15, 5, 13, 14, 8, 15]
- length = len(nums)
- for i in range(length // 2):
- maxindex = i
- minindex = length - i - 1
- minorigin = length - i - 1
- for j in range(i + 1, length - i):
- if nums[j]> nums[maxindex]:
- maxindex = j
- if nums[j-1] <nums[minindex]:# 正序比较 或者逆序比较都可以 length - j - 1
- minindex = j - 1
- if i != maxindex:
- nums[i], nums[maxindex] = nums[maxindex], nums[i]
- if i == minindex: #如果 i 就是最小值索引, 则执行此 if, 因为上一行索引 i 的值与最大值已经进行了交换
- minindex = maxindex
- if minorigin != minindex:
- nums[minorigin], nums[minindex]=nums[minindex], nums[minorigin]
- print(nums)
方法三 (基于方法二的优化):
优化点: 如果一次迭代最大值与最小值相等则剩余元素值相同, 即已排序完毕
- nums = [7, 19, 15, 12, 15, 5, 13, 14, 8, 15]
- length = len(nums)
- for i in range(length // 2):
- maxindex = i
- minindex = length - i - 1
- minorigin = length - i - 1
- for j in range(i + 1, length - 1):
- if nums[j]> nums[maxindex]:
- maxindex = j
- if nums[length - j - 1] <nums[minindex]:
- minindex = length - j - 1
- if minindex == maxindex: #!
- break
- if i != maxindex:
- nums[i], nums[maxindex] = nums[maxindex], nums[i]
- if i == minindex:
- minindex = maxindex
- if minorigin != minindex:
- nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
- print(nums)
方法四 (基于方法三的优化):
如果列表为下面这种情况, 最小值无需交换
- nums =[1, 1, 1, 1, 1, 1, 1, 1, 2]
- length = len(nums)
- for i in range(length // 2):
- maxindex = i
- minindex = length - i - 1
- minorigin = length - i - 1
- for j in range(i + 1, length - 1):
- if nums[j]> nums[maxindex]:
- maxindex = j
- if nums[length - j - 1] <nums[minindex]:
- minindex = length - j - 1
- if minindex == maxindex: #!
- break
- if i != maxindex:
- nums[i], nums[maxindex] = nums[maxindex], nums[i]
- if i == minindex:
- minindex = maxindex
- if minorigin != minindex and nums[minorigin] != nums[minindex]: #!
- nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
- print(nums)
习题解析
1. 用户输入一个数字
打印每一位数字及其重复的次数
方法一:
- num = input('>>>')
- d = {}
- for c in num:
- if not d.get(c):
- d[c] = 1
- continue
- d[c] += 1
- print(d)
方法二:
- d ={}
- for c in num:
- if c not in d.keys():
- d[c] = 1
- else:
- d[c] += 1
- print(d)
2. 数字重复统计
随机产生 100 个整数
数字的范围 [-1000, 1000]
升序输出所有不同的数字及其重复的次数
- import random
- n = 100
- nums = [0] * n
- for i in range(n):
- nums[i] = random.randint(-1000, 1000)
- print(nums)
- t = nums.copy()
- t.sort()
- print(t)
- d = {}
- for x in nums:
- if x not in d.keys():
- d[x] = 1
- else:
- d[x] += 1
- print(d)
- d1 = sorted(d.items())
- print(d1)
3. 字符串重复统计
字符表'abcdefghijklmnopqrstuvwxyz'
随机挑选 2 个字母组成字符串, 共挑选 100 个
降序输出所有不同的字符串及重复的次数
- import random
- alphabet = 'abcdefghijklmnopqrstuvwxyz'
- words = []
- for _ in range(100):
- words.append(''.join(random.choice(alphabet) for _ in range(2)))
- d = {}
- for x in words:
- d[x] = d.get(x, 0) + 1
- print(d)
- d1 = sorted(d.items(), reverse = True)
- print(d1)
4. 返回 1-10 平方的列表
[i ** 2 for i in range(1,11)]
5. 有一个列表 lst = [1,4,9,16,2,5,10,15], 生成一个新列表, 要求新列表元素是 lst 相邻 2 项的和
- lst = [1,4,9,16,2,5,10,15]
- [lst[i] + lst[i + 1] for i in range(len(lst) - 1)]
6. 打印九九乘法表
[print('{}*{}={:<{}}{}'.format(j, i, j * i,2 if j ==1 else 3, ''if i != j else'\n'),end ='')for i in range(1,10) for j in range(1,i + 1)]
7."0001.abadicddws" 是 ID 格式, 要求 ID 格式是以点号分割, 左边是 4 位从 1 开始的整数, 右边是
10 位随机小写英文字母. 请依次生成前 100 个 ID 的列表
- import random
- [('{:>04}'.format(i) + '.' + ''.join('abcdefghijklmnopqrstuvwxyz'[random.randint(0,25)] for _ in range(10))) for i in range(1,101)]
来源: http://www.bubuko.com/infodetail-2554152.html