Python实现经典排序算法
1.冒泡排序：设计思想：
1.依次对比左右相邻的两个数字，让最大的数，排到队末，此方法类似水泡，从水底逐渐上浮逐渐变大；
2.将上述方法执行len(array)遍，让所有较大的数据都依次冒出来，从小到大的方式排到队末，整个列表形成一个升序，排序则完成.
def maopao(array):
for i in range(len(array)):
for j in range(len(array)-1):
if array > array:
array, array = array, array
return array
2.鸡尾酒排序
设计思想：
1.作为冒泡排序的改进，顶层循环减少一半 range(len(array)/2);
2.每次对一分二的两个列表分别进行冒泡排序，直到排序完成，实际测试对比冒泡排序效率提升50%左右。
def cocktail_sort(l):# 鸡尾酒排序
size = len(l)
sign = 1
for i in range(size / 2):
if sign:
sign = 0
for j in range(i,> -i是为了减少循环的次数，当i=0时执行此循环就已经获取末位最大值
if l > l:
l, l = l, l
for k in range(size - 2 - i, i, -1):# -2 上面已经获取末位最大值无须循环，
-i同上为了减少循环次数
if l < l:
l, l = l, l
sign = 1
else:
break
return l
3.快速排序：
设计思想：
1.以第一个数作为基础参考，依次和列表中每一个数进行对比；
2.分别定义左右两个空列表，小于第一个参考数字放在左边空列表，大于放在右边空列表；
3.把左右两个列表作为参数传给排序函数本身，赋值给一个变量，让其递归执行排序；
4.返回左列表排序结果 + [基础参考值] + 右列表排序结果，即最终排序好的结果
def quick_sort(array):# 快速排序
if not array or len(array) == 1:
return array
base = array
_left, _right = [], []
for i in array:
if i >= base:
_right.append(i)
else:
_left.append(i)
_left = quick_sort(_left)
_right = quick_sort(_right)
return _left + + _right
4.插入排序：
设计思想：
1.从列表中第二个值开始循环对比，如果前一个比当前数大，把当前的数多存一份；
2.当，前一个值比需要插入的值大时，把前面的值依次往后挪（当前位置的值等于前一个位置值），while 循环到队首；
3.直到前面的值小于等于需要插入值，用多存的数据插入到对应位置上；
def insert_sort(array):
for i in range(1, len(array)):
if array > array:
temp = array
while i > 0 and array > temp:# 用待插入的temp和前面已排序数据对比，找把前面的值依次往后挪，直到前面值小于等于需要插入值，用多存的数据插入到对应位置。
array = array#依次把前一个数往后挪一位
i -= 1
array = temp
return array
5.归并排序
设计思想：
1.从中间开始讲列表递归分解成单个列表；
2.从单个列表递归排序组合成一个有序的列表；
def mergesort(array):
if len(array) <= 1:
return array
mid = len(array) / 2
_left = mergesort(array[:mid])# 从中间开始，左边依次递归分解成单个列表
_right = mergesort(array)# 从中间开始，右边依次递归分解成单个列表
return merge(_left,_right)# 从单个列表依次递归排序组合成有序的列表
def merge(_left,_right):
result = []
i, j = 0, 0
while i < len(_left) and j < len(_right):
if _left <= _right
result.append(_left)
i += 1
else:
result.append(_right)
j += 1
result += _left
result += _right
return result
页:
[1]