排序算法的python实现

枫铃4年前 (2021-06-26)Python266

冒泡排序

在这里插入图片描述

冒泡排序是比较简单的排序方法，它的思路是重复的走过要排序的序列，一次比较两个元素，如果顺序错误，就交换元素的位置，直到没有元素需要交换位置。

原始618597第一次168597第二次168597第三次165897第四次165897第五次165879

……

第N次156789

代码实现：

1.lst = [6,1,8,5,9,7]
2.for i in range(len(lst)-1):
3.    for j in range(len(lst)-1):
4.        if lst[j] > lst[j+1]:
5.            tmp = lst[j]
6.            lst[j] = lst[j+1]
7.            lst[j+1] = tmp
8.print lst

选择排序

在这里插入图片描述

选择排序是从等待排序的数组里选择一个最小（或者最大）的元素，拿出来放入新的数组，直到取出全部元素。

原始6185973第一次1685973第二次1385976第三次1358976第四次1356978第五次1356798第六次1356789

每一次排序后最小的数组放在已排序的序列的最后

实现代码

1.lst = [6,1,8,5,9,7,3]
2.for i  in range(len(lst)):
3.    tmp = lst[i]
4.    pos = i
5.    for j in range(i+1,len(lst)):
6.        if tmp > lst[j]:
7.            tmp = lst[j]
8.            pos = j
9.    a_tmp = lst[i]
10.    lst[i] = tmp
11.    lst[pos] = a_tmp
12.
13.print lst

插入排序

在这里插入图片描述

插入排序是一种简单直观的排序算法，原理是通过构建有序序列，对于未排序的数据，在已排序的序列中从后想前扫描，找到相应位置后插入。插入排序通常采用in-place排序，即只需要用到O(1) 的额外空间的排序。

算法描述：

从第一个元素开始，记该元素已经排序，
获取下一个元素作为新元素，在已经排序的序列中，从后向前扫描
如果该元素（已排序的序列中的元素）大于新元素，，则将该元素移到下一位置
重复步骤3，直到找到已排序的元素小雨或等于新元素的位置
将心元素插入该位置
重复步骤2 ～步骤5 ，直到排序完成

在排序时，如果元素比较的操作代价比较大，可以采用二分查找，来减少操作。
实现代码：

1.lst = [6,1,8,5,9,7,2,4,6,9,2,32,45,76,8,3,3,4]
2.
3.for i in range(len(lst)):
4.    for j in range(i,0,-1):
5.        if lst[j-1] >lst[j]:
6.            tmp = lst[j-1]
7.            lst[j-1] = lst[j]
8.            lst[j] = tmp

快速排序 quick sort

又称划分交换排序;排序n个元素，需要Ο(n log n)次比较，最坏情况时需要，Ο(n2)次比较，但这种状况并不常见。

设有序列 lst = [3,0,1,8,7,2,5,4,9,6] ， i= 0 j=9 k = lst[0]

01234567893018725496201873549620137854962013785496

以3为基准，从右向左找比 3 小的值 ,j–
找到第一个小于三的数字2， lst[i] lst[j]交换位置；
从左向右找第一大于3的数字 8 ，交换 lst[i] lst[j]位置 i++
1. 继续从右向左找比3小的数字，直到 i==j 此时第一趟完成，3的当前位置为正确位置
此时大序列可分为两个小序列
sub_lst_01 = [2,0,1]
sub_lst_01 = [7,8,5,4,9,6]
按照第一趟排序的规则对两个子序列进行排序，直到所有子序列长度为1。