【1.选择排序】
有一个n位的数据。
排序方法：
1.从第一位开始与后面位数进行大小比较，如果选取的第n位>所比较位数，则这两位数交换。用新得到的这个第n位继续把右侧的所有位数比较完毕，即结束一轮。
2.第（n-1）轮结束后，排序完成。
※解析：
eg.
原始数据： |6 2 8 5 1
第一轮： 1 |2 8 5 6
第二轮： 1 2 |8 5 6
第三轮： 1 2 5 |8 6
第四轮： 1 2 5 6 |8
第一轮：最左的6与2比，2更小
接下来用这个2与后面几位比：
6 2 8 5 1（原始）
2 6 8 5 1（6与2比）
2 6 8 5 1（2与8比）
2 6 8 5 1（2与5比）
1 6 8 5 2（2与1比）
第二轮：用第2位（6）与后面位数比较
1 6 8 5 2（第一轮原始）
1 6 8 5 2（6与8比）
1 5 8 6 2（6与5比）
1 2 8 6 5（5与2比）
第三轮：用第3位（8）与后面位数比较
1 2 8 6 5（第二轮原始）
1 2 6 8 5（8和6比）
1 2 5 8 6（6和5比）
第四轮：用第4位（8）与后面位数比较
1 2 5 8 6（第三轮原始）
1 2 5 6 8（8和6比）
#coding:utf-8
def sel(a):
for i in range(len(a)-1):#控制轮数
for j in range(i+1,len(a)):#从第n位一直到最后一位（eg.第一轮中：从第2位到最后一位）
if a[i]>a[j]:
#互换a[i]和a[j]
t=a[i]
a[i]=a[j]
a[j]=t
return a
'''
【2.冒泡排序】
有一个n位数的数据。
1.比较相邻的两个元素，若选取的两个相邻元素中，原来靠左侧的元素>原来靠右侧的元素，则交换两数位置。
2.需要进行n-1轮交换，每轮交换进行n-1次比较（换or不换位置）
※解释：
eg.
原始数据： 6 2 8 5 1
第一轮： 2 6 5 1 |8
第二轮： 2 5 1 |6 8
第三轮： 2 1 |5 6 8
第四轮： 1 |2 5 6 8
第一轮：
6 2 8 5 1（原始）
2 6 8 5 1（第1-2位：6 2交换）
2 6 8 5 1（第2-3位：6 8不交换）
2 6 5 8 1（第3-4位：8 5交换）
2 6 5 1 8（第4-5位：8 1交换）
第二轮：
2 6 5 1 8（第一轮原始）
2 6 5 1 8（第1-2位：2 6不交换）
2 5 6 1 8（第2-3位：6 5交换）
2 5 1 6 8（第3-4位：6 1交换）
- 2 5 1 6 8（第4-5位：6 8不交换）*
第三轮：
2 5 1 6 8（第二轮原始）
2 5 1 6 8（第1-2位：2 5不交换）
2 1 5 6 8（第2-3位：1 5交换）
- 2 1 5 6 8（第3-4位：5 6不交换）*
- 2 1 5 6 8（第4-5位：6 8不交换）*
第四轮：
2 1 5 6 8（第三轮原始）
1 2 5 6 8（第1-2位：2 1交换）
- 1 2 5 6 8（第2-3位：2 5不交换）*
- 1 2 5 6 8（第3-4位：5 6不交换）*
- 1 2 5 6 8（第4-5位：6 8不交换）*
比较了5-1=4轮，排序结束。
def bub(a):
for m in range(len(a)-1):
for n in range(len(a)-m-1):#一轮过后，最后一个数不需要比较
if a[n]>a[n+1]:
#互换a[i]和a[j]
t=a[n]
a[n]=a[n+1]
a[n+1]=t
return a
【3.插入排序法】
有一个n位数的数据。
从左边第2位开始，将该选取出的数字与左边每一位进行比较（习惯是从近往远比，比如我选的是第3位，我先用第3位与第2位比，再用这个*原来选取的第3位与第1位比），如果选取的数比左侧的比较数要小，则交换两个数字。
*：特别注意是原来选取的第3位，因为比较后数据可能发生交换。选了哪个数字，就用这个数字比较，直到比完该数原来左侧的所有位数。
※解释：
eg.
原始数据： 6| 2 8 5 1
第一轮： 2 6| 8 5 1
第二轮： 2 6 8| 5 1
第三轮： 2 5 6 8| 1
第四轮： 1 2 5 6 8|
*习惯是选一个数，然后与左边的每一位比较。（所以一开始选的是第2位，因为第1位左边没有数字了）
第一轮：
6 2 8 5 1（原始，选第2位的2）
2 6 8 5 1（2 6交换）
第二轮：
2 6 8 5 1（第一轮原始，选第3位的8）
2 6 8 5 1（8 6不交换）
2 6 8 5 1（8 2不交换）
第三轮：
2 6 8 5 1（第二轮原始，选第4位的5）
2 6 5 8 1（5 8交换）
2 5 6 8 1（5 6交换）
2 5 6 8 1（5 2不交换）
第四轮：
2 5 6 8 1（第三轮原始，选第5位的1）
2 5 6 1 8（1 8交换）
2 5 1 6 8（1 6交换）
2 1 5 6 8（1 5交换）
1 2 5 6 8（1 2交换）
def ins(a):
for i in range(1,len(a)):
t=a[i]
j=i-1
while(j>=0 and a[j]>t):
a[j+1]=a[j]
a[j]=t
j=j-1
return a
【4.快速排序法】
有一个n位数的数据。
从中间（或中间附近or开头or结尾，习惯是在中间）选取一个数，作为中间数。
将该中间数从原来的数据中剔除，再将剩下的数据分为两组——left组和right组。
其中left组存比中间数小的数据，right组存比中间数大的数据（注意，分组时不会影响各组中数据的顺序）
eg：6 2 8 5 9，我选8为中间数，剩下的 6 2 5 9分为两组也是6 2 5和9，顺序是不会变的。
※解释：
eg.
原始数据： |6| 2 8 5 1
第一轮： |1| 2 5 | 6 |8|
第二轮： 1 ||2| 5 | 6 | 8
第三轮： 1 | 2 | 5 | 6 | 8
6 2 8 5 1（原始数据，选中间或附近的一位（其实也可以选开头或结尾），此时选8）
剩余组成：6 2 5 1
将比选出的数（8）小的放进left组：6 2 5 1
比选出的数（8）大的放进right组：right=（空）【此时确定8放在最右】
再在left组（6 2 5 1）中选中间一位数（此时选2）
新的left：1
right：6 5【此时left+中间+right排序：1（left） 2（中间） 6 5（right）】
再在right组（6 5）选一位（6）
新的left：5【此时确定5在最左】
right：（空）【此时确定left+中间+right排序：5（left） 6（中间）】
综合以上，得出最终排序： 1 2 5 6 8
def fast_sort(a):
#找基准数
if(len(a)>=2):
mid=a[len(a)//2]#可以是第一个，也可以是最后一个
left,right=[],[]#定义基准数左右两边的列表
a.remove(mid)
for num in a:
if num>=mid:
right.append(num)
else:
left.append(num)
return fast_sort(left)+[mid]+fast(right)
else:
return a
