谁有qq网站开发资源群,廊坊seo排名公司,大连网站制作公司费用多少,卡二卡三卡四卡在线冒泡排序#xff1a;
冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法。它通过比较相邻元素的大小#xff0c;并交换它们的位置#xff0c;使较大#xff08;或较小#xff09;的元素逐渐“浮”到数组的一端#xff0c;从而实现排序的目的。
下面是冒…冒泡排序
冒泡排序Bubble Sort是一种简单的排序算法。它通过比较相邻元素的大小并交换它们的位置使较大或较小的元素逐渐“浮”到数组的一端从而实现排序的目的。
下面是冒泡排序的基本步骤 首先从数组的第一个元素开始依次比较相邻的两个元素。将较大或较小的元素交换到右侧这样一次遍历之后最大或最小的元素就会“浮”到数组的末尾。 接下来继续进行第一步的操作但这次只需要遍历数组的前 n-1 个元素其中 n 是数组的长度。这样一次遍历之后第二大或第二小的元素会“浮”到数组的倒数第二个位置。 重复上述步骤每次遍历的元素个数减少一直到只剩下一个元素为止。 最后经过多次遍历之后数组中的元素就会按照从小到大或从大到小的顺序排列。
下面是一个示例演示冒泡排序的过程
假设我们有以下数组[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[j1]:li[j], li[j1] li[j1], li[j]return li
该算法的时间复杂度为O(n^2),同时为了减小计算时间有优化后的冒泡排序
def Bubble_sort(li):exchangeTruefor i in range(len(li) - 1):for j in range(0, len(li) - i - 1):if li[j] li[j1]:li[j], li[j1] li[j1], li[j]exchangeTrueif not exchange:return True
插入排序 插入排序Insertion Sort是一种简单直观的排序算法它的原理是逐步构建有序序列。插入排序的过程类似于打扑克牌时整理手中的牌。
下面是插入排序的基本步骤 假设我们有一个无序的数组将该数组分为两个部分已排序部分和未排序部分。初始时已排序部分只包含数组的第一个元素而未排序部分包含剩余的元素。 从未排序部分取出第一个元素将其与已排序部分的元素逐个比较。将该元素插入到已排序部分的正确位置使得插入后的已排序部分仍然保持有序。 重复上述步骤直到未排序部分的所有元素都被插入到已排序部分中。
下面是一个示例演示插入排序的过程
假设我们有以下数组[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)):ji-1tmpli[i]while li[j]tmp and j0:li[j1]li[j]j-1 li[j1]tmp return li
选择排序
选择排序Selection Sort是一种简单直观的排序算法。它的原理是在未排序部分中选择最小或最大的元素并将其放置在已排序部分的末尾。选择排序的过程类似于在一组元素中不断选择最值的操作。
下面是选择排序的基本步骤 假设我们有一个无序的数组将该数组分为两个部分已排序部分和未排序部分。初始时已排序部分为空而未排序部分包含所有的元素。 在未排序部分中找到最小或最大的元素将其与未排序部分的第一个元素交换位置。这样最小或最大的元素就被放置在已排序部分的末尾。 重复上述步骤每次从未排序部分选择一个最小或最大的元素并将其放置在已排序部分的末尾。 当未排序部分为空时排序完成。
下面是一个示例演示选择排序的过程
假设我们有以下数组[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)minifor j in range(i1,len(li))if li[j]li[min]:minjli[i],li[min];i[min],li[i]
