冒泡排序 选择排序
选择排序
延申问题--怎样找出一个列表中的最大值
请列举出集中方法找出一个列表中的最大值，并将最大值交换到列表的最后
def PickMax(arr,begin,end):
maxVal=arr[begin]
maxIndex=begin
for i in range(begin,end+1):
if maxVal<arr[i]:
maxVal=arr[i]
maxIndex=i
return maxIndex
这里应注意，arr为传入的列表，begin是开始要找最大值的部分，end是结束要找最大值的部分，其中begin和end都是包含在范围里的。
如果利用上面这个找最大值的函数，找出一个区间里的最大值，然后按顺序放到一起，则可将一个列表排好序---这就是交换排序的思想
实现程序如下：
y=[2,7,1,8,9]
for k in range(len(y)-1,0,-1)
mIndex=PickMax(y,0,k)
y[mIndex],y[k]=y[k],[mIndex]
print(y)
其中k是每次要确定大小的位置，则将k作为范围的右边值，选取0~k之间的最大值然后放到k的位置
因为是从小到大排序，而函数是每次找出最大值，所以k的取值是从后向前
冒泡排序
延申问题--怎样找出一个列表中的最大值
相同的延申问题，怎样找出一个列表中的最大值，一个不同的思路
如果从头到尾逐个将列表中的两个元素进行比较，每次比较后进行交换都保证小的在前面大的在后面，则从头到尾循环一遍后最大的一定在最后面，按照这个思路有如下程序。
y=[2,3,4,1,6]
for i in range(0,len(y)-1):
if a[i]>a[i+1]:
a[i],a[i+1]=a[i+1],a[i]
print(a)
最简单的冒泡排序，如果一个列表有5个元素，将上面的程序循环5-1次会有什么效果
程序如下：
y=[2,3,4,1,6]
for k in range(0,4):
for i in range(0,len(y)-1):
if a[i]>a[i+1]:
a[i],a[i+1]=a[i+1],a[i]
print(a)
运行后可以发现，列表被排好序了
但是这里有个问题，并不需要每次里层循环都执行相同的次数，如果一个位置的值被确定了那么这个位置就不需要被重复比较。
所以外层循环可以被看成是遍历每个位置的循环，每遍历一个位置那么这个位置的值就被内层循环确定了，所以程序可以改成：
y=[2,3,4,1,6]
for k in range(0,4):
for i in range(0,len(y)-k-1):
if a[i]>a[i+1]:
a[i],a[i+1]=a[i+1],a[i]
print(a)
通过这个改动里层循环的次数每次都在减少。
延申问题 -- 如果给定的列表已经被排好序了，那么还需要这么多次的比较次数吗
如果一个列表已经是从小到大排好序的，那么可以看到if后面的条件永远不会被满足，所以if永远不会进入。则：
y=[2,3,4,1,6]
flag=1
for k in range(0,4):
for i in range(0,len(y)-1):
if a[i]>a[i+1]:
a[i],a[i+1]=a[i+1],a[i]
flag=0
if flag==1:
break
print(a)
上面的程序只是一个draft版本，因为如果一个列表经过前面的若干次循环后已经变成有序，那么接下来的循环也不需要进行了，则：
y=[2,3,4,1,6]
for k in range(0,4):
flag = 1
for i in range(0,len(y)-1):
if a[i]>a[i+1]:
a[i],a[i+1]=a[i+1],a[i]
flag=0
if flag==1:
break
print(a)
延申问题--如果一个列表前面的值已经是排好序的最小的值，若知识让下表从左到右单向循环则序号比较多次，则：
for j in range(0,len(y)//2):
for i in range(j,len(y)-1-j):
if y[i]>y[i+1]:
y[i],y[i+1]=y[i+1],y[i]
for k in range(len(y)-1-j,j,-1):
if y[k]<y[k-1]:
y[k],y[k-1]=y[k-1],y[k]
print(y)
上面的改进方法叫做鸡尾酒排序
网友评论