python----列表排序（由⼩到⼤）-python--8⼤排序（原理+代
码）
常⽤的排序⽅法：冒泡排序、选择排序、插⼊排序、快速排序、堆排序、归并排序
冒泡排序(Bubble Sort)：
⽐较相邻的元素。如果第⼀个⽐第⼆个⼤（升序），就交换他们两个。
对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。这步做完后，最后的元素会是最⼤的数。
针对所有的元素重复以上的步骤，除了最后⼀个。
持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较
defbubble_sort(alist):
n=len(alist)for i in range(n-1):for j in range(n-1-i):if alist[j] > alist[j+1]:
alist[j],alist[j+1] = alist[j+1],alist[j]if __name__ == "__main__":
alist= [1,2,4,9,5,6,8]
bubble_sort(alist)print(alist)
最优时间复杂度：O(n)
最坏时间复杂度：O(n2)
空间复杂度：o(1)
稳定性：稳定
选择排序(Selection sort)：
⾸先在未排序序列中到最⼩（⼤）元素，存放到排序序列的起始位置
然后，再从剩余未排序元素中继续寻最⼩（⼤）元素，
然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
defselect_sort(alist):
n=len(alist)for i in range(n-1):
min_index=ifor j in range(i+1,n): #遍历⽆序序列
#判断当前数值是否⼩于最⼩值，如果⼩于，则记录其索引
if alist[j]
min_index=j#判断min_index索引是否相同，不相同，做数值交换
if i !=min_index:
alist[i],alist[min_index]=alist[min_index],alist[i]if __name__ == "__main__":
alist= [12,34,56,78,90,87,65,43,21]
select_sort(alist)print(alist)
最优时间复杂度：O(n*log2n)
快速排序python实现
最坏时间复杂度：O(n2)
空间复杂度：O(log2n)~o(n)
稳定性：不稳定
插⼊排序：
开始假定列表⾥下标为0的元素是最⼩，在后⾯还未排序的数据⾥依次选取数据在前⾯有序区域⾥做⽐较并放在正确的位置，就像我们在玩扑克牌的时候依次把扑克牌有顺序的拜访
importrandomdefinsert_sort(li):for i in range(1, len(li)):
tmp= li[i] #tmp是⽆序区取出的⼀个数
j = i - 1 #li[j]是有序区最⼤的那个数
while j >= 0 and li[j] >tmp:#li[j]是有序区最⼤的数，tmp是⽆序区取出的⼀个数，tmp从有序区最⼤的那个数开始⽐
#⼩就调换位置，直到到有序区中值不⼤于tmp的结束
li[j+1]=li[j] #将有序区最右边的数向右移⼀个位置
j = j - 1li[j+ 1] = tmp #将tmp放到以前有序区最⼤数的位置，再依次与前⼀个数⽐较
data = list(range(100))
random.shuffle(data)#将有序列表打乱
insert_sort(data)print(data)
时间复杂度：o(n2)
空间复杂度：o(1)
稳定性：稳定
快速排序：
随机选取⼀个值，挨个跟后⾯的数值作⽐较，⽐该数值⼩的将放在左列表中，反之则放在右列表，返回形式为：左列表+[随机值]+右列表，左右列表使⽤递归的⽅式继续进⾏排序。
defquick(list):if len(list) < 2:returnlist
tmp= list[0] #临时变量 可以取随机值
left = [x for x in list[1:] if x <= tmp] #左列表
right = [x for x in list[1:] if x > tmp] #右列表
return quick(left) + [tmp] +quick(right)
li= [4,3,7,5,8,2]print(quick(li))
时间复杂度：O(nlog₂n)
空间复杂度：O(nlog₂n)
稳定性：不稳定
堆排：
堆总是⼀棵完全⼆叉树，构造堆、调整堆
构造堆：每个根节点总是⼤于等于其⼦节点，从最⼩堆依次往上做调整
调整堆：将堆顶最⼤元素出堆，将最后⼀个元素放⾄堆顶，然后⽤构造堆的⽅法进⾏调整，此过程循环往复，将数据从⼤到⼩的顺序依次出堆，直⾄此堆变空。
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
归并排序：
将列表越分越⼩，直⾄分成⼀个元素，⼀个元素是有效的，然后将两个有序的列表合并。
时间复杂度：O(nlog₂n)
空间复杂度：O(1)
稳定性：稳定

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