算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明.
#学习难度: ###桶排序 < 冒泡排序 < 选择排序 < 插入排序 < 快速排序 < 归并排序 < 希尔排序
桶排序(简化版)
桶排序: 将列表中最大数与最小数之间的数全部做成标签,贴到N个桶上 将每个元素放到对应值的桶里面(如果有M个相同的元素值,则将M个元素全部放到相应的桶中,取的时候占用M个位置) 最后按照桶编号的先后顺序,从桶中依次取出值,排列完成
__author__ = 'zhaozhao'def pail_sort(my_list): max_num = max(my_list) min_num = min(my_list) Y_list = list() for i in range(min_num, max_num+1): zhao_list = [i, 0] Y_list.append(zhao_list) for m in my_list: for Y in Y_list: if Y[0] == m: Y[1] += 1 result = list() for n in Y_list: for t in range(0, n[1]): result.append(n[0]) return result passdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("简单桶排序之前的序列:", Y_list) print("简单桶排序之后的序列:", pail_sort(Y_list))if __name__ == '__main__': main()复制代码 冒泡排序
冒泡排序: 有N个待排序元素 1.设置游标,游标带领第一个元素开始,与右侧元素(第1个元素)比较,如果大于右侧元素,则二者交换数值,然后游标带领元素继续向右移动，如果小于右侧元素,则不进行交换，游标继续向右移动，当游标移动到列表最右侧，第一轮比较就完成了（共比较N-1次） 2.然后游标回到起始位置，开始第二轮比较，由于最后一个元素已经确定大于剩余的元素所以(第二轮共比较N-2)次。 3.由于每次都只能选取出一个最大值,所以N个元素的数组,进行N-1轮对比即可完成排列
__author__ = 'zhaozhao'def bubble_sort(my_list): N = len(my_list) # 循环的次数 circle_num = N-1 while circle_num > 0: # 初始的游标值 index_value = 0 while index_value < circle_num: if my_list[index_value] < my_list[index_value+1]: pass else: my_list[index_value], my_list[index_value+1] = my_list[index_value + 1], my_list[index_value] # 游标右移一个单位 index_value += 1 pass circle_num -= 1 print("冒泡排序之后的序列:",my_list) return my_listdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("冒泡排序之前的序列:",Y_list) bubble_sort(Y_list) passif __name__ == '__main__': main()复制代码 选择排序
选择排序(升序): 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
__author__ = 'zhaozhao'def selection_sort(my_list): # N为列表元素的个数 N = len(my_list) circle_num = 0 #需要进行N-1次循环 while circle_num < N: # 每次循环开始的游标索引值 为 circle_num , 结束的索引值为N-1 for m in range(circle_num, N): if my_list[circle_num] <= my_list[m]: pass else: my_list[circle_num], my_list[m] = my_list[m], my_list[circle_num] circle_num += 1 print("选择排序之后的序列:",my_list)def main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("选择排序之前的序列:",Y_list) selection_sort(Y_list) passif __name__ == '__main__': main()复制代码 插入排序
插入排序: 序列共有N个元素 将序列分为,已排序序列(第一个元素) 和 未排序序列(除第一个元素以外的其它元素，共N-1个）两部分,然后通过N-1轮循环,将N-1个元素,依次添加到已排序序列中
__author__ = 'zhaozhao'def insert_sort(my_list): N = len(my_list) finish_list = list() f_len = len(finish_list) finish_list.append(my_list[0]) # circle_num为待插入的值的索引 for circle_num in range(1, N): for pre in range(0, circle_num): # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面 if my_list[circle_num] < finish_list[pre]: finish_list.insert(pre, my_list[circle_num]) break # 如果新加入的值比已排序的序列最大的值都大,那么 elif my_list[circle_num] >= finish_list[-1]: finish_list.append(my_list[circle_num]) break # 如果新加入的值 比已排序的某个值大但比 已排序后面的值小 elif my_list[circle_num] >= finish_list[pre] and my_list[circle_num] < finish_list[pre+1]: finish_list.insert(pre+1, my_list[circle_num]) break else: pass return finish_listdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("插入排序之前的序列:", Y_list) insert_sort(Y_list) print("插入排序之后的序列:", insert_sort(Y_list))if __name__ == '__main__': main()复制代码 快速排序(面试常用算法)
快速排序 1.选择左侧第一个元素为 基准元素(其实基准元素可以是任意值,这里选择第一个是为了方便叙述)
- 创建两个指针, 左侧指针初始位置在列表首部,右侧指针初始位置在列表尾部
- 先移动(为了保证,两个指针相遇时,所在位置的元素不大于 基准元素)右侧指针(左移),当到达 元素值 小于基准值 的位置停止(等待左侧指针的支援)
- 移动左侧指针(右移),当到达 元素值 大于基准值 的位置停止,将此元素与 右侧指针当时所在位置的值互换.
- 互换元素后,右侧指针继续先移动, 循环 3,4步骤 6, 当左右指针相遇时, 将相遇位置的 元素值与 基准元素对调,完成第一轮循环 7, 此时,基准元素左侧的值都小于 基准值,基准元素右侧的值都大于基准值 8, 递归调用上面的算法,将两侧的 元素列表 进行排序 9, 伴随着层层递归,新的基准值两侧的元素会越来越少,当基准值 无两侧元素时,排序终止
def q_sort(my_list, left, right): #设置左右指针 left_point = left right_point = right stand_num = left if left > right: return while left_point != right_point: #先移动右指针,如果遇到 比基准值更小 的值,就停下来 while (my_list[right_point] >= my_list[stand_num]) and (left_point < right_point): right_point -= 1 # 再移动左指针,如果遇到比基准值更大的值,就停下来 while (my_list[left_point] < my_list[stand_num]) and (left_point < right_point): left_point += 1 # 找到了双方可交换的点后, 开始交换 my_list[left_point], my_list[right_point] = my_list[right_point],my_list[left_point] # 将基准点 与 指针相遇的点互换 if left_point == right_point: my_list[stand_num], my_list[left_point] = my_list[left_point], my_list[stand_num] q_sort(my_list, left, left_point-1) q_sort(my_list, right_point+1, right) return (my_list)def quick_sort(out_of_order): end = len(out_of_order) - 1 start = 0 q_sort(out_of_order, start, end) return out_of_orderdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("快速排序之前的序列:", Y_list) print("快速排序之后的序列:", quick_sort(Y_list))if __name__ == '__main__': main()复制代码 归并排序（先分后和, 分而治之）
归并排序(python内置sort方法的实现原理): 归并排序是典型的分治法排序，将待排序元素拆成多个分组，分组内部进行排序，然后分组进行合并，最终合并成完整的数组。
__author__ = 'zhaozhao'# 负责 将列表拆分def merge_sort(Y_list): if len(Y_list) <= 1: return Y_list # 先将未排序的列表进行分组 num = len(Y_list) // 2 left_list = merge_sort(Y_list[:num]) right_list = merge_sort(Y_list[num:]) # 将分组的列表交给merge函数, merge负责将列表合并 return merge(left_list, right_list)# 负责将列表合并def merge(left, right): left_point = 0 right_point = 0 finish_list = list() while right_point < len(right) and left_point < len(left): if left[left_point] <= right[right_point]: finish_list.append(left[left_point]) left_point += 1 else: finish_list.append(right[right_point]) right_point += 1 finish_list += left[left_point:] finish_list += right[right_point:] return finish_listdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("归并排序之前的序列:", Y_list) print("归并排序之后的序列:", merge_sort(Y_list))if __name__ == '__main__': main()复制代码 希尔排序
希尔排序: 希尔排序是为优化插入排序,而创建的算法, 其核心思想是通过设置步长 将元素分组，对每个分组进行快速排序,然后将步长减少,产生新的分组，对每个新分组进行快速排序，当步长减为1时,完成排序
__author__ = 'zhaozhao'def shell_sort(Y_list): gap = len(Y_list) while gap >= 0: tem_list = list() if gap == 0: return Y_list # 将要抽取的值和索引保存到一个 列表里 for index, value in enumerate(Y_list): if index % gap == 0: zhao_list = [index, value] tem_list.append(zhao_list) tem_value_list = list() for i in tem_list: tem_value_list.append(i[1]) tem_value_list = insert_sort(tem_value_list) for i, vv in enumerate(tem_value_list): tem_list[i][1] = vv # 排序好的值 替换 原位置的值 for iv in tem_list: Y_list[iv[0]] = iv[1] gap = gap // 2 return Y_listdef insert_sort(my_list): N = len(my_list) finish_list = list() f_len = len(finish_list) finish_list.append(my_list[0]) # circle_num为待插入的值的索引 for circle_num in range(1, N): for pre in range(0, circle_num): # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面 if my_list[circle_num] < finish_list[pre]: finish_list.insert(pre, my_list[circle_num]) break # 如果新加入的值比已排序的序列最大的值都大,那么 elif my_list[circle_num] >= finish_list[-1]: finish_list.append(my_list[circle_num]) break # 如果新加入的值 比已排序的某个值大但比 已排序后面的值小 elif my_list[circle_num] >= finish_list[pre] and my_list[circle_num] < finish_list[pre+1]: finish_list.insert(pre+1, my_list[circle_num]) break else: pass return finish_listdef main(): Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20] print("希尔排序之前的序列:", Y_list) print("希尔排序之后的序列:", shell_sort(Y_list))if __name__ == '__main__': main()复制代码