图解算法 -使用Python 学习笔记(3)
排序算法
3.1认识排序
用以排序的依据是键，它所含的值被称为“键值”。通常键值的数据类型有数值类型、中文字符串以及非中文字符串三种。其中中文字符串用该中文内码，如中文繁体BIG5码、中文简体GB码，非中文的用ASCII码来进行比较。
在排序过程中，数据的移动方式可分为“直接移动”和“逻辑移动”两种。这当中逻辑移动不会移动数据存储的位置，尽改变指向这些数据的辅助指针的值。
3.2冒泡排序
data=[16,25,39,27,12,8,45,63]#原始数据
print('冒泡排序:原始数据为:')
for i in range(8):
print('%3d'%data[i],end='')
print()
for i in range(7,-1,-1):#扫描次数
for j in range(i):
if data[j]>data[j+1]:#比较,交换的次数
data[j],data[j+1]=data[j+1],data[j]#比较相邻两数,如果第一个数较大则交换
print('第%d次排序的结果是:'%(8-i),end='')#把各次扫描后的结果打印出来
for j in range(8):
print('%3d'%data[j],end='')
print()
print ('排序后的结果为:')
for j in range(8):
print('%3d' % data[j], end='')
print()
3.3选择排序
def showdata(data):
for i in range(8):
print('%3d' % data[i], end='')
print()
def select(data):
for i in range(7):
for j in range(i + 1, 8):
if data[i] > data[j]: # 比较第i位和第j位元素
data[i], data[j] = data[j], data[i]
print()
data = [16, 25, 39, 27, 13, 8, 45, 63]
print('原始数据:')
for i in range(8):
print('%3d' % data[i], end='')
print('\n-----------------')
select(data)
print('排序后的数据为:')
for i in range(8):
print('%3d' % data[i], end='')
print('')
3.4插入排序
SIZE = 8 # 定义数组大小
def showdata(data):
for i in range(8):
print('%3d' % data[i], end='') # 用来打印数组数据
print()
def insert(data):
for i in range(1, SIZE):
tmp = data[i] # 暂存数据
no = i - 1
while no >= 0 and tmp < data[no]:
data[no + 1] = data[no] # 就把所有元素往后推一位
no -= 1
data[no + 1] = tmp # 最小的元素放在第一位
def main():
data = [16, 25, 39, 27, 13, 8, 45, 63]
print('原始数据:')
showdata(data)
insert(data)
print('排序后的数据为:')
showdata(data)
main()
3.5希尔排序
SIZE = 8 # 定义数组大小
def showdata(data):
for i in range(8):
print('%3d' % data[i], end='') # 用来打印数组数据
print()
def shell(data, size):
k = 1 # k打印次数
jmp = size // 2
while jmp != 0:
for i in range(jmp, SIZE): # i为扫描次数,jmp为设置间距的位移量
tmp = data[i] # tmp用来暂存数据
j = i - jmp # 以j来定位比较的元素
while tmp < data[j] and j >= 0: # 插入排序法
data[j + jmp] = data[i]
j = j - jmp
data[jmp + j] = tmp
print('第%d次排序过程' % k, end='')
k += 1
showdata(data)
print('-----------------')
jmp = jmp // 2 # 控制循环次数
def main():
data = [16, 25, 39, 27, 13, 8, 45, 63]
print('原始数据:')
showdata(data)
print('\n-----------------')
shell(data, SIZE)
main()
3.6合并排序
# 合并排序法(Merge Sort)
#99999为数列1的结束数字不列入排序
list1 = [20,45,51,88,99999]
#99999为数列2的结束数字不列入排序
list2 = [98,10,23,15,99999]
list3 = []
def merge_sort():
global list1
global list2
global list3
# 先使用选择排序将两个数列排序，再进行合并
select_sort(list1, len(list1)-1)
select_sort(list2, len(list2)-1)
print('\n第1个数列的排序结果为: ', end = '')
for i in range(len(list1)-1):
print(list1[i], ' ', end = '')
print('\n第2个数列的排序结果为: ', end = '')
for i in range(len(list2)-1):
print(list2[i], ' ', end = '')
print()
for i in range(60):
print('=', end = '')
print()
My_Merge(len(list1)-1, len(list2)-1)
for i in range(60):
print('=', end = '')
print()
print('\n合并排序法的最终结果为: ', end = '')
for i in range(len(list1)+len(list2)-2):
print('%d ' % list3[i], end = '')
def select_sort(data, size):
for base in range(size-1):
small = base
for j in range(base+1, size):
if data[j] < data[small]:
small = j
data[small], data[base] = data[base], data[small]
def My_Merge(size1, size2):
global list1
global list2
global list3
index1 = 0
index2 = 0
for index3 in range(len(list1)+len(list2)-2):
if list1[index1] < list2[index2]: # 比较两个数列，数小的先存于合并后的数列
list3.append(list1[index1])
index1 += 1
print('此数字%d取自于第1个数列' % list3[index3])
else:
list3.append(list2[index2])
index2 += 1
print('此数字%d取自于第2个数列' % list3[index3])
print('目前的合并排序结果为: ', end = '')
for i in range(index3+1):
print(list3[i], ' ', end = '')
print('\n')
#主程序开始
merge_sort() #调用所定义的合并排序法函数
3.7快速排序法
import random
def inputarr(data,size):
for i in range(size):
data[i]=random.randint(1,100)
def showdata(data,size):
for i in range(size):
print('%3d' %data[i],end='')
print()
def quick(d,size,lf,rg):
#第一项键值为d[lf]
if lf<rg: #排序数列的左边与右边
lf_idx=lf+1
while d[lf_idx]<d[lf]:
if lf_idx+1 >size:
break
lf_idx +=1
rg_idx=rg
while d[rg_idx] >d[lf]:
rg_idx -=1
while lf_idx<rg_idx:
d[lf_idx],d[rg_idx]=d[rg_idx],d[lf_idx]
lf_idx +=1
while d[lf_idx]<d[lf]:
lf_idx +=1
rg_idx -=1
while d[rg_idx] >d[lf]:
rg_idx -=1
d[lf],d[rg_idx]=d[rg_idx],d[lf]
for i in range(size):
print('%3d' %d[i],end='')
print()
quick(d,size,lf,rg_idx-1) #以rg_idx为基准点分成左右两半以递归方式
quick(d,size,rg_idx+1,rg) #分别为左右两半进行排序直至完成排序
def main():
data=[0]*100
size=int(input('请输入数列的大小(100以下)：'))
inputarr (data,size)
print('您输入的原始数据是：')
showdata (data,size)
print('排序的过程如下：')
quick(data,size,0,size-1)
print('最终的排序结果为：')
showdata(data,size)
main()
3.8基数排序法
# 基数排序法，从小到大排序
import random
def inputarr(data,size):
for i in range(size):
data[i]=random.randint(0,999) #设置 data 值最大为 3 位数
def showdata(data,size):
for i in range(size):
print('%5d' %data[i],end='')
print()
def radix(data,size):
n=1 #n为基数，从个位数开始排序
while n<=100:
tmp=[[0]*100 for row in range(10)] # 设置暂存数组，[0~9位数][数据个数]，所有内容均为0
for i in range(size): # 对比所有数据
m=(data[i]//n)%10 # m为 n 位数的值，如 36 取十位数(36/10)%10=3
tmp[m][i]=data[i] # 把 data[i] 的值暂存在 tmp 中
k=0
for i in range(10):
for j in range(size):
if tmp[i][j] != 0: # 因为一开始设置 tmp ={0}，故不为 0 者即为
data[k]=tmp[i][j] # data 暂存在 tmp 中的值，把 tmp 中的值放
k+=1 # 回 data[ ]里
print('经过%3d位数排序后：' %n,end='')
showdata(data,size)
n=10*n
def main():
data=[0]*100
size=int(input('请输入数列的大小(100以下)：'))
print('您输入的原始数据是：')
inputarr (data,size)
showdata (data,size)
radix (data,size)
main()
