企业网站为什么做优化,医疗网站建设行业现状,手机网站模板 优帮云,上海 网站开发 外包在数据处理和算法设计中#xff0c;排序是一项基础且重要的操作。本文将介绍两种经典的排序算法#xff1a;冒泡排序#xff08;Bubble Sort#xff09;和选择排序#xff08;Selection Sort#xff09;。我们将通过示例代码来演示这两种算法如何对列表进行升序排列。
一…在数据处理和算法设计中排序是一项基础且重要的操作。本文将介绍两种经典的排序算法冒泡排序Bubble Sort和选择排序Selection Sort。我们将通过示例代码来演示这两种算法如何对列表进行升序排列。
一. 冒泡排序
冒泡排序是一种简单的排序算法它重复地遍历待排序的列表比较相邻的元素并将顺序错误的元素进行交换。这个过程会一直进行直到没有需要交换的元素为止。
分析
冒泡排序是一种简单的排序算法主要思想是通过重复遍历待排序的列表比较相邻的元素并根据顺序交换它们。每次遍历后未排序部分的最大元素会“冒泡”到列表的末尾。因此算法得名为“冒泡排序”。
我们先拿到需要排序的列表 [ 10, 50 , 20, 60, 40, 30] 我们知道冒泡排序实现的原理以后可以自己在脑海里模拟计算机进行遍历排序
首先第一轮我们先拿数列第一个数据和第二个数据比较如果第二个数
比第一个数大就交换两个数据的位置。然后然后比较第二个数与第三个
数一直到比较完整个数列这时候数列最小的数就已经排在最后面了于
是后面每轮就不需要再与最后一个数据比较了。
然后后面每一轮都和第一轮一样只不过每轮结束下一轮都可以少比较一个数据。
我们需要比较的列表是[ 10, 50, 20, 60, 40, 30]那么我们每轮结束以后
够可以得到一个列表。
然后让我们模拟一下每一轮结束得到的列表应该是什么样的
第一轮 [50, 20, 60, 40, 30, 10]
第二轮 [50, 60, 40, 30, 20, 10]
第三轮 [60, 50, 40, 30, 20, 10] # 注意这里我们都可以看到其实数组的排序其实已经完成了
第四轮 [60, 50, 40, 30, 20, 10] # 但是计算机不是人类它只会按照程序运行继续比较。
第五轮 [60, 50, 40, 30, 20, 10]
冒泡排序的实现
以下是使用 Python 实现的冒泡排序代码排序列表 [10, 50, 20, 60, 40, 30]
# 冒泡排序 降序,升序将改成
l0 [10, 50, 20, 60, 40, 30]
total 0
count 0for i in range(len(l0) - 1):for j in range(len(l0) - i - 1):total 1 # 统计比较次数if l0[j] l0[j 1]: # 升序排序条件count 1 # 统计交换次数temp l0[j] # 交换元素l0[j] l0[j 1]l0[j 1] tempprint(f第{i 1}轮{l0})print(f比较了{total}次,数值互换了{count}次, l0)
运行结果
运行上述代码后输出结果如下:
第一轮 [50, 20, 60, 40, 30, 10]
第二轮 [50, 60, 40, 30, 20, 10]
第三轮 [60, 50, 40, 30, 20, 10]
第四轮 [60, 50, 40, 30, 20, 10]
第五轮 [60, 50, 40, 30, 20, 10]
比较了15次,数值互换了9次 [60, 50, 40, 30, 20, 10] 在这个例子中我们可以看到最终的排序结果是 [10, 20, 30, 40, 50, 60] 。在排序过程中总共进行了 15 次比较其中 9 次进行了值的交换。
二. 选择排序
选择排序是一种不稳定的排序算法它的基本思想是每一趟从未排序的部分中选择最小或最大的元素放到已排序序列的末尾直到所有元素都排好序。这种方法的时间复杂度为 O(n^2)。
分析
选择排序是一种简单的排序算法。它的基本思想是每次从未排序的部分中选择最小或最大的元素将其放到已排序部分的末尾。
我们先拿到需要排序的列表 [ 10, 50 , 20, 60, 40, 30] 我们知道选择排序实现的原理以后就像冒泡排序一样在脑海里模拟计算机进行遍历排序
首先我们定义一个循环外的变量max_index把它当作每轮未排序最大数值的索引第一轮我们先把数列第一个数据当作最大值把它的索引赋予max_index
然后比较l0[max_index]和第二个数据如果第二个数比第一个数大就把
第二个数的索引赋予max_index。然后,l0[max_index]与第三个数比较
一直到比较完整个数列这时候max_index就是数组最大数值的索引交换
数列中第一个数值与最大数值的位置。然后后面每一轮都和第一轮一样只不过每轮结束下一轮都可以少比较一个数据。
我们需要比较的列表是[ 10, 50, 20, 60, 40, 30]那么我们每轮结束以后就
可以得到一个列表。
然后让我们模拟一下每一轮结束得到的列表应该是什么样的
第1轮[60, 50, 20, 10, 40, 30]
第2轮[60, 50, 20, 10, 40, 30]
第3轮[60, 50, 40, 10, 20, 30]
第4轮[60, 50, 40, 30, 20, 10]
第5轮[60, 50, 40, 30, 20, 10]
选择排序的实现
以下是使用 Python 实现的选择排序代码对列表 [60, 10, 20, 50, 40, 30] 进行降序排序
# 选择排序 降序, 升序将改成
l0 [10, 50, 20, 60, 40, 30]
total 0
count 0for i in range(len(l0) - 1):max_index i # 假设未排序部分的第一个元素为最大值for j in range(i 1, len(l0)):total 1 # 记录比较次数if l0[max_index] l0[j]: # 寻找最大值max_index jcount 1 # 记录交换次数# 交换当前元素和找到的最大元素temp l0[i]l0[i] l0[max_index]l0[max_index] tempprint(f第{i 1}轮{l0})print(f比较了{total}次, 数值互换了{count}次, l0)
运行结果
运行上述选择排序的代码后输出结果如下
第1轮[60, 50, 20, 10, 40, 30]
第2轮[60, 50, 20, 10, 40, 30]
第3轮[60, 50, 40, 10, 20, 30]
第4轮[60, 50, 40, 30, 20, 10]
第5轮[60, 50, 40, 30, 20, 10]
比较了15次,数值互换了5次 [60, 50, 40, 30, 20, 10] 在这个例子中最终的排序结果是 [60, 50, 40, 30, 20, 10] 。在排序过程中总共进行了 15 次比较一共进行了5次值的交换。 三. 冒泡排序与选择排序比较
性能分析
时间复杂度:
冒泡排序的时间复杂度为 O(n²)最坏和平均情况下都是 O(n²)最佳情况下列表已排序为 O(n)。
选择排序的时间复杂度也是 O(n²)无论是最坏、平均还是最佳情况都是 O(n²)。
选择排序
比较次数在每一轮中选择排序需要遍历未排序的部分以找到最大值或最小值。对于长度为 (n) 的列表第一轮需要比较 (n-1) 次第二轮需要比较 (n-2) 次以此类推。因此总的比较次数为O(n^2)
交换次数每一轮最多只进行一次交换因此交换次数为 (O(n))。
冒泡排序
比较次数在每一轮中冒泡排序需要比较相邻的元素。对于长度为 (n) 的列表第一轮需要比较 (n-1) 次第二轮需要比较 (n-2) 次以此类推。总的比较次数同样为O(n^2)
交换次数在最坏的情况下每一次比较都需要进行交换因此交换次数也是 (O(n^2))。
空间复杂度: 冒泡排序是原地排序算法空间复杂度为 O(1)。 选择排序同样是原地排序算法空间复杂度也为 O(1)。
使用场景
冒泡排序: 1.因为其简单易懂适合教育和教学的场景帮助初学者理解排序的基本概念。 2.不适合处理大型数据集效率较低。
选择排序: 1.选择排序虽然也不适合处理大型数据集但在某些特定情况下例如数据基本有序时它可能会表现得比冒泡排序更好。 2.适合对小型数据集进行排序且实现简单。
四. 总结
通过本文的介绍我们了解了冒泡排序和选择排序这两种经典的排序算法。虽然它们在实际应用中并不常用因为有更高效的排序算法如快速排序和归并排序但它们在学习算法的过程中提供了良好的基础。
代码复用在实际开发中使用内置的排序函数会更加高效。例如Python 提供了内置的 sort() 方法和 sorted() 函数使用起来简单且效率高。
示例如下
# 使用 Python 内置的排序
l0 [10, 50, 20, 60, 40, 30]
l0.sort() # 原地排序
print(l0) # 输出[10, 20, 30, 40, 50, 60]l1 [60, 10, 20, 50, 40, 30]
sorted_l1 sorted(l1) # 返回新排序的列表
print(sorted_l1) # 输出[10, 20, 30, 40, 50, 60]
希望本文能够帮助你理解冒泡排序和选择排序的基本概念及其实现。如果你有任何问题欢迎在评论区讨论
