文档介绍：算法设计与分析基础
实验报告
应用数学学院
姓名:
学号:
班级:
二零一六年六月
实验选择排序算法
一、实验性质设计
二、实验学时 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 .*;
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;
("请输入一组数字:");
Scanner sc = new Scanner();
try {
while (i <n) {
a[i]=();
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;
}
("选择排序输出结果为:");
for (i = 0; i < n; i++) {
(a[i]);
}
} catch (Exception e) {
(e);
}
}
}
Ⅳ、运行结果显示:
图(1) 图(2)
Ⅴ、实验结论:
选择排序是一个Θ(n2)的算法,键的交换次数仅为Θ(n)。或者是n-1次。择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有