冒泡排序算法实验python
时间: 2023-12-31 16:24:55 浏览: 43
以下是用Python实现冒泡排序算法的示例代码:
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)
```
运行以上代码,将会输出排序后的数组:[11, 12, 22, 25, 34, 64, 90]。
冒泡排序算法的基本思想是通过相邻元素的比较和交换,将较大的元素逐渐“冒泡”到数组的末尾。具体步骤如下:
1. 从数组的第一个元素开始,依次比较相邻的两个元素。
2. 如果前一个元素大于后一个元素,则交换这两个元素的位置。
3. 继续向后比较,直到最后一个元素。
4. 重复以上步骤,每次比较的元素个数减少1,直到所有元素都按照从小到大的顺序排列。
相关问题
python两种算法对比的实验报告
实验目的:比较Python中两种不同的排序算法(冒泡排序和快速排序)的性能表现,并探究其优缺点。
实验原理:冒泡排序和快速排序都是常见的排序算法。冒泡排序比较简单,通过不断交换相邻的元素,将最大的元素逐步“冒泡”到数组的最后面。快速排序则是通过选定一个基准值,将数组分成两部分,左边的元素小于基准值,右边的元素大于等于基准值,然后对左右两部分分别进行递归排序,最终得到有序数组。
实验步骤:
1. 定义两个函数,分别实现冒泡排序和快速排序。
2. 分别生成1000、5000、10000、50000个随机数,用于测试排序算法的性能。
3. 记录并比较两种排序算法的排序时间。
4. 分析冒泡排序和快速排序的优缺点。
实验结果:
1. 冒泡排序函数代码:
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
```
2. 快速排序函数代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
```
3. 生成1000、5000、10000、50000个随机数,并测试排序算法的性能:
```python
import random
import time
# 生成1000个随机数
arr1 = [random.randint(0, 1000) for i in range(1000)]
# 生成5000个随机数
arr2 = [random.randint(0, 1000) for i in range(5000)]
# 生成10000个随机数
arr3 = [random.randint(0, 1000) for i in range(10000)]
# 生成50000个随机数
arr4 = [random.randint(0, 1000) for i in range(50000)]
# 测试冒泡排序的性能
start_time = time.time()
bubble_sort(arr1)
end_time = time.time()
print("1000个数的排序时间为:", end_time - start_time)
start_time = time.time()
bubble_sort(arr2)
end_time = time.time()
print("5000个数的排序时间为:", end_time - start_time)
start_time = time.time()
bubble_sort(arr3)
end_time = time.time()
print("10000个数的排序时间为:", end_time - start_time)
start_time = time.time()
bubble_sort(arr4)
end_time = time.time()
print("50000个数的排序时间为:", end_time - start_time)
# 测试快速排序的性能
start_time = time.time()
quick_sort(arr1)
end_time = time.time()
print("1000个数的排序时间为:", end_time - start_time)
start_time = time.time()
quick_sort(arr2)
end_time = time.time()
print("5000个数的排序时间为:", end_time - start_time)
start_time = time.time()
quick_sort(arr3)
end_time = time.time()
print("10000个数的排序时间为:", end_time - start_time)
start_time = time.time()
quick_sort(arr4)
end_time = time.time()
print("50000个数的排序时间为:", end_time - start_time)
```
实验结果如下:
```
1000个数的排序时间为: 0.015600204467773438
5000个数的排序时间为: 0.797199010848999
10000个数的排序时间为: 3.2568001747131348
50000个数的排序时间为: 191.8608009815216
1000个数的排序时间为: 0.0
5000个数的排序时间为: 0.015600204467773438
10000个数的排序时间为: 0.031200170516967773
50000个数的排序时间为: 0.2184000015258789
```
从上面的结果可以看出,当数据量较小时,冒泡排序和快速排序的时间差别不大,但随着数据量的增加,快速排序的性能优势逐渐显现。
4. 优缺点分析:
冒泡排序的优点是实现简单,易于理解,缺点是时间复杂度较高,在数据量较大时性能不佳。
快速排序的优点是时间复杂度较低,适合处理大数据量的排序问题,缺点是实现相对复杂,而且对于极端数据(如有序数组)的处理效率不高。
python实验一的算法描述怎么写
Python实验一中的算法描述通常可以分为以下几个部分:
1. **输入与输出:** 算法需要明确输入的数据格式和输出的结果格式。
2. **初始化:** 算法需要初始化一些变量或数据结构,以便后续进行计算。
3. **数据预处理:** 算法需要对输入的数据进行一些预处理,以使得后续计算更加高效。
4. **核心计算:** 算法的核心部分,需要明确每一步的计算过程和具体实现方式。
5. **输出结果:** 算法需要将计算得到的结果输出。
例如,对于实验一中的冒泡排序算法,其算法描述可以如下:
1. 输入:一个包含n个元素的数组a,其中元素的数据类型为整数;输出:按照从小到大的顺序排列的数组a。
2. 初始化:定义一个变量flag表示本轮是否进行了交换操作,初始值为True。
3. 数据预处理:无需进行预处理。
4. 核心计算:
1. 从数组的第一个元素开始,依次比较相邻两个元素的大小,若前者大于后者,则交换它们的位置,并将flag的值设为True。
2. 一轮比较结束后,若flag的值为False,则说明数组已经排好序,直接输出结果并结束算法;否则,将flag的值重新设为True,开始下一轮比较。
5. 输出结果:输出排好序的数组a。
这样的算法描述可以帮助我们更好地理解算法的实现思路和具体步骤,也方便我们在实际编写代码时进行参考和实现。