排序的分类：
冒泡排序，快速排序
参考：
知识部分
一、排序介绍
1、内排序和外排序
内排序：排序时，待排序的所有记录都在内存中
外排序：排序时，使用到了外部存储
2、排序按操作划分
插入排序 复杂度：O(n^2)
交换排序 复杂度：O(n^2)
选择排序 复杂度：O(n^2)
归并排序
交换排序和选择排序的复杂度相同，是因为它们的比较次数一样多，但是选择排序比交换排序中的冒泡排序时间短，是因为它的交换次数少得多，而CPU处理交换的速度比处理比较的速度慢。
3、以算法复杂度分为
简单算法：冒泡排序 、简单选择排序 和直接插入排序
改进算法：希尔排序 、堆排序 、归并排序 和快速排序
重点是这七种经典排序算法
4、排序的稳定性
如果原序列之中有两个相同的元素，例如A[i] = A[j]，它们在排序前的序号分别是i和j，且i<j，如果排序完成之后，i<j依旧成立，那么说明排序是稳定。
二、冒泡排序
示例：
Copy 4, 3, 2, 1
第一次： 4, 3, 1, 2 -> 4,1,3,2 -> 1,4,3,2
... 虽然可以用python写出冒泡排序的算法，但感觉没有什么意义。因为只要你能制定出比较两者“大小”的方式，就可以使用sort(list，key=func)来实现。说起来，我倒是对python中原有的排序机理产生了兴趣。因为它涉及到了合并排序和插入排序，那就先看一下这两种排序。
三、直接插入排序
原文的代码太奇怪了，我自己写一个吧
Copy def insert_sort(lis):
length = len(lis)
if not length:
return []
result = [lis[0]]
for i in range(1, length):
for j in range(len(result)):
if lis[i] < result[j]:
result.insert(j, lis[i])
break
if j == len(result)-1:
result.insert(j+1, lis[i])
return result 四、归并排序
感觉这个名字起得不好啊，是不是分并排序更好些？原文代码一大段，看得又头疼又无聊，所以下面还是我自己写的
Copy def merge_sort(lis):
# 分
length = len(lis)
# 长度为2或1时的排序
if length == 1:
return lis
elif length == 2:
return lis if lis[0] < lis[1] else lis[::-1]
if length % 2 == 0:
mid = length // 2
else:
mid = (length - 1) // 2
a = merge_sort(lis[0:mid])
b = merge_sort(lis[mid:])
# 合并
i = 0
j = 0
new = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
new.append(a[i])
i += 1
else:
new.append(b[j])
j += 1
new += a[i:] + b[j:]
return new 简单来说就是，使用迭代的方式先拆后合并。但是关于拆分的最小单位如何确定效率才比较高，这点我还不清楚。
三、Timsort
Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序，现在Java SE7和Android也采用Timsort算法对数组排序。
习题部分
一、数组（列表）排序
1、对于数字排序，用list.sort()方法或者sorted方法都可以，如果非要实现的话，基本与字母排序一样
2、字母排序
Copy ['-', '-', '+', '+', '+','-', '+','-', '+','-','-'] 网上看到的一种解答是
Copy def StringSort(data):
startindex = 0
endindex = 0
count = len(data)
while startindex + endindex < count:
if data[startindex] == '-':
data[startindex], data[count - endindex - 1] = data[count - endindex - 1], data[startindex]
endindex += 1
else:
startindex += 1
return data
data = ['-', '-', '+', '+', '+','-', '+','-', '+','-','-']
print(StringSort(data)) 点评：我觉得毫无意义，数字排序不用说了，内置方法几乎可以帮你完成所有的排序方式包括自定义，而这种字母排序，我实在不能理解其中的意义。假设只有两个符号，一种排前面，一种排后面，完全可以使用以下方法
Copy def StringSort(data):
count_1 = data.count('+')
count_2 = data.count('-')
result = ['+' for i in range(count_1)] + ['-' for j in range(count_2)]
return result
data = ['-', '-', '+', '+', '+','-', '+','-', '+','-','-']
print(StringSort(data)) 结果丝毫不差，没错这不是排序，但这解决了排序问题。