四.排序(冒泡/选择)
目录
11-排序介绍
常见排序算法:
12-冒泡排序介绍
代码要求:
思路:
13-冒泡排序
代码:
14-选择排序
简单写法:
好的写法:
11-排序介绍
排序：将一组“无序”的记录序列调整为“有序”的记录序列。 列表排序：将无序列表变为有序列表 输入：列表 输出：有序列表 升序与降序 内置排序函数：sort()
常见排序算法:
12-冒泡排序介绍
列表每两个相邻的数，如果前面比后面大，则交换这两个数.
一趟排序完成后，则无序区减少一个数，有序区增加一个数。
代码要求:
列表每两个相邻的数，如果前面比后面大，则交换这两个数。
一趟排序完成后，则无序区减少一个数，有序区增加一个数。
代码关键点：趟、无序区范围.
思路:
走了多少趟,每次谁和谁交换(一趟中交换了多少次).
假设一共有n个元素. --那就要走(n-1)趟,因为最后一趟不需要走了. 第0(i=0)趟--两两交换需要n-1--->排出最大值 1 n-1-1--->得出次大值 2 n-1-2 . . . n n-1-i
13-冒泡排序
代码:
import random
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
for j in range(len(li)-i-1): #每i趟,箭头移到的次数(j)
if li[j] > li[j+1]: #如果下面的值大于上面的值. 那么这两个值就互相换位置. 以此类推.
li[j], li[j+1] = li[j+1], li[j]
li=[random.randint(0,9999) for i in range(100)]
print(li)
print('*-*'*30)
bubble_sort(li)
print(li)
14-选择排序
简单写法:
--缺点:占用双倍内存 一个循环+两个遍历(min,remove),复杂度较高.
def select_sort_simple(li): li_new = [] #创建一个新列表,接收值(有序) for i in range(len(li)): #循环n次, min_val = min(li) #依次找到最小的数, li_new.append(min_val) #放入新列表. li.remove(min_val) #将就列表的值依次移除. return li_new li=[4,2,3,6,7,1] print(select_sort_simple(li))
好的写法:
--不开辟新的列表.
只需要交换最小的就行啦.
循环遍历n次,每次找到最小的值,最小的值交换到最前面,
def select_sort(li): for i in range(len(li)-1): #循环n趟(i是第几趟) min_loc = i #假设最小的值在无序的第一个位置. for j in range(i+1,len(li)): #循环无序的值, if li[j]<li[min_loc]: #如果值小于假设的那个最小的值. min_loc = j #假设的最小的值就换. if min_loc !=i: li[i], li[min_loc] = li[min_loc], li[i] #最小的值与无序的最小的值交换. print(li) li = [5,3,1,5,2,8,1,4] print(li) select_sort(li) ----------------- [5, 3, 1, 5, 2, 8, 1, 4] [1, 3, 5, 5, 2, 8, 1, 4] [1, 1, 5, 5, 2, 8, 3, 4] [1, 1, 2, 5, 5, 8, 3, 4] [1, 1, 2, 3, 5, 8, 5, 4] [1, 1, 2, 3, 4, 8, 5, 5] [1, 1, 2, 3, 4, 5, 8, 5] [1, 1, 2, 3, 4, 5, 5, 8]