Python实现经典排序算法

浅见池也

　　1.冒泡排序：
　　设计思想：
　　1.依次对比左右相邻的两个数字，让最大的数，排到队末，此方法类似水泡，从水底逐渐上浮逐渐变大；
　　2.将上述方法执行len(array)遍，让所有较大的数据都依次冒出来，从小到大的方式排到队末，整个列表形成一个升序，排序则完成.
　　def maopao(array):
　　for i in range(len(array)):
　　for j in range(len(array)-1):
　　if array[j] > array[j + 1]:
　　array[j], array[j + 1] = array[j + 1], array[j]
　　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[j] > l[j + 1]:
　　l[j], l[j + 1] = l[j + 1], l[j]
　　for k in range(size - 2 - i, i, -1):  # -2 上面已经获取末位最大值无须循环，
　　-i同上为了减少循环次数
　　if l[k] < l[k - 1]:
　　l[k], l[k - 1] = l[k - 1], l[k]
　　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[0]
　　_left, _right = [], []
　　for i in array[1:]:
　　if i >= base:
　　_right.append(i)
　　else:
　　_left.append(i)
　　_left = quick_sort(_left)
　　_right = quick_sort(_right)
　　return _left + [base] + _right
　　4.插入排序：
　　设计思想：
　　1.从列表中第二个值开始循环对比，如果前一个比当前数大，把当前的数多存一份；
　　2.当，前一个值比需要插入的值大时，把前面的值依次往后挪（当前位置的值等于前一个位置值），while 循环到队首；
　　3.直到前面的值小于等于需要插入值，用多存的数据插入到对应位置上；
　　def insert_sort(array):
　　for i in range(1, len(array)):
　　if array[i - 1] > array:
　　temp = array
　　while i > 0 and array[i-1] > temp:  # 用待插入的temp和前面已排序数据对比，找把前面的值依次往后挪，直到前面值小于等于需要插入值，用多存的数据插入到对应位置。
　　array = array[i - 1]  #  依次把前一个数往后挪一位
　　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[mid:])  # 从中间开始，右边依次递归分解成单个列表
　　return merge(_left,_right)  # 从单个列表依次递归排序组合成有序的列表
　　def merge(_left,_right):
　　result = []
　　i, j = 0, 0
　　while i < len(_left) and j < len(_right):
　　if _left <= _right[j]
　　result.append(_left)
　　i += 1
　　else:
　　result.append(_right)
　　j += 1
　　result += _left[i:]
　　result += _right[j:]
　　return result