三大排序：冒泡、选择、插入

冒泡排序：

冒泡排序（Bubble Sort）是一种简单的排序算法。它通过比较相邻元素的大小，并交换它们的位置，使较大（或较小）的元素逐渐“浮”到数组的一端，从而实现排序的目的。

下面是冒泡排序的基本步骤：

1. 首先，从数组的第一个元素开始，依次比较相邻的两个元素。将较大（或较小）的元素交换到右侧，这样一次遍历之后，最大（或最小）的元素就会“浮”到数组的末尾。

2. 接下来，继续进行第一步的操作，但这次只需要遍历数组的前 n-1 个元素，其中 n 是数组的长度。这样一次遍历之后，第二大（或第二小）的元素会“浮”到数组的倒数第二个位置。

3. 重复上述步骤，每次遍历的元素个数减少一，直到只剩下一个元素为止。

4. 最后，经过多次遍历之后，数组中的元素就会按照从小到大（或从大到小）的顺序排列。

下面是一个示例，演示冒泡排序的过程：

假设我们有以下数组：[5, 3, 8, 2, 1]

第一次遍历：

• 比较 5 和 3：交换位置，数组变为 [3, 5, 8, 2, 1]
• 比较 5 和 8：位置不变
• 比较 8 和 2：交换位置，数组变为 [3, 5, 2, 8, 1]
• 比较 8 和 1：交换位置，数组变为 [3, 5, 2, 1, 8]

第二次遍历：

• 比较 3 和 5：位置不变
• 比较 5 和 2：交换位置，数组变为 [3, 2, 5, 1, 8]
• 比较 5 和 1：交换位置，数组变为 [3, 2, 1, 5, 8]

第三次遍历：

• 比较 3 和 2：交换位置，数组变为 [2, 3, 1, 5, 8]
• 比较 3 和 1：交换位置，数组变为 [2, 1, 3, 5, 8]

第四次遍历：

• 比较 2 和 1：交换位置，数组变为 [1, 2, 3, 5, 8]

经过四次遍历之后，数组就变为有序的：[1, 2, 3, 5, 8]。

冒泡排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。尽管冒泡排序在大规模数据集上的效率相对较低，但它是一种简单且容易理解的排序算法。

代码实现：

def Bubble_sort(li):for i in range(len(li) - 1):for j in range(0, len(li) - i - 1):if li[j] > li[j+1]:li[j], li[j+1] = li[j+1], li[j]return li

该算法的时间复杂度为O(n^2),同时为了减小计算时间有优化后的冒泡排序：

def Bubble_sort(li):exchange=Truefor i in range(len(li) - 1):for j in range(0, len(li) - i - 1):if li[j] > li[j+1]:li[j], li[j+1] = li[j+1], li[j]exchange=Trueif not exchange:return True

插入排序：

插入排序（Insertion Sort）是一种简单直观的排序算法，它的原理是逐步构建有序序列。插入排序的过程类似于打扑克牌时整理手中的牌。

下面是插入排序的基本步骤：

1. 假设我们有一个无序的数组，将该数组分为两个部分：已排序部分和未排序部分。初始时，已排序部分只包含数组的第一个元素，而未排序部分包含剩余的元素。

2. 从未排序部分取出第一个元素，将其与已排序部分的元素逐个比较。将该元素插入到已排序部分的正确位置，使得插入后的已排序部分仍然保持有序。

3. 重复上述步骤，直到未排序部分的所有元素都被插入到已排序部分中。

下面是一个示例，演示插入排序的过程：

假设我们有以下数组：[5, 3, 8, 2, 1]

第一次遍历：

• 取出未排序部分的第一个元素 3，将其与已排序部分的元素 5 比较。由于 3 小于 5，将 3 插入到 5 之前，已排序部分变为 [3, 5]。
• 数组变为 [3, 5, 8, 2, 1]

第二次遍历：

• 取出未排序部分的第一个元素 8，将其与已排序部分的元素逐个比较。由于 8 大于 5，不需要进行插入操作。
• 数组保持不变：[3, 5, 8, 2, 1]

第三次遍历：

• 取出未排序部分的第一个元素 2，将其与已排序部分的元素逐个比较。由于 2 小于 8，需要将 2 插入到 8 之前，已排序部分变为 [3, 5, 2, 8]。
• 数组变为 [3, 5, 2, 8, 1]

第四次遍历：

• 取出未排序部分的第一个元素 1，将其与已排序部分的元素逐个比较。由于 1 小于 8，需要将 1 插入到 8 之前，已排序部分变为 [3, 5, 2, 1, 8]。
• 数组变为 [3, 5, 2, 1, 8]

经过四次遍历之后，数组就变为有序的：[1, 2, 3, 5, 8]。

插入排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。尽管插入排序的性能在大规模数据集上比其他高级排序算法略逊一筹，但在小型或部分有序的数组上，插入排序的效率较高，并且它的实现较为简单

代码：

def Insert_sort(li):for i in range(1,len(li)):j=i-1tmp=li[i]while li[j]>tmp and j>=0:li[j+1]=li[j]j-=1    li[j+1]=tmp             return li    

选择排序：

选择排序（Selection Sort）是一种简单直观的排序算法。它的原理是在未排序部分中选择最小（或最大）的元素，并将其放置在已排序部分的末尾。选择排序的过程类似于在一组元素中不断选择最值的操作。

下面是选择排序的基本步骤：

1. 假设我们有一个无序的数组，将该数组分为两个部分：已排序部分和未排序部分。初始时，已排序部分为空，而未排序部分包含所有的元素。

2. 在未排序部分中找到最小（或最大）的元素，将其与未排序部分的第一个元素交换位置。这样，最小（或最大）的元素就被放置在已排序部分的末尾。

3. 重复上述步骤，每次从未排序部分选择一个最小（或最大）的元素，并将其放置在已排序部分的末尾。

4. 当未排序部分为空时，排序完成。

下面是一个示例，演示选择排序的过程：

假设我们有以下数组：[5, 3, 8, 2, 1]

第一次遍历：

• 在未排序部分中找到最小的元素 1，将其与未排序部分的第一个元素 5 交换位置。已排序部分变为 [1]，未排序部分变为 [5, 3, 8, 2]。
• 数组变为 [1, 3, 8, 2, 5]

第二次遍历：

• 在未排序部分中找到最小的元素 2，将其与未排序部分的第一个元素 3 交换位置。已排序部分变为 [1, 2]，未排序部分变为 [3, 8, 5]。
• 数组变为 [1, 2, 8, 3, 5]

第三次遍历：

• 在未排序部分中找到最小的元素 3，将其与未排序部分的第一个元素 8 交换位置。已排序部分变为 [1, 2, 3]，未排序部分变为 [8, 5]。
• 数组变为 [1, 2, 3, 8, 5]

第四次遍历：

• 在未排序部分中找到最小的元素 5，将其与未排序部分的第一个元素 8 交换位置。已排序部分变为 [1, 2, 3, 5]，未排序部分变为 [8]。
• 数组变为 [1, 2, 3, 5, 8]

经过四次遍历之后，数组就变为有序的：[1, 2, 3, 5, 8]。

选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。尽管选择排序的性能在大规模数据集上不如其他高级排序算法，但它是一种简单且容易实现的排序算法。

代码：

def select_sort(li):for i in range(len(li)-1)；min=ifor j in range(i+1,len(li))；if li[j]<li[min]:min=jli[i],li[min]=;i[min],li[i]