实验12排序算法的程序实现

查找和排序算法实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的查找和排序算法，通过实际编程实现和性能比较，分析不同算法在不同数据规模和数据分布情况下的效率和优劣，为在实际应用中选择合适的算法提供依据。

二、实验环境本次实验使用的编程语言为 Python 3x，开发环境为 PyCharm。

实验中使用的操作系统为 Windows 10。

三、实验内容（一）查找算法1、顺序查找顺序查找是最基本的查找算法，从数组的一端开始，逐个比较元素，直到找到目标元素或遍历完整个数组。

｀｀｀pythondef sequential_search(arr, target)：for i in range(len(arr)）：if arri ＝＝ target:return ireturn －1｀｀｀2、二分查找二分查找要求数组是已排序的。

通过不断将数组中间的元素与目标元素比较，缩小查找范围，直到找到目标元素或确定目标元素不存在。

｀｀｀pythondef binary_search(arr, target)：low ＝ 0high ＝ len(arr) 1while low ＜＝ high:mid ＝（low ＋ high) ／／ 2if arrmid ＝＝ target:return midelif arrmid ＜ target:low ＝ mid ＋ 1else:high ＝ mid 1return －1｀｀｀（二）排序算法1、冒泡排序冒泡排序通过反复比较相邻的元素并交换位置，将最大的元素逐步“浮”到数组的末尾。

｀｀｀pythondef bubble_sort(arr)：n ＝ len(arr)for i in range(n)：for j in range(0, n i 1)：if arrj ＞ arrj ＋ 1 ：arrj, arrj ＋ 1 ＝ arrj ＋ 1, arrj｀｀｀2、插入排序插入排序将未排序的元素逐个插入到已排序的部分中，保持已排序部分始终有序。

快速排序算法c语言实验报告冒泡法和选择法排序C程序实验报告实验六：冒泡法排序物理学416班赵增月F12 2011412194日期：2013年10月31日一·实验目的 1.熟练掌握程序编写步骤；2.学习使用冒泡法和选择法排序；3.熟练掌握数组的定义和输入输出方法。

二·实验器材1.电子计算机；2.VC6.0三·实验内容与流程1.流程图（1）冒泡法(2)选择法 2.输入程序如下：（1）冒泡法#includestdio.h void main() { int a[10]; int i,j,t; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]); printf(\n); for(j=0;j9;j++)for(i=0;i9-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;i10;i++) printf(%d,a[i]); printf(\n); }（2）选择法#includestdio.h void main() { int a[10]; int i,j,t,k; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]);printf(\n); for(i=0;i9;i++) {k=i;for(j=i+1;j10;j++) if (a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t; }printf(排序后如下：\n); for(i=0;i10;i++)printf(%d,a[i]); printf(\n); }四．输出结果（1冒泡法）请输入10个数字：135****2468排序后如下：12345678910 （2）选择法输出结果请输入10个数字：135****6810排序后如下：12345678910五．实验反思与总结1.冒泡法和选择法是一种数组排序的方法，包含两层循环，写循环时，要注意循环变量的变化范围。

next i
•.
•3
练习1、下表中的原始数据是一组学生的军训打靶成绩， 若采用冒泡排序算法对其进行排序，则第1~4遍的排序 结果分别是（）
原始数据 98 95 85 93 88
第1遍
第2遍
第3遍
第4遍
•.
•4
2、陈晓峰和同学们去农科院开展研究性学习，大家都收获很大， 晓峰设计了一个Visual Basic程序，他把同学们收集到的水稻亩 产量和同学姓名已分别保存在数组a和数组b中，第i个同学收集 的亩产量保存在a(i)中，对应的同学姓名保存在b(i)中，最后按 亩产量从高到低进行排序。
Dim b(1 To n) As String
Private Sub Command1_Click()
Dim i As Integer, j As Integer, c As Single, t As String
For i = 1 To n

' 设共有n名同学
For j = n To i + 1 ①
8.0
7.0
9.0
k
8.5
8.0
7.0 8.0
k 8.5
9.0
7.0
7.0
i=3
8.0
8.0
8.5
k 8.5
9.0
9.0
•.
•9
程序：
for i=1 to 3 k=i for j=i+1 to 4 if d(k)>d(j) then k=j next j if k<>i then t=d(i) d(i)=d(k) d(k)=t endif
next i
•.
•10
练习1、下表中的原始数据是一组学生的军训打靶成绩， 若采用选择排序算法对其进行排序，则第1~4遍的排序 结果分别是（）

常见排序算法及其实现与分析排序算法在计算机科学中占据重要地位，它们能够对一系列的数据进行按照特定规则的排序，为我们提供了高效的数据处理方式。

本文将介绍几种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序，并对它们的实现与性能进行分析。

一、冒泡排序冒泡排序是一种简单的比较排序算法，它通过不断地交换相邻元素将最大（或最小）值“冒泡”到序列的一端。

其实现过程如下：1. 从序列的第一个元素开始，依次比较相邻的两个元素，若它们的顺序不符合要求，则交换它们的位置，将较大（或较小）的数往后移动。

2. 对剩下的元素重复上述步骤，直到整个序列有序。

冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

二、选择排序选择排序是一种简单直观的排序算法，它通过不断选择剩余元素中的最小（或最大）值，并将其放置在已排序序列末尾。

其实现过程如下：1. 在未排序序列中找到最小（或最大）元素，将其与未排序序列的第一个元素进行交换，将该元素置于已排序序列的末尾。

2. 对剩下的元素重复上述步骤，直到整个序列有序。

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

三、插入排序插入排序是一种简单直观的排序算法，它通过构建有序序列，对未排序序列中的元素逐个进行插入。

其实现过程如下：1. 将序列的第一个元素视为有序序列，从第二个元素开始依次将未排序序列中的元素插入到有序序列中的适当位置。

2. 对剩下的元素重复上述步骤，直到整个序列有序。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

四、快速排序快速排序是一种高效的排序算法，它采用分治的思想，通过将序列划分为较小和较大的子序列，分别对其进行排序。

其实现过程如下：1. 选取一个基准元素，通过一趟排序将序列划分为两个子序列，使得左子序列的所有元素小于等于基准元素，右子序列的所有元素大于等于基准元素。

2. 递归地对左右子序列进行快速排序，直到子序列的长度为1。