第九课 - 冒泡排序,选择排序,快速排序和归并排序

# 冒泡排序 **原理** (1)循环遍历列表,每次循环找出本次循环最大的元素排在后面 (2)需要使用嵌套循环实现,外层循环控制总循数,内层循环负责每层的循环比较 ![](http://wenda.chinahadoop.cn/uploads/questions/20180501/b33d35a9f6473eeeb386050977548b63.png) **算法:** * 第一轮循环5次 = 循环列表的长度6 - 1,即元素之间比较次数;找出最大元素 * 第二轮循环4次 = 循环列表的长度6 - 找出的最大值个数1 - 1;依次类推。 * 第n轮循环n次 = 循环列表长度 m - 找出的最大值个数 j - 1 * n = 列表元素个数 - 1 **算法实现:** ``` # 排序的总轮数=列表元素个数 - 1 # 每轮元素互相比较的次数 = 列表元素个数 - 已经排好序的元素个数 - 1 #data_list:待排序列表 def bubble_sort(data_list): num = len(data_list) #列表元素个数 for i in range(0,num -1):#排序的总轮数 print("第{}轮:".format(i)) for j in range(0,num-i-1): if data_list[j] > data_list[j+1]:#前后两个元素比较 data_list[j],data_list[j+1] = data_list[j+1],data_list[j] print(data_list) ``` # 选择排序 **原理** (1)将待排序列表看成是未排序和已排序两部分 (2)每次从未排序列表中找出最小值放到已排序列表末尾 ![](http://wenda.chinahadoop.cn/uploads/questions/20180501/8f7a8d9c9be02b419db780e451054a4d.png) **算法实现** ``` #data_list:待排序列表 def select_sort(data_list): list_len = len(data_list) #待排序元素个数 for i in range(0,list_len-1):#控制排序比较总轮数 tmp_min_index = i for j in range(i+1,list_len): if data_list[tmp_min_index] > data_list[j]: tmp_min_index = j if i != tmp_min_index: data_list[i],data_list[tmp_min_index] = data_list[tmp_min_index],data_list[i] print(data_list) ``` # 快速排序 **原理** (1)一次排序按照一个基准值将待排序的列表分隔成两部分,基准值左边是比基准值小的元素,基准值右边是比基准值大的元素 (2)按照上一步的方法对基准值左右两部分数据分别进行快速排序 ![](http://wenda.chinahadoop.cn/uploads/questions/20180501/c0a200d7c999ab49df14a6f560b74241.png) **算法实现** ![](http://wenda.chinahadoop.cn/uploads/questions/20180501/494c95ba9ed27af9c85cc15c80698ac2.png) # 归并排序 **原理** 先递归分解序列,再排序合并序列 ![](http://wenda.chinahadoop.cn/uploads/questions/20180501/6c8b4242386e7c76e4032ba8db27cdf4.png) **算法** (1)拆分到不能分为止 (2)合并的过程中进行排序 **算法实现** ``` def merge_sort(data_list): if len(data_list)<=1: return data_list #根据列表长度确定拆分的中间位置 mid_index = len(data_list) // 2 # left_list = data_list[:mid_index] #使用切片实现对列表的切分 # right_list = data_list[mid_index:] left_list = merge_sort(data_list[:mid_index]) right_list = merge_sort(data_list[mid_index:]) return merge(left_list,right_list) def merge(left_list,right_list): l_index = 0 r_index = 0 merge_list = [] while l_index < len(left_list) and r_index < len(right_list): if left_list[l_index] < right_list[r_index]: merge_list.append(left_list[l_index]) l_index += 1 else: merge_list.append(right_list[r_index]) r_index += 1 merge_list += left_list[l_index:] merge_list += right_list[r_index:] return merge_list ``` **排序算法调用输出:** ``` list = [28,32,14,12,53,42] #冒泡排序 bubble_sort(list) #选择排序 select_sort(list) #快速排序 quick_sort(list,0,len(list)-1) #归并排序 new_list = merge_sort(list) print("--------排序结果--------") print(new_list) ```

0 个评论

要回复文章请先登录注册