语言就是一门心与心交流的桥梁。有时候，往往更多的成就，或许就是你语言艺术上的造诣！
再次强调：出现概率非常高、面试考的最多的 面试题*****（必须掌握）
排序算法:
选择、冒泡、选择、堆、插入...
1、选择排序
排序算法的逻辑非常简单，首先搜索整个列表，找到最小项的位置，如果该位置不是列表的第1项，就交换这两个位置的元素。然后从列表的第2个元素开始，重复上述过程，直到算法达到整个过程的最后一个位置，图形解释如下
简单排序算法——一元选择排序
lst=[1,9,8,5,6,7,4,3,2] # 9;
n=len(lst)
count_swap=0
count_iter=0
for i in range(9): # 0,8 ;
maxindex=i #最大值索引；
m=lst[i] #最大值；
for j in range(i+1,8):
count_iter+=1
if lst[j]>lst[maxindex]: #找出中间的最大值交换
maxindex=j
if i!=maxindex: # 不判断也可以；有时候会多几下；
lst[i],lst[maxindex]=lst[maxindex],lst[i]
count_swap+=1
print(lst,count_swap,count_iter)
------------------------------------------
[9, 8, 7, 6, 5, 4, 3, 1, 2] 6 28
总结：
1.先根据逻辑写框架：
2.思路：每一趟 选出max固定在左端，剩下的值再来一趟找最大值，继续交换固定；
3.记录每一趟的极值索引、值，一趟一趟的交换；一次不能少，一次也不多；
4.再次强调：出现概率非常高的 面试题*****（必须掌握）
冒泡排序
冒泡排序从列表的开头处开始，逐个比较一对数据项，如果顺序不对就交换两项位置，直到移动到列表的末尾。这个过程的效果就是将最大的项以冒泡的方式排到算法的末尾。然后算法从列表开头到倒数第二项重复这一过程，依次类推，图形解释如下。
冒泡排序算法
# 简单选择排序——冒泡法 往右边排序；
lst=[1,9,8,5,6,7,4,3,2]
n=len(lst)
for j in range(1,n):
for i in range(n-1):
if lst[i]>lst[i+1]:
lst[i],lst[i+1]=lst[i+1],lst[i]
lst
-----
[1, 2, 3, 4, 5, 6, 7, 8, 9]
2. 二元选择排序优化
方法1：两头同时找max、index；（渐少迭代的次数）
m_list=[[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[9,8,7,6,5,4,3,2,1]]
nums=m_list[1]
length=len(nums)
print(nums)
count_swap=0
count_iter=0
#二元选择排序；
for i in range(length//2):
maxindex=i
minindex=-i-1
minorigin=minindex
for j in range(i+1,length-i):
count_iter+=1
if nums[maxindex]<nums[j]:
maxindex=j
if nums[minindex]>nums[-j-1]:
minindex=-j-1
if i !=maxindex: ##索引不同就交换
nums[i],nums[maxindex]=nums[maxindex],nums[i]
if i==minindex or i==length+minindex:
minindex=maxindex
if minorigin !=minindex: #索引不同就交换
nums[minorigin],nums[minindex]=nums[minindex],nums[minorigin]
count_swap+=1
print(nums,count_swap,count_iter)
--------------------------------------------------------------------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1] 4 20
方法2：如果一趟的最大值和最小值相等； 说明比较的序列元素全部相等；
m_list=[[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[9,8,7,6,5,4,3,2,1]]
nums=m_list[1]
length=len(nums)
print(nums)
count_swap=0
count_iter=0
#二元选择排序；
for i in range(length//2):
maxindex=i
minindex=-i-1
minorigin=minindex
for j in range(i+1,length-i):
count_iter+=1
if nums[maxindex]<nums[j]: # 算最小值；
maxindex=j
if nums[minindex]>nums[-j-1]: # 算最大值
minindex=-j-1
if nums[maxindex]==nums[minindex]: # 如果max=min;就直接跳出循环；
break
if i !=maxindex: ##索引不同就交换
nums[i],nums[maxindex]=nums[maxindex],nums[i]
if i==minindex or i==length+minindex:
minindex=maxindex
if minorigin !=minindex: #索引不同就交换
nums[minorigin],nums[minindex]=nums[minindex],nums[minorigin]
count_swap+=1
print(nums,count_swap,count_iter)
简单选择排序总结：
1.简单选择排序需要数据一轮轮的比较，并发现每一轮的极值；
2.没有办法知道当前是否已经达到排序要求，但是可以知道极值是否再目标索引位置上；
3.遍历次数1，...,n-1 之和n(n-1)/2
4.时间复杂度O(n2)
5.渐少交换次数，提高了效率，性能略优于冒泡法（冒泡法一直交换）；
网友评论