开发者学堂课程【Python 开发基础入门：Python 选择排序及二元选择排序优化】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/556/detail/7656
Python 选择排序及二元选择排序优化
目录：
一、简单选择排序
二、二元排序
三、总结
一、简单选择排序
1、简单选择排序
2、属于选择排序
排序一定存在比较问题，但是有比较不能决定它是什么算法。
3、两两比较大小（一定要做），找出极值(极大值或极小值）被放置在固定的位置，这个固定位置一般指的是某一端，也是最大值。
一定要做的事，就是做完这个两两比较大小之后，要找出一个极值，因为极大值极小值之后找到这个机制之后，把它放在一个固定的位置。这是固定位置，指的是某一端，有12345 共5个数字，必须从头走到尾才知道是最大的。
所以直接把5 只要放到第一个的地方去，现在把头部要交换到尾部上去，那也就是说每次决定一个极值之后，下面要做的事情就是找到那两个位置之后交换就完了。但是刚才是5交换的首位，那剩下那几个数谁是最大？
那也就说12345，已经知道了一次只能固定一个数，一次也只能知道谁是这一次里的最大值。然后下一次继续，说这里面1234了，但是那个1已经退到队尾了，还得2341，依次比较一下，才知道谁最大，然后这下应该是现在5到前面来了因此比较234才发现是最大4就要2要换一下，这些变成什么54321。
对计算机来说，他还是不知道。所以每一趟都要走一遍，唯一要优化的时候，发现它要换个位置，正好是它自己的位置不用换了。
换了也白换，这个是要判断的地方，但是这个这一点对整个来说不是什么太大的问题。
4、结果分为升序和降序排列
5、降序
6、n个数从左至右，索引从0开始到n-1，两两依次比较，记录大值索引，此轮所有数比较完毕，将大数和索引0数交换，如果大数就是索引1，不交换。第二轮，从1开始比较，找到最大值，将它和索引1位置交换，如果它就在索引1位置则不交换。依次类推，每次左边都会固定下一个大数。
7、升序
8、和降序相反
123456789九个数字，为了对换匹配，这次把大头9放到最左边来看，第一趟初始的时候是198567432，然后第一趟的循环是9在里面要找到一个极值，9这个位置是所以最大，索引是最大的，此时得找个极值的索引，这个极大值的索引是被记录的。
之后考虑跟谁换，是把大头放最左边的，当然也可以找最小值，这个就是看想升序还是降序的问题。第二趟，它的索引为1，这个时候18比较一下最大值是8，然后依次向后找，依次比较。如果第二趟当前要换的这个位置来找1，索引为1，然后找所谓的max，index最大，索引最大，所以是找到它在这个位置应该是2，一路找下去，这个最大索引是不动了，就应该是这个位置。
现在索引为2，待插入的索引位置是1，发现它俩不一样就交换，交换索引对应的值后，记录下当前的最大index，此时就会刷新，看这绿色的告诉，每次谁被交换走了，红色是告诉谁固定下来，黑色告诉连动都没动。
也就说在每一趟要记住最大，找到这个时候，换后再找，剩余里面找一个最大，所以最大值所在索引，然后进行交换。
1）
lst =[ 1,9,8,5,6,7,4,3,2] #[9，8，7]
length = len (lst)
For i in range ( length) :（（1）按照i去迭代一个个值）再去记住索引，如果大于0，下一轮等于j
x= lst[i] # 1和其它数比较，找出maxindex
maxindex = -1
for j in range(i) : # j 1,2,...
If lst [j]>lst [maxindex]：（比较索引的大小）
maxindex=j
if i !=maxindex:l
lst[i], lst [maxindex] = lst[maxindex], lst[i]
print(lst)
[9，8，7，6，5，4，3，2，1]
还是一样选择排序还得比较大小，那做完两两比较大小之后，要找出一个极值，因为说极大值极小值的找到当下的极值之后，极大值或者极小值找到这个极值之后，把它放在一个固定的位置。
固定位置指的是某一端，必须从头走到尾，猜测最大的，在尾部，把原来头部比较交换到尾部上去，每一趟下来决定一个极值之后，下面要做的事情就是找到那两个位置之后是以交换就完了。
请问剩下那几个数里面，知道谁是最大数吗，因为自己是最大自己知道的，但是5之外的，，用这么简单的12345，一次只能固定一个，也只能知道谁是这一套里面最大值，然后下一趟继续。说的是里面个1234了，要判断的地方。
2）
lst =[1,9,8,5,6,7,4,3,2]
length = len (lst)
for i in range (length) :
和其它数比较，找出maxindex找出最大值索引
x= lst[i] #1和其它数比较，找出
maxindexmaxindex = i每一趟都不知道最大值索引是谁，-1可以但不合适，所以这个地方就是i，i增加，这个值就变成一。
因为只有一个数，所以只有我自己，下面的数要看比较关系，下面的数如果找最大值
for j in range (i) :
pass
假设前面都是固定下来
lst =[ 1,9,8,5,6,7,4,3,2] #[ 9,8 ,7]
length =len (lst)
for i in range (length) :这里先大概写个范围，它不影响算法设计
x = lst[i] #1maxindex
maxindex = i
for j in range (i+1,length) : #j 1,2,....（j最大值就是length-1）
if lst[j]> lst [maxindex] :
i在j循环里面一直不动，如果大于maxindex就大于i，因为所有数都大于1，这块肯定要比较，所以应该应该和maxindex比较，此时才有用，关键在后面这趟走完后，就知道max是谁，如果说i不等于，假设98754321，第一趟max就是第一个9，所以换就没必要，所以list i在不相等才有换的价值。
maxindex = j
关键是下一轮再进来比较大小的时候，
if i != maxindex :（这个时候是一个很简单的判断）
lst[i], lst [maxindex] = lst [maxindex], lst [i]
Print（lst））
按照i去迭代的那个值，
按这个逻辑，一直走下去，走到最后，如果这块不出现任何问题的话，就没什么太大问题，这个不能超过最大值length，因为最后一个值，还得跟这个所谓的最大所对应。
一个都不能少，而且说写逻辑的过程中，觉得这很难判断，就往后丢，先不理它，先把这些基本组干的这个基本的代码都写完，写完之后，然后还有边界问题在思考，之后在判断会不会超，如果没办法判断就直接打印出来，之后进行交换，print检验一下。
就是每一趟找到极值所对应的索引与你最左边固定的那个最左端的索引之间进行交换。一趟都不能少，就是走发完九位数的。
技巧：确定最大值的索引，并确定其位置。
3）
nums = m_list[1]
length = len (nums)
print (nums)
count_swap = o
countiter =0
for i in range ( length) :
maxindex = i
for jin range (i + 1, length) :
count_iter += 1
if nums [maxindex] < nums[j]:
maxindex = j
if i != maxindex:
tmp =nums [i]
nums [i]= nums [maxindex]
nums [maxindex] = tmp
count_swap += 1
print (nums,count__swap,count_iter)
比较迭代次数，交换次数，大大减少交换次数，大于就交换，并减少了交换步骤，交换的代价较高：
元素需要挪动，极限情况下，数字挪动的交换过程要确定极值。
九个数字固定了八回，每一趟结束才能交换，确定极值，如果没发现
交换不了。
这是必须掌握的基本功，用来比较一些它的次数，只要有大于的情况就交换。
新的要求：
一趟里比最大值和最小值都找到，找最小值的代码和最大值，走完一趟后最大值，1和9的位置可以记录，一到最右边，9到最左边，减少了躺数，可以比较出，这个就是二元选择排序，以此固定两个值。
二、二元排序
简单选择排序代码实现(二）
口优化实现
可以大大减小了迭代次数，经过测试，讲次数折半，
二元选择排序
同时固定左边最大值和右边最小值
优点:
减少迭代元素的次数
length//2整除，通过几次运算就可以发现规律
2、由于使用了负索引，所以条件中要增加
i == length + minindex
如何进行优化
#二元选择排序
for i in range ( length //2):（这里是整除2 的数字）
maxindex = i 假设谁是最大最小值，只要思想对就行，记录一个值当做最大值，记录一个值认为那边存了最小值，分别记录下来，在记录一个原始的地方，原始的最小值，一个从左边一个从右边走，
minindex = -i - 1记录所谓的最小值索引，每一次都可以减一个数跟i相关，i在左边加，每次比较时越来越短，可以平移索引等等。
minorigin = minindex
for j in range (i + 1,length - i) : #每次左右都要少比较一个
count_iter += 1
if nums [maxindex]
如果最小值大于负索引，就要发现最小值的索引。
maxindex = j
if nums [minindex] > nums[-j - 1]∶当向左边找，最小值索引都比比较的大，所以索引要刷新，
minindex = -j- 1
# print (maxindex ,minindex)
if i != maxindex: 当i是最左端，minindex被移动
最大值索引如果不等于起始的i就要交换并记录交换次数。如果这趟走完，最小值索引记录是-9，最大索引记录是1，然后如果先做最大值交换，当把9到1时，9已结移动到最左边
tmp = nums [i]
nums [i]= nums [maxindex]
nums [maxindex] = tmp
count_swap += 1
#如果最小值被交换过，要更新索引
if i == minindex or i == length + minindex:当i最左端时，manindex做完交换后，9到最左端，最小值是-9，在移动，所以当写的不等于，就一旦进来就会发生交换，注意换的是谁。
如果正索引记录，i=0或者等于length最小索引的副索引，说明最大值与i一定发生交换，所以把0索引的数字与1索引交换，而且交换的是最小值的索引，所以最小值已经迁移到最大值那里，
minindex = maxindex（才是存最小的数）
if minorigin != minindex :
（这里在做一个判断，相同就交换，可能影响最小索引，所以要最小索引修正法）
tmp = nums [minorigin]
nums [minorigin] = nums [minindex]
nums [minindex] = tmp
count_swap += 1
print (nums,count_swap,count_iter)
有三种：
同时最大最小，或者最大值或者最小值，虽然对于记录一个值，把它当做是最大值。
然后把最右端，从负一开始，认为那边存了个最小值。对于这个来说，认为这是那个最大值，这东西是个最小值，记住一个所谓的原始的地方。
原始的最小，故意分两头走了，一个从左边走，一个右边走。
但目前为止来说就是在刚才那个基础上加了一行。就是最小值，每一次都得减一个数，比较长度两头固定。这个做其它测试的知道了，每次左右就要少，就是找出规律，这是我刚才的谁大谁小的问题。
1.改进实现
如果一轮比较后,极大值、极小值的值相等，说明比较的序列元素全部相等
关键：先交换谁，会影响后面一个的交换。
找到最大值，可以找到对应的最小值，并找到对应的索引。
如果极大极小值找到并相同就不用交换直接break即可。
2. 改进实现
观察交换次数可以发现某些特殊数据，所以判断一下即可
如果最大值索引与最小值索引对应的值一致时，说明了在某一趟内它们相同时，这一趟里剩下的数全部相等。
像311113，第一趟与第二趟，此时有没有必要再向后比较，剩下的一它们的值相等，如果不用二元是得不到这个结论，所以用一元是得不到这个结论的如果在i循环里相等就直接结束必须写在j循环之外，如果找到的值完全相同，中间也一样直接break。
在二元选择排序上来做得[1,1: 1,1,1,1,1,1,2]这种情况，找到的最小值索引是-2，最大值索引8，上面的代码会交换2次,最小值两个1交换是无用功，所以,增加一个判断（值是否相等） （在二元选择排序时，才做这个）
31111111，如果假设1是最小值所以是最小值3最大值
13111111 最大需要换，最小不用，
1111113 最小值索引记录是-2与1交换 特意置换特例3
Max=5 min=-2
111113
311111
此时直接break
特意构造一些特例，观察它的规律。观察它的特殊数列，发现可以少交换一些
当最小值交换的目标位置相等就没有必要交换，此时需要加一个判断。
三、简单选择排序总结
1.简单选择排序需要数据一轮轮比较,并在每一轮中发现极值
是最经常用的选择排序之一
这些都是最常用的选择排序，实际上因为它的效率的问题，也未必都用，其它的变形的一些方法，算法相对来说都是比较。
总的来说是一轮轮的比较，并在每一轮中发现某值。当然简单来讲，可以发现某一个极大值或者小于，但是也可以一次性直接发现最大值最小值，除了二元。
2. 没有办法知道当前轮是否已经达到排序要求，但是可以知道极值是否在目标索引位置上
除了二元只能解决等值的一些特例，非等值解决不了，对于一个特别不一样的也没有办法，必须通过一轮轮的排序。
3. 遍历次数1,.,n-1之和n(n-1)/2
4.时间复杂度O(n2)
5.减少了交换次数，提高了效率，性能略好于冒泡法
注意：
记住简单选择排序的概念，二元的因人而异，解决一元的极大极小。
时间复杂度必须记住，加几个变量可以忽略不计。
一般来说选择排序略高于交换排序。
