实验六：冒泡法排序物理学416班赵增月F12 2011412194 日期：2013年10月31日一·实验目的1.熟练掌握程序编写步骤；2.学习使用冒泡法和选择法排序；3.熟练掌握数组的定义和输入输出方法。
二·实验器材1.电子计算机；2.VC6.0三·实验内容与流程1.流程图（1）冒泡法(2)选择法2.输入程序如下：（1）冒泡法#include<stdio.h>void main(){int a[10];int i,j,t;printf("请输入10个数字：\n");for(i=0;i<10;i++)scanf("%d",&a[i]);printf("\n");for(j=0;j<9;j++)for(i=0;i<9-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}printf("排序后如下：\n");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");}（2）选择法#include<stdio.h>void main(){int a[10];int i,j,t,k;printf("请输入10个数字：\n");for(i=0;i<10;i++)scanf("%d",&a[i]);printf("\n");for(i=0;i<9;i++){k=i;for(j=i+1;j<10;j++)if (a[k]>a[j])k=j;t=a[i];a[i]=a[k];a[k]=t;}printf("排序后如下：\n");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");} 四．输出结果（1冒泡法）请输入10个数字：135****2468排序后如下：12345678910（2）选择法输出结果请输入10个数字：135****6810排序后如下：12345678910五．实验反思与总结1.冒泡法和选择法是一种数组排序的方法，包含两层循环，写循环时，要注意循环变量的变化范围。
一、实验目的1. 理解常见的排序算法及其原理。
2. 掌握排序算法的编程实现。
3. 比较不同排序算法的效率。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 实现以下排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序。
2. 对一组随机数进行排序，并记录排序过程。
3. 比较不同排序算法的运行时间。
四、实验步骤1. 定义一组随机数列表。
2. 实现冒泡排序、选择排序、插入排序、快速排序、归并排序算法。
3. 对随机数列表进行排序，并记录排序过程。
4. 使用time模块记录排序算法的运行时间。
5. 比较不同排序算法的运行时间。
五、实验结果与分析1. 随机数列表：[43, 21, 65, 56, 87, 29, 17, 58, 39, 74]2. 冒泡排序：排序过程：[43, 21, 65, 56, 87, 29, 17, 58, 39, 74][43, 21, 56, 65, 87, 29, 17, 58, 39, 74] ...[17, 21, 29, 39, 43, 56, 58, 65, 74, 87]运行时间：0.0009秒3. 选择排序：排序过程：[43, 21, 65, 56, 87, 29, 17, 58, 39, 74] [21, 43, 65, 56, 87, 29, 17, 58, 39, 74] [21, 43, 56, 65, 87, 29, 17, 58, 39, 74] ...[17, 21, 29, 39, 43, 56, 58, 65, 74, 87]运行时间：0.0011秒4. 插入排序：排序过程：[43, 21, 65, 56, 87, 29, 17, 58, 39, 74] [21, 43, 65, 56, 87, 29, 17, 58, 39, 74] [21, 43, 56, 65, 87, 29, 17, 58, 39, 74] ...[17, 21, 29, 39, 43, 56, 58, 65, 74, 87]运行时间：0.0008秒5. 快速排序：排序过程：[17, 21, 29, 39, 43, 56, 65, 58, 87, 74][17, 21, 29, 39, 43, 56, 65, 58, 74, 87]...[17, 21, 29, 39, 43, 56, 58, 65, 74, 87]运行时间：0.0005秒6. 归并排序：排序过程：[43, 21, 65, 56, 87, 29, 17, 58, 39, 74][17, 21, 29, 39, 43, 56, 65, 58, 74, 87]...[17, 21, 29, 39, 43, 56, 58, 65, 74, 87]运行时间：0.0004秒六、实验结论1. 通过本次实验，我们掌握了冒泡排序、选择排序、插入排序、快速排序、归并排序算法的编程实现。
一、实验目的1. 掌握排序算法的基本原理和实现方法。
2. 熟悉常用排序算法的时间复杂度和空间复杂度。
3. 能够根据实际问题选择合适的排序算法。
4. 提高编程能力和问题解决能力。
二、实验内容1. 实现并比较以下排序算法：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。
2. 对不同数据规模和不同数据分布的序列进行排序，分析排序算法的性能。
3. 使用C++编程语言实现排序算法。
三、实验步骤1. 冒泡排序：将相邻元素进行比较，如果顺序错误则交换，直到序列有序。
2. 插入排序：将未排序的元素插入到已排序的序列中，直到序列有序。
3. 选择排序：每次从剩余未排序的元素中选取最小（或最大）的元素，放到已排序序列的末尾。
4. 快速排序：选择一个枢纽元素，将序列分为两部分，一部分比枢纽小，另一部分比枢纽大，递归地对两部分进行排序。
5. 归并排序：将序列分为两半，分别对两半进行排序，然后将两半合并为一个有序序列。
6. 堆排序：将序列构建成一个最大堆，然后依次取出堆顶元素，最后序列有序。
四、实验结果与分析1. 冒泡排序、插入排序和选择排序的时间复杂度均为O(n^2)，空间复杂度为O(1)。
这些算法适用于小规模数据或基本有序的数据。
2. 快速排序的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)，空间复杂度为O(logn)。
快速排序适用于大规模数据。
3. 归并排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。
4. 堆排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。
五、实验结论1. 根据不同数据规模和不同数据分布，选择合适的排序算法。
2. 冒泡排序、插入排序和选择排序适用于小规模数据或基本有序的数据。
3. 快速排序、归并排序和堆排序适用于大规模数据。
4. 通过实验，加深了对排序算法的理解，提高了编程能力和问题解决能力。
六、实验总结本次实验通过对排序算法的学习和实现，掌握了常用排序算法的基本原理和实现方法，分析了各种排序算法的性能，提高了编程能力和问题解决能力。
一、实验目的1. 理解排序算法的基本原理和操作步骤。
2. 掌握几种常见的排序算法，如冒泡排序、选择排序、插入排序等。
3. 分析不同排序算法的时间复杂度和空间复杂度。
4. 实现排序算法，并进行性能测试。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容1. 冒泡排序2. 选择排序3. 插入排序4. 性能测试四、实验步骤1. 实现冒泡排序```pythondef 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. 实现选择排序```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i] return arr```3. 实现插入排序```pythondef insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr```4. 性能测试```pythonimport timedef test_sort_performance(sort_func, arr):start_time = time.time()sort_func(arr)end_time = time.time()return end_time - start_timearr = [64, 34, 25, 12, 22, 11, 90]print("原始数组：", arr)print("冒泡排序耗时：", test_sort_performance(bubble_sort, arr.copy()))print("选择排序耗时：", test_sort_performance(selection_sort,arr.copy()))print("插入排序耗时：", test_sort_performance(insertion_sort,arr.copy()))```五、实验结果与分析1. 冒泡排序耗时：0.000766秒2. 选择排序耗时：0.001023秒3. 插入排序耗时：0.000789秒从实验结果可以看出，冒泡排序、选择排序和插入排序在处理相同数据量时，耗时相差不大。
