选择排序算法实验报告.docx

算法设计与分析基础
实验报告

应用数学学院

姓名：

学号：

班级：

二零一六年六月

实验 选择排序算法
一、实验性质 设计
二、实验学时 14学时
三、实验目的
1、掌握选择排序的方法和原理。
2、掌握java语言实现该算法的一般流程。
四、实验内容
1、数组的输入。
2、输入、输出的异常处理。
3、选择排序的算法流程。
4、运行结果的输出。
五、实验报告
Ⅰ、算法原理
首先扫描整个列表，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。然后从第二个元素开始扫描列表，找到最后n-1个元素中的最小元素，在和第二个元素交换位置，把第二小的元素放在它的最终位置上。一般来说，在对该列表做第i次扫描的时候（i的值从0到n-2），该算法在最后n - i个元素中寻找最小元素，然后拿它和Ai交换，在n-1遍以后就被排序好了。
Ⅱ、书中源代码
算法 SelectionSort(A[0..n-1])
//该算法用选择排序对给定的数组排序
//输入：一个可排序数组A[0..n-1]
//输出：升序排列的数组A[0..n-1]
for i ← 0 to n-2 do
min ← i
for j ← i+1 to n-1 do
if A[j] < A[min] min ← j
swap A[i] and A[min]

Ⅲ、Java算法代码：
import java.util.*;

public class Xuanze {
public static void main(String[] args) {
int n = 5;
int a[] = new int[n];
int i = 0, j = 0;
int sm = 0, min = 0;
System.out.println("请输入一组数字：");
Scanner sc = new Scanner(System.in);
try {
while (i <n) {
a[i]=sc.nextInt();
i++;
}
for (i = 0; i <= n - 2; i++) {
min = i;
for (j = i+1;j<=n-1; j++) {
if (a[j] < a[min]) {
min=j;
}
}
sm = a[min];
a[min] = a[i];
a[i] = sm;
}
System.out.println("选择排序输出结果为：");
for (i = 0; i < n; i++) {
System.out.println(a[i]);
}
} catch (Exception e) {
System.out.println(e);
}

}
}
Ⅳ、运行结果显示：

图（1） 图（2）
Ⅴ、实验结论：
选择排序是一个Θ（n2）的算法，键的交换次数仅为Θ（n）。或者是n-1次。择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

实验三 折半查找算法
一、实验性质 设计
二、实验学时 14学时
三、实验目的
1、掌握折半查找算法的方法和原理。
2、掌握java语言实现该算法的一般流程。
四、实验内容
1、给定一个数组。
2、输入、输出的异常处理。
3、折半查找的算法流程。
4、运行结果的输出。
五、实验报告
Ⅰ、算法原理
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~ax，要查找的数是K,通过比较查找键K和数组中间元素A[m]来完成查找工作。如果他们相等，算法结束，否则，如果K<A[m],就最数组的前半部分执行该操作，如果K>A[m],则对数组的后半部分执行该操作。
Ⅱ、书中源代码
算法 BinarySearch(A[0..n-1],K)
//实现非递归的折半查找
//输入：一个可排序数组A[0..n-1]和一个查找键K
//输出：一个数组的下标，该元素等于K；如果没有该元素，则返回-1
l ← 0; r ← n - 1
while l ≤ r do
m ← [ (l+r)/2]
if K = A[m] return m
else if K < A[m] r ← m-1
else l ← m+1
return -1
Ⅲ、Java算法代码：
import java.util.*;

public class Zheban {
public static void main(String args[]) {
int k = 0, i = 0, m = 0;
int a[] = {15,25,36,98,108,250,360,782};
int s = a.length-1;
System.out.println("请输入一个需要查找的数字：");
Scanner sc = new Scanner(System.in);
try{
k = sc.nextInt();
while (i<=s) {
m=(int)((i+s)/2);
if (k == a[m]) {
System.out.print("该数字在数组中的下标为："+m);
System.exit(-1);
}
else if (k < a[m]){
s = m - 1;
}
else{
i=m+1;
}
}
System.out.println(-1);
}catch(Exception es){
System.out.println(es);
}
}
Ⅳ、运行结果显示：

图（1） 图（2）
Ⅴ、实验结论：
折半查找的最差效率属于集合Θ(logn), 就依赖键值比较操作的查找算法来说，折半查找已经是一种最优的查找算法了。