十大排序算法思想与 Python 实现

defselection_sort(gList):
"""选择排序    :param gList: 给定的一组序列    :return: 返回排好序的序列    """length=len(gList)
foriinrange(length-1):
flag=iforjinrange(i+1, length):
ifgList[flag] >gList[j]:
flag=j# 如果最小值的索引与最小值相对应，则无需再次交换ifflag!=i:
gList[flag], gList[i] =gList[i], gList[flag]
returngList

defbubble_sort(gList):
"""冒泡排序"""length=len(gList)
foriinrange(length):
forjinrange(i+1, length):
ifgList[i] >gList[j]:
gList[i], gList[j] =gList[j], gList[i]
returngList

definsertion_sort(gList):
"""插入排序"""length=len(gList)
foriinrange(1, length):
temp=gList[i]  # 当前的待插入的值j=i-1# 前一个值whilej>=0:
ifgList[j] >temp:
gList[j+1] =gList[j]  # 插入的动作gList[j] =temp# 插入完毕j-=1returngList

defmerge_sort(gList: list) ->list:
"""归并排序    :param gList: 给定序列    :return: 升序排列后的集合    """defmerge(left: list, right: list) ->list:
"""merge left and right        :param left: left list        :param right: right list        :return: merge reslut        """i, j=0, 0result= []
whilei<len(left) andj<len(right):
ifleft[i] <=right[j]:
result.append(left[i])
i+=1else:
result.append(right[j])
j+=1result+=left[i:]
result+=right[j:]
returnresultiflen(gList) <=1:
returngListnum=len(gList) //2left=merge_sort(gList[:num])
right=merge_sort(gList[num:])
returnmerge(left, right)
if__name__=='__main__':
gList= [3, 5, 2, 4, 1]
print("----排序前:", gList)
print("----归并排序后: ", merge_sort(gList))

# -*- coding: utf-8 -*-defquick_sort(gList, left=0, right=None) ->list:
"""快速排序    :param gList: 给定一组序列    :param left:    :param right:    :return: 升序排序后的序列    """ifrightisNone:
right=len(gList)-1ifleft>right:
returngListkey=gList[left]
low=lefthigh=rightwhileleft<right:
whileleft<rightandgList[right] >=key:
right-=1gList[left] =gList[right]
whileleft<rightandgList[left] <=key:
left+=1gList[right] =gList[left]
gList[right] =keyquick_sort(gList, low, left-1)
quick_sort(gList, left+1, high)
returngListif__name__=='__main__':
gList= [3, 5, 2, 4, 1, 6, 7]
print("----排序前:", gList)
print("----快速排序后: ", quick_sort(gList))

# -*- coding: utf-8 -*-defshell_sort(gList) ->list:
"""希尔排序"""length=len(gList)
step=2group=length//stepwhilegroup>0:
forstartPosinrange(group):
gap_insertion_sort(gList, startPos, group)
group=group//2returngListdefgap_insertion_sort(gList, start, gap):
foriinrange(start+gap, len(gList), gap):
curr_value=gList[i]
pos=iwhilepos>=gapandgList[pos-gap] >curr_value:
gList[pos] =gList[pos-gap]
pos=pos-gapgList[pos] =curr_valueif__name__=='__main__':
gList= [5, 4, 2, 1, 7, 3, 6]
print("-----yuzhou1su-----", gList)
print("-----希尔排序后:", shell_sort(gList))

defheapify(unsorted, index, heap_size):
largest=indexleft_index=2*index+1right_index=2*index+2ifleft_index<heap_sizeandunsorted[left_index] >unsorted[largest]:
largest=left_indexifright_index<heap_sizeandunsorted[right_index] >unsorted[largest]:
largest=right_indexiflargest!=index:
unsorted[largest], unsorted[index] =unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
defheap_sort(unsorted):
"""堆排序"""length=len(unsorted)
foriinrange(length//2-1, -1, -1):
heapify(unsorted, i, length)
foriinrange(length-1, 0, -1):
unsorted[0], unsorted[i] =unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
returnunsortedif__name__=='__main__':
gList= [5, 4, 2, 1, 7, 3, 6]
print("-----yuzhou1su-----", gList)
print("-----堆排序后:", heap_sort(gList))

# -*- coding: utf-8 -*-# @Author    : 宇宙之一粟defcounting_sort(unsorted):
"""计数排序    :param unsorted：给定一组序列    :return: 升序序列    """ifunsortedis []:
return []
# 根据给定序列求信息coll_len=len(unsorted)
coll_max=max(unsorted)
coll_min=min(unsorted)
# 创建计数数组counting_arr_length=coll_max+1-coll_mincounting_arr= [0] *counting_arr_length# 计数操作fornumberinunsorted:
counting_arr[number-coll_min] +=1# 将每个位置与它的前一个相加。counting_arr[i]统计出多少个# element <= i的元素foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]
# 创建保存升序结果的数组ordered= [0] *coll_lenforiinreversed(range(0, coll_len)):
ordered[counting_arr[unsorted[i] -coll_min] -1] =unsorted[i]
counting_arr[unsorted[i] -coll_min] -=1returnorderedif__name__=='__main__':
gList= [5, 4, 2, 1, 3, 6]
print("-----yuzhou1su：", gList)
print("-----计数排序后:", counting_sort(gList))

# -*- coding: utf-8 -*-# @Author    : 宇宙之一粟importmathdefinsertion_sort(collection):
foriinrange(1, len(collection)):
temp=collection[i]
index=iwhileindex>0andtemp<collection[index-1]:
collection[index] =collection[index-1]
index-=1collection[index] =tempdefbucket_sort(collection):
code=hashing(collection)
buckets= [list() for_inrange(code[1])]
foriincollection:
x=rehashing(i, code)
buck=buckets[x]
buck.append(i)
forbucketinbuckets:
insertion_sort(bucket)
ndx=0forbucinrange(len(buckets)):
forvalinbuckets[buc]:
collection[ndx] =valndx+=1returncollectiondefhashing(collection):
m=collection[0]
foriinrange(1, len(collection)):
ifm<collection[i]:
m=collection[i]
result= [m, int(math.sqrt(len(collection)))]
returnresultdefrehashing(i, code):
returnint(i/code[0] * (code[1] -1))
if__name__=='__main__':
gList= [5, 4, 2, 1, 3, 6]
print("-----yuzhou1su：", gList)
print("-----桶排序后:", bucket_sort(gList))

defradix_sort(unsorted):
radix=10max_len=Falsetmp, placement=-1, 1whilenotmax_len:
max_len=Truebuckets= [list() for_inrange(radix)]
foriinunsorted:
tmp=int(i/placement)
buckets[tmp%radix].append(i)
ifmax_lenandtmp>0:
max_len=Falsea=0forbinrange(radix):
buck=buckets[b]
foriinbuck:
unsorted[a] =ia+=1# move to next digitplacement*=radixreturnunsortedif__name__=='__main__':
gList= [5, 4, 2, 1, 3, 6]
print("-----yuzhou1su：", gList)
print("-----基数排序后:", radix_sort(gList))