1 冒泡排序
1.1 算法步骤：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
（1） 不管原始数组是否有序，时间复杂度都是O（n2）
（2） 空间复杂度是O（1）
（3） 冒泡排序是从最后一位开始确定最大或最小的数，保证后面的数都是有序的且都大于或小于前面的数
1.2 算法实现
def bubble_sort(alist):
for i in range(len(alist) - 1):
for j in range(len(alist) - 1 - i):##最后的几位已经确定好大小的不用再次参与排序
if alist[j] > alist[j + 1]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
count += 1
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)
1.3 算法优化
def bubble_sort(alist):
for i in range(len(alist) - 1):
count = 0 ## 记录交换的次数
for j in range(len(alist) - 1 - i):
if alist[j] > alist[j + 1]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
count += 1 ## 如果此次遍历为未发生交换，则说明数据是有序的
if count == 0:
return
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)
2 选择排序
2.1 算法步骤
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕
2.2 算法实现
def select_sort(alist):
for i in range(len(alist) - 1):
min = i ## i之前的元素已经确定位置，假设第i个元素为最小值
for j in range(i, len(alist)):
if alist[min] > alist[j]: ## 如果后面的元素比第i个元素小，则记录该元素的索引为最小元素的索引
min = j
alist[i], alist[min] = alist[min], alist[i]
list = [3, 4, 2, 7, 11, 15, 5]
select_sort(list)
print(list)
3 插入排序
3.1 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
3.2 算法实现
def insert_sort(alist):
for i in range(1, len(alist)):
for j in range(i, 0, -1): ## 倒序取从下标i的元素开始到下标0
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
list = [3, 4, 2, 7, 11, 15, 5]
insert_sort(list)
print(list)
3.3 算法优化
def insert_sort(alist):
for i in range(1, len(alist)):
for j in range(i, 0, -1): ## 倒序取从下标i的元素开始到下标0
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
else: ## 如果当前数值大于前一个数值，退出
break
list = [3, 4, 2, 7, 11, 15, 5]
insert_sort(list)
print(list)
4 快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 将大于pivot的值放在pivot的右边；
- 将小于pivot的值放在pivot的左边；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
4.2 算法实现
def quickSort(left, right, lst):
l, r = left, right ## 确定左右指针
if left >= right: ## 如果序列只有一个元素，则退出排序
return
## 确定基准数为最左侧元素
base = lst[left]
## base为序列最左侧元素，则应为右指针先左移，然后左指针右移
while l < r:
while l < r and lst[r] >= base: ## 如果l<r同时最右侧的值大于等于base，则向左移动r指针，退出的条件右指针的值<base
r -= 1
while l < r and lst[l] <= base: ## 如果l<r同时最左侧的值小于等于base，则向右移动l指针,退出的条件左指针的值>base
l += 1
if l < r: ## 如果左指针小于右指针（同时lst[r] < base lst[l] > base，满足上述两个条件）,则交换左右指针的值
lst[l], lst[r] = lst[r], lst[l]
lst[l], lst[left] = lst[left], lst[l] ## 基准数回归，将左右指针所指元素和基准数进行交换
## 此时一次排序结束
quickSort(left, l - 1, lst) ## 对基准数左侧序列进行排序
quickSort(l + 1, right, lst) ## 对基准数右侧序列进行排序
list = [3, 4, 2, 7, 11, 15, 5]
end = len(list) - 1
quickSort(0, end, list) ## 开始位置索引，结束位置索引，列表
print(list)
4 四种排序算法的比较
| 算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(nlog2n) | 不稳定 |
总结
到此这篇关于python排序算法简单实现的文章就介绍到这了,更多相关python排序算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
