python算法优化练习之排序

题目

依次接收用户输入的3个数，排序后打印。

1 - 转换int后，判断大小排序

nums = []
for i in range(3):
    nums.append(int(input(‘{}:‘.format(i))))

if nums[0]>nums[i]:
    if nums[0] > nums[2]:
        i3=nums[0]
        if nums[1]>nums[2]:
            i2=nums[1]
            i1=nums[2]
        else:
            i2=nums[2]
            i1=nums[1]
    else:
        i2=nums[0]
        i3=nums[2]
        i1=nums[1]
else:
    if nums[0]>nums[2]:
        i3=nums[1]
        i2=nums[0]
        i1=nums[2]
    else:
        if nums[1]<nums[2]:
            i1 = nums[0]
            i2 = nums[1]
            i3 = nums[2]
        else:
            i1 = nums[0]
            i2 = nums[2]
            i3 = nums[3]
print(i1,i2,i3)

2 - 优化

nums = []
for i in range(3):
    nums.append(int(input(‘{}:‘.format(i))))

if nums[0] > nums[1]:
    if nums[0] > nums[2]:
        if nums[1] > nums[2]:
            out = [2,1,0]
        else:
            out = [1,2,0]
else:
    if nums[0] > nums[2]:
        out=[2,0,1]
    else:
        if nums[1] < nums[2]:
            out = [0,1,2]
        else:
            out = [0,2,1]
out.reverse() 通过这里，可以控制从小到大升序，从大到小降序
for i in out:
    print(nums[i],end="")

3 - 使用max函数

# 用最大值函数max、或者for循环，都是可以的
nums = []
for i in range(3):
    nums.append(int(input(‘{}:‘.format(i))))

while True:
    cur = min(nums)
    print(cur)
    nums.remove(cur)
    if len(nums) == 1
        print(nums[0])
        break

4 - 列表sort函数

nums = []
for i in range(3):
    nums.append(int(input(‘{}:‘.format(i))))

nums.sort(reverse=False)
print(nums)

5 - 冒泡法

利用索引，交换排序更漂亮。
让两个数进行比较。
大的上去，往右边跑。

冒泡法

• 属于交换排序

• 两两比较大小，交换位置。如同水泡咕嘟咕嘟往上冒

• 结果分为升序和降序排列

• 升序
  n个数，从左到右，编号从0开始到n-1，
  索引0和1的值比较，如果索引0大，则交换两者位置，如果索引1大，则不交换。
  继续比较索引1和2的值，将大值放在右侧。
  直至n-2和n-1比较完，第一轮比较完成。
  第二轮从索引0比较到n-2，因为最右侧n-1位置上已经是最大值了。
  依次类推，每一轮都会减少最右侧的，不参与比较，直至剩下最后2个数比较。

• 降序

  • 和升序相反

冒泡法应该学会，但是效率不太高

冒泡法代码实现（一）

num_list=[
    [1,9,8,5,6,7,4,3,2],
    [1,2,3,4,5,6,7,8,9]
]
nums=num_list[0]
print(nums) # [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
count_swap = 0
count = 0
# bubble_sort
for i in range(length): # 外层循环控制的是走多少轮，凑这个数
    for j in range(length-i-1): # 内层循环控制的是单轮比较多少次，凑这个数
        count+=1
        if nums[j] > nums[j+1]:
            tmp=nums[j]
            nums[j]=nums[j+1]
            nums[j+1]=tmp
            count_swap +=1
print(nums,count_swap,count)

冒泡法代码实现（二）

num_list=[
    [1,9,8,5,6,7,4,3,2],
    [1,2,3,4,5,6,7,8,9]
]
nums=num_list[1]
print(nums) # [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
count_swap = 0
count = 0
# bubble_sort
for i in range(length): # 外层循环控制的是走多少轮，凑这个数
    for j in range(length-i-1): # 内层循环控制的是单轮比较多少次，凑这个数
        flag=True
        count+=1
        if nums[j] > nums[j+1]:
            tmp=nums[j]
            nums[j]=nums[j+1]
            nums[j+1]=tmp
            count_swap +=1
            flag=False
    if flag:
        break
print(nums,count_swap,count)

冒泡法总结：

• 冒泡法需要数据一轮轮比较。
• 可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序。如果发生交换，继续下一轮排序。
• 最差的排序情况是，初始顺序与目标顺序完全相反，遍历次数1,...,n-1之和n(n-1)/2
• 最好的情况排序是，初始顺序与目标顺序完全相同，遍历次数n-1
• 时间复杂度O(n2)

后续：

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 堆排序
5. 快速排序

python算法优化练习之排序

原文：https://www.cnblogs.com/gnuzsx/p/12723390.html