一、冒泡排序

1、原理

循环遍历列表，每次循环找出本次循环最大的元素排在后边。

需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。

2、过程

排序算法 - 图1

1）比较相邻的两个数据，如果第二个数小，就交换位置。

2）从头到尾两两比较，一直到比较最后两个数据。最终最大的数被交换到末尾。

3）继续重复上述过程，依次将第2.3…n-1个数排好位置。

3、Python代码实现
  1. # 冒泡排序
  2. '''
  3. 排序的总轮数=列表元素个数 - 1
  4. 每轮元素互相比较的次数 = 列表元素个数 - 已经排好序的元素个数 - 1
  5. '''
  6. def bubble_sort(data_list):
  7.     num = len(data_list) #列表元素个数
  8.     for i in range(0,num -1):#排序的总轮数
  9.         print("第{}轮：".format(i))
  10.         for j in range(0,num-i-1):
  11.             if data_list[j] > data_list[j+1]:#前后两个元素比较
  12.                 data_list[j],data_list[j+1] = data_list[j+1],data_list[j]
  13.             print(data_list)
  14. list = [28,32,14,12,53,42]
  15. bubble_sort(list)

运行结果

  1. 第0轮：
  2. [28, 32, 14, 12, 53, 42]
  3. [28, 14, 32, 12, 53, 42]
  4. [28, 14, 12, 32, 53, 42]
  5. [28, 14, 12, 32, 53, 42]
  6. [28, 14, 12, 32, 42, 53]
  7. 第1轮：
  8. [14, 28, 12, 32, 42, 53]
  9. [14, 12, 28, 32, 42, 53]
  10. [14, 12, 28, 32, 42, 53]
  11. [14, 12, 28, 32, 42, 53]
  12. 第2轮：
  13. [12, 14, 28, 32, 42, 53]
  14. [12, 14, 28, 32, 42, 53]
  15. [12, 14, 28, 32, 42, 53]
  16. 第3轮：
  17. [12, 14, 28, 32, 42, 53]
  18. [12, 14, 28, 32, 42, 53]
  19. 第4轮：
  20. [12, 14, 28, 32, 42, 53]

二、选择排序

1、原理

将待排序列表看成是已排序和未排序两部分

每次从未排序列表中找出最小值放到已排序列表末尾

2、过程

排序算法 - 图2

在长度为n的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；

第二次遍历n-2个数，找到最小的数值与第二个元素交换；

……

第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

3、Python代码实现
  1. # 选择排序
  2. def select_sort(data_list):
  3.     list_len = len(data_list) #待排序元素个数
  4.     for i in range(0,list_len-1):#控制排序比较总轮数
  5.         tmp_min_index = i
  6.         for j in range(i+1,list_len):
  7.             if data_list[tmp_min_index] > data_list[j]:
  8.                 tmp_min_index = j
  9.         if i != tmp_min_index:
  10.             data_list[i],data_list[tmp_min_index] = data_list[tmp_min_index],data_list[i]
  11.         print(data_list)
  12. list = [28,32,14,12,53,42]
  13. select_sort(list)

运行结果

  1. [12, 32, 14, 28, 53, 42]
  2. [12, 14, 32, 28, 53, 42]
  3. [12, 14, 28, 32, 53, 42]
  4. [12, 14, 28, 32, 53, 42]
  5. [12, 14, 28, 32, 42, 53]

三、快速排序

1、原理

一次排序按照一个基准值将待排序的列表分割成两部分，基准值左边是比基准值小的元素，基准值右边是比基准值大的元素。

按照上一步的方法对基准值左右两部分数据分别进行快速排序。

2、过程

排序算法 - 图3

1）先从数列中取出一个数作为基准值；

2）将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；

3）对左右两个小数列重复第二步，直至各区间只有1个数。

3、Python代码实现
  1. #快速排序
  2. def quick_sort(data_list,start,end):
  3.     #设置递归结束条件
  4.     if start >= end:
  5.         return
  6.     low_index = start#低位游标
  7.     high_index = end #高位游标
  8.     basic_data = data_list[start] #初始基准值
  9.     while low_index < high_index:
  10.         #模拟高位游标从右向左指向的元素与基准值进行比较，比基准值大则高位游标一直向左移动
  11.         while low_index < high_index and data_list[high_index] >= basic_data:
  12.             high_index -= 1
  13.         if low_index != high_index:
  14.             #当高位游标指向的元素小于基准值，则移动该值到低位游标指向的位置
  15.             data_list[low_index] = data_list[high_index]
  16.             low_index += 1 #低位游标向右移动一位
  18.         while low_index < high_index and data_list[low_index]<basic_data:
  19.             low_index +=1
  20.         if low_index != high_index:
  21.             data_list[high_index] = data_list[low_index]
  22.             high_index -= 1
  24.     data_list[low_index] = basic_data
  25.     #递归调用
  26.     quick_sort(data_list,start,low_index-1) #对基准值左边未排序队列排序
  27.     quick_sort(data_list,high_index+1,end) #对基准值右边未排序队列排序
  29. list = [28,32,14,12,53,42]
  30. quick_sort(list,0,len(list)-1)
  31. print(list)

运行结果

  1. [12, 14, 28, 32, 42, 53]

四、归并排序

1、原理

先递归分解序列，再排序合并序列

2、过程

排序算法 - 图4

3、Python代码实现
  1. # 归并排序
  2. def merge_sort(data_list):
  3.     if len(data_list)<=1:
  4.         return data_list
  5.     #根据列表长度确定拆分的中间位置
  6.     mid_index = len(data_list) // 2
  7.     # left_list = data_list[:mid_index] #使用切片实现对列表的切分
  8.     # right_list = data_list[mid_index:]
  9.     left_list = merge_sort(data_list[:mid_index])
  10.     right_list = merge_sort(data_list[mid_index:])
  11.     return merge(left_list,right_list)
  13. def merge(left_list,right_list):
  14.     l_index = 0
  15.     r_index = 0
  16.     merge_list = []
  17.     while l_index < len(left_list) and r_index < len(right_list):
  18.         if left_list[l_index] < right_list[r_index]:
  19.             merge_list.append(left_list[l_index])
  20.             l_index += 1
  21.         else:
  22.             merge_list.append(right_list[r_index])
  23.             r_index += 1
  25.     merge_list += left_list[l_index:]
  26.     merge_list += right_list[r_index:]
  27.     return merge_list
  29. list = [28, 32, 14, 12, 53, 42]
  30. new_list = merge_sort(list)
  31. print("--------排序结果--------")
  32. print(new_list)

运行结果

  1. --------排序结果--------
  2. [12, 14, 28, 32, 42, 53]