排序是什么

排序：将一组“无序”的记录序列调整为“有序”的记录序列

列表排序

列表排序：将无序列表变为有序列表

输入：列表

输出：有序列表

顺序的类型：升序（从小到大）与降序（从大到小）

内置排序函数：sort()

常见的排序算法

排序基础三人组：冒泡排序 选择排序 插入排序

排序进阶三人组：快速排序 堆排序 归并排序

其他排序算法：希尔排序 计数排序 基数排序 桶排序

（可能归纳不全࿰c;但保证管用）

---

冒泡排序

什么是冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访要排序的数列࿰c;依次比较两个元素࿰c;如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换࿰c;也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

简单来说࿰c;列表每两个相邻的数࿰c;如果前面的比后面的大则交换这两个数࿰c;一趟排序完成后࿰c;则无序区减少一个数࿰c;有序区增加一个数。（每一趟冒出一个无序区最大的数--->冒泡排序）

 图片来自菜鸟教程

代码讲解

# 冒泡排序初级代码

import random

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟,此处也可以直接用len(lst),但是直接用len(lst)会多走了最后一遍

@R_673_5179@ for j in range(len(lst)-i-1):  # 表示箭头（下标）可移动的无序区范围࿰c;比如长为10的列表࿰c;i取值则是0-9࿰c;第二次查找则无序区的长度为10-i(此时是1࿰c;第一次是0)-1（-1因为是根据下标查找）=8࿰c;因此箭头范围0-8

@R_673_5179@     if lst[j] > lst[j+1]: # 此时是升序排序࿰c;>改为<则改为了降序

@R_673_5179@@R_673_5179@  lst[j],lst[j+1] = lst[j+1],lst[j]

@R_673_5179@ print(f"第{i+1}趟后的列表为：{lst}")  # 查看排序过程

 

lst1 = [random.randint(0,10000) for i in range(5)]

print(f"初始列表:{lst1}")

bubble_sort(lst1)

# 结果

# 初始列表:[3053, 8957, 2153, 4502, 2518]

# 第1趟后的列表为：[3053, 2153, 4502, 2518, 8957]

# 第2趟后的列表为：[2153, 3053, 2518, 4502, 8957]

# 第3趟后的列表为：[2153, 2518, 3053, 4502, 8957]

# 第4趟后的列表为：[2153, 2518, 3053, 4502, 8957]

lst2 = [1,2,3,8,7,6,5]

print(f"初始列表:{lst2}")

bubble_sort(lst2)

# 初始列表:[1, 2, 3, 8, 7, 6, 5]

# 第1趟后的列表为：[1, 2, 3, 7, 6, 5, 8]

# 第2趟后的列表为：[1, 2, 3, 6, 5, 7, 8]

# 第3趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

# 第4趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

# 第5趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

# 第6趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

此时我们发现冒泡排序多走路了一趟࿰c;第3趟和第6趟一样࿰c;且第3趟已排好࿰c;那么如何对代码进行改进？

代码优化

# 改进后的代码

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟

@R_673_5179@ exchange = false  # 每一趟做标记

@R_673_5179@ for j in range(len(lst)-i-1):  # 表示箭头

@R_673_5179@     if lst[j] > lst[j+1]: # 此时是升序排序࿰c;>改为<则改为了降序

@R_673_5179@@R_673_5179@  lst[j],lst[j+1] = lst[j+1],lst[j]

@R_673_5179@@R_673_5179@  exchange = True  # 进行了交换࿰c;exchange标记为Ture

@R_673_5179@ print(f"第{i+1}趟后的列表为：{lst}")  # 查看排序过程

@R_673_5179@ if not exchange: # 如果没有进行交换࿰c;直接返回࿰c;优化的步骤

@R_673_5179@     return

lst2 = [1,2,3,8,7,6,5]

print("***改进后的冒泡排序***")

print(f"初始列表:{lst2}")

bubble_sort(lst2)

# 结果

# ***改进后的冒泡排序***

# 初始列表:[1, 2, 3, 8, 7, 6, 5]

# 第1趟后的列表为：[1, 2, 3, 7, 6, 5, 8]

# 第2趟后的列表为：[1, 2, 3, 6, 5, 7, 8]

# 第3趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

# 第4趟后的列表为：[1, 2, 3, 5, 6, 7, 8]

冒泡算法的时间复杂度：O(n2)࿰c;两层查找。

---

选择排序

什么是选择排序

选择排序（SELEction sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素࿰c;存放到排序序列的起始位置࿰c;然后࿰c;再从剩余未排序元素中继续寻找最小（大）元素࿰c;然后放到已排序序列的末尾。以此类推࿰c;直到所有元素均排序完毕。

简单来说࿰c;选择排序就是每一趟排序记录最小的数࿰c;并放到第一个位置࿰c;在一趟排序记录列表中无序区最小的数࿰c;放到有序区第二个位置…….以此循环࿰c;直到只剩最后一个数时࿰c;此数绝对是最大的数。

此算法的关键点时：有序区和无序区以及无序区最小数的位置。

图片来自菜鸟教程 

代码讲解

简单易理解的选择排序

def SELEct_sort_simple(lst):

    new_lst = []

    for i in range(len(lst)):

@R_673_5179@ min_val = min(lst)

@R_673_5179@ new_lst.append(min_val)

@R_673_5179@ lst.remove(min_val)

    return new_lst

 

lst1 = [3,2,4,13,11,8]

result = SELEct_sort_simple(lst1)

print(result)

# 结果

# [2, 3, 4, 8, 11, 13]

思考：该代码有什么不足之处？或需要改进的地方？@H_355_262@

1.建立新的列表占用了内存

2.时间复杂度较大࿰c;O(n^2)

接下来我们对列表进行优化

优化后的选择排序代码@H_355_262@

def SELEct_sort(lst):

    for i in range(len(lst) - 1):  # i代表第几趟

@R_673_5179@ min_LOCATIOn = i # 最小位置的标记࿰c;第一次默认最小的数为无序区的第一个࿰c;即下标为i

@R_673_5179@ for j in range(i+1,len(lst)): # 从i开始相当于自己和自己比了一次࿰c;此步骤多余࿰c;因此从i+1开始

@R_673_5179@     if lst[j] < lst[min_LOCATIOn]:

@R_673_5179@@R_673_5179@  min_LOCATIOn = j

@R_673_5179@ lst[i],lst[min_LOCATIOn] = lst[min_LOCATIOn],lst[i] # 最小的值和有序区的最后一个值进行交换

@R_673_5179@ print(f"第{i + 1}趟后的列表为：{lst}")

 

 

lst1 = [3,2,4,13,11,8]

SELEct_sort(lst1)

# 结果

# 第1趟后的列表为：[2, 3, 4, 13, 11, 8]

# 第2趟后的列表为：[2, 3, 4, 13, 11, 8]

# 第3趟后的列表为：[2, 3, 4, 13, 11, 8]

# 第4趟后的列表为：[2, 3, 4, 8, 11, 13]

# 第5趟后的列表为：[2, 3, 4, 8, 11, 13]

选择排序的时间复杂度：O(n2)(两层循环)

---

插入排序

什么是插入排序？

先举个生活实例

假设࿰c;你的手上有一副排好顺序的牌（有序区）࿰c;此时你需要从还没摸完的牌（无序区）里摸一张牌࿰c;插入到已有牌的手里࿰c;直到摸完牌（从无序去）࿰c;最后手上的牌（有序区）也排好序了。

插入排序（英语：Insertion Sort）的工作原理是通过构建有序序列࿰c;对于未排序数据࿰c;在已排序序列中从后向前扫描࿰c;找到相应位置并插入。

图片来自菜鸟教程 

代码讲解

def insert_sort(lst):

    for i in range(1,len(lst)):  # i表示摸到的牌的下标

@R_673_5179@ tmp = lst[i] # tmp代表摸到的牌

@R_673_5179@ j = i - 1 # j代表的是手里的牌的下标࿰c;手上自动已有第一张牌

@R_673_5179@ while lst[j] > tmp and j >= 0: # 需要移动有序区牌的情况

@R_673_5179@     lst[j+1] = lst[j]

@R_673_5179@     j -= 1

@R_673_5179@ lst[j+1] = tmp  # lst[j+1]是用来存放要插入的牌

@R_673_5179@ print(f"第{i}趟的列表：{lst}")

 

lst1 = [3,2,5,8,6,9,7]

print(f"原列表{lst1}")

insert_sort(lst1)

# 结果原列表[3, 2, 5, 8, 6, 9, 7]

# 第1趟的列表：[2, 3, 5, 8, 6, 9, 7]

# 第2趟的列表：[2, 3, 5, 8, 6, 9, 7]

# 第3趟的列表：[2, 3, 5, 8, 6, 9, 7]

# 第4趟的列表：[2, 3, 5, 6, 8, 9, 7]

# 第5趟的列表：[2, 3, 5, 6, 8, 9, 7]

# 第6趟的列表：[2, 3, 5, 6, 7, 8, 9]

插入排序时间复杂度：O(n2)

---

冒泡排序、选择排序、插入排序小总结

1.三种排序方法的时间复杂度都是O(n2)

2.三种算法都属于原地排序࿰c;为创建新的列表

3.效率较低

思考：三种算法效率如何体现

现在利用装饰器࿰c;以冒泡排序为例子计算一下运算时间

from runtime import *

 

@runtime

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟

@R_673_5179@ exchange = false  # 每一趟做标记

@R_673_5179@ for j in range(len(lst)-i-1):  # 表示箭头

@R_673_5179@     if lst[j] > lst[j+1]: # 此时是升序排序࿰c;>改为<则改为了降序

@R_673_5179@@R_673_5179@  lst[j],lst[j+1] = lst[j+1],lst[j]

@R_673_5179@@R_673_5179@  exchange = True  # 进行了交换࿰c;exchange标记为Ture

@R_673_5179@ # print(f"第{i+1}趟后的列表为：{lst}")  # 查看排序过程

@R_673_5179@ if not exchange: # 如果没有进行交换࿰c;直接返回࿰c;优化的步骤

@R_673_5179@     return

 

lst = list(range(10000))

random.shuffle(lst)

bubble_sort(lst)

# 结果

# bubble_sort执行用时12.76702880859375s

我们发现当列表长度比较长时࿰c;冒泡排序需要的时间很长（相对于机器的运算）

那么是否有时间复杂度更低的排序算法呢？

答案是肯定有的࿰c;明天超超来解密！