python内置排序算法_吐⾎整理--史上最全排序算法Python实
现
排序算法
⼀般排序算法最常考的：快速排序和归并排序。这两个算法体现了分治算法的核⼼观点，⽽且还有很多出题的可能。
1. 常见的排序算法
排序算法很多，除了能写出常见排序算法的代码，还需要了解各种排序的时空复杂度、稳定性、使⽤场景、区别等。
1.1 选择排序
1.1.1 思想
对于给定的⼀组序列，第⼀轮⽐较选择最⼩(或最⼤)的值，然后将该值与索引第⼀个进⾏交换；接着对不包括第⼀个确定的值进⾏第⼆次⽐较，选择第⼆个记录与索引第⼆个位置进⾏交换，重复到只剩最后⼀个记录位置。
案例：幼⼉园排队，⽼师先让站成⼀队，带第⼀个⼩朋友依此跟其他⼩朋友逐个⽐较，选出个⼦最矮的，然后依此进⾏
1.1.2 实现
def selection_sort(gList):
"""选择排序
:param gList: 给定的⼀组序列
:return: 返回排好序的序列
"""
length = len(gList)
for i in range(length - 1):
flag = i
for j in range(i+1, length):
if gList[flag] > gList[j]:
flag = j
# 如果最⼩值的索引与最⼩值相对应，则⽆需再次交换
if flag != i:
gList[flag], gList[i] = gList[i], gList[flag]
return gList
1.1.3 选择排序分析
时间复杂度：最好、最坏、平均的时间复杂度都为
空间复杂度:
稳定性：不稳定
1.2 冒泡排序
1.2.1 思想
对于给定的⼀组序列含n个元素，从第⼀个开始对相邻的两个记录进⾏⽐较，当前⾯的记录⼤于后⾯的记录，交换其位置，进⾏⼀轮⽐较和换位之后，最⼤记录在第n个位置；然后对前(n-1)个记录进⾏第⼆轮⽐较；重复该过程直到进⾏⽐较的记录只剩下⼀个时为⽌。
案例：冒泡，像⽓泡⼀样往上升
1.2.2 实现
def bubble_sort(gList):
"""冒泡排序"""
length = len(gList)
for i in range(length):
for j in range(i+1, length):
if gList[i] > gList[j]:
gList[i], gList[j] = gList[j], gList[i]
return gList
1.2.3 冒泡排序分析
时间复杂度：
最好时间复杂度：
最坏时间复杂度:
平均时间复杂度:
空间复杂度:
稳定性：稳定的排序
1.3 插⼊排序
1.3.1 思想
对于给定的⼀组记录，初始时假设第⼀个记录⾃成⼀个有序序列，其余的记录为⽆序序列；接着从第⼆个记录开始，按照记录的⼤⼩依次将当前处理的记录插⼊到其之前的有序序列中，直⾄最后⼀个记录插⼊到有序序列中为⽌。
案例：抓扑克牌
1.3.2 实现
def insertion_sort(gList):
"""插⼊排序"""
length = len(gList)
for i in range(1, length):
temp = gList[i] # 当前的待插⼊的值
j = i - 1 # 前⼀个值
while j >= 0:
if gList[j] > temp:
gList[j+1] = gList[j] # 插⼊的动作
gList[j] = temp # 插⼊完毕
j -= 1
return gList
1.3.3 插⼊排序分析
时间复杂度
最好时间复杂度：
最坏时间复杂度:
平均时间复杂度:
空间复杂度:
稳定性：稳定的排序
1.4 归并排序 ☆☆★
1.4.1 思想
利⽤递归与分治技术将数据序列划分成为越来越⼩的半⼦表，再对半⼦表排序，最后再⽤递归步骤将排好序的半⼦表合并成为越来越⼤的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。
给定⼀组序列含n个元素，⾸先将每两个相邻的长度为1的⼦序列进⾏归并，得到n/2(向上取整)个长度为2或1的有序⼦序列，再将其两两归并，反复执⾏此过程，直到得到⼀个有序序列为⽌。
1.4.2 实现
def merge_sort(gList: list) -> list:
"""归并排序
:param gList: 给定序列
:
return: 升序排列后的集合
"""
def merge(left: list, right: list) -> list:
"""merge left and right
:param left: left list
:param right: right list
:return: merge reslut
"""
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
if len(gList) <= 1:
return gList
num = len(gList) // 2
left = merge_sort(gList[:num])
right = merge_sort(gList[num:])
return merge(left, right)
if __name__ == '__main__':
gList = [3, 5, 2, 4, 1]
print("----排序前:", gList)
print("----归并排序后: ", merge_sort(gList))
1.4.3 归并排序分析
时间复杂度: 最好、最坏和平均情况
空间复杂度:
稳定性：稳定
题⽬：100个有序数列如何合成⼀个⼤数组？
1.5 快速排序☆★★
1.5.1 思想
⾼效的排序算法，它采⽤“分⽽治之”的思想，把⼤的拆分为⼩的，⼩的再拆分为更⼩的。其原理是：对于⼀组给定的记录，通过⼀趟排序后，将原序列分为两部分，其中前部分的所有记录均⽐后部分的所有记录⼩，然后再依次对前后两部分的记录进⾏快速排序，递归该过程，直到序列中的所有记录均有序为⽌。
1.5.2 实现
# -*- coding: utf-8 -*-
def quick_sort(gList, left=0, right=None) -> list:
"""快速排序
:
param gList: 给定⼀组序列
:param left:
:param right:
:return: 升序排序后的序列
"""
if right is None:
right = len(gList)-1
if left > right:
return gList
key = gList[left]
low = left
high = right
while left < right:
while left < right and gList[right] >= key: right -= 1
菜鸟教程python函数
gList[left] = gList[right]
while left < right and gList[left] <= key: left += 1
gList[right] = gList[left]
gList[right] = key
quick_sort(gList, low, left-1)
quick_sort(gList, left+1, high)
return gList
if __name__ == '__main__':
gList = [3, 5, 2, 4, 1, 6, 7]
print("----排序前:", gList)
print("----快速排序后: ", quick_sort(gList)) 1.5.3 快速排序分析
时间复杂度：
最坏时间复杂度：
最好时间复杂度：
平均时间复杂度:
空间复杂度：
稳定性：不稳定

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。