定义一最大长度为20的结构体数组（可以在结构体中只定义关键字域），从键盘输入结构体数组各元素的关键字值，以输入-9999为结束，对该数组中的元素按关键字非递减的顺序进行排序，分别用冒泡排序，非递归的快速排序，递归的快速排序方法完成，再用折半查找方法对已经有序的结构体数组进行操作，输入一待查记录关键字，若查找成功输出“success”,查找不成功则输出“unsuccess”，以上各功能模块均用函数实现。设计相应算法并分析各排序方法的效率。
该程序运行情况举例说明：
运行主界面如下图所示：提示用户输入相应选项，键入数字1则进行待排序数据值的输入；键入数字2直接插入排序；键入数字3进行直接选择排序；键入数字4则进行冒泡排序；键入数字5则进行递归的快速排序；键入数字6则进行折半查找；键入数字7显示元素序列；键入数字0程序退出。
基本要求：
1、写出完成实验内容的实验方法和源代码。
2、写出实验数据及运行结果。
3、写出在实验过程中所遇到的问题及解决办法。
实验方法：
- 本次实验使用JAVA语言实现
- 因为测试数据量太小不能看出几种排序算法的效率如何，所以在用户自己输入测试数据的基础上，还增加了一个测试数组，测试数组由java提供的Random()方法实现，测试的大小由用户输入确定、数字大小范围是1-100000。
- 因为觉得输入以-9999结尾比较麻烦，所以做了一点小改进：用户输入数字空格分隔，回车确定创建整型数组通过先创建一个ArrayList集合,先将数字保存最后转成int[],利用集合的扩容机制就避免了空间浪费，输入则设置两个Scanner, 第一个以行为单位读取数据，这样就相当于是用回车（enter）当作结束符，然后把读取到的字符串传入第二个Scanner，然后在进行处理。
- 使用System类里面的currentTimeMillis方法，记录每次排序的时间。
实验源代码
package 查找排序;
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Random;
//创建测试数组
class TestArray {
public static int[] creat(int n) {
int[] array = new int[n];
for (int i = 0; i < n; i++)
{
array[i] = new Random().nextInt(100000);
}
return array;
}
}
//创建数组
class CreatArray {
public static int[] creat() {
ArrayList arrayList = new ArrayList();//创建ArrayList，先将数字保存最后转成int[],利用集合的扩容机制就避免了空间浪费
Scanner in = new Scanner(System.in);
String line = in.nextLine(); //设置两个Scanner 第一个以行为单位读取数据，这样就相当于是用回车（enter）当作结束符，
Scanner in2 = new Scanner(line); //然后把读取到的字符串传入第二个Scanner， 然后在进行处理
while (in2.hasNextInt()) { //输入以回车结尾
arrayList.add(in2.nextInt());
}
return arrayList.stream().mapToInt(Integer::valueOf).toArray();//将ArrayList转换成int[]
}
}
//冒泡排序
class BubbleSort {
public static void sort(int[] array)
{
long startTime = System.currentTimeMillis(); //记录执行时间
int i, j, temp;
boolean t = true;
for (i = 0; i < array.length; i++)
{
for (j = 0; j < array.length - i - 1 && t; j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
t = true;
}
}
}
System.out.println("冒泡排序成功");
Print.print(array);
long endTime = System.currentTimeMillis();
System.out.println("冒泡排序执行耗时 : " + (endTime - startTime) + " 毫秒 ");
}
}
//快速排序
class QuickSort {
public static void sorttime(int[] array)
{
int head = 0, tail = array.length - 1;
long startTime = System.currentTimeMillis(); //记录执行时间
sort(array, head, tail);
System.out.println("快速排序成功");
Print.print(array);
long endTime = System.currentTimeMillis();
System.out.println("快速排序执行耗时 : " + (endTime - startTime) + " 毫秒 ");
}
public static int[] sort(int[] array, int head, int tail) {
int temp = array[head];
int i = head;
int j = tail;
while (i < j) {
while (array[j] > temp && j > i) {
j--;
}
while (array[i] < temp && j > i) {
i++;
}
if ((array[i] == array[j] && i < j))
i++;
else {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
if (i - 1 > head)
array = sort(array, head, i - 1);
if (j + 1 < tail)
array = sort(array, j + 1, tail);
return array;
}
}
//直接插入排序
class InsertSort {
public static void sort(int[] array) {
long startTime = System.currentTimeMillis();
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
System.out.println("直接插入排序成功");
Print.print(array);
long endTime = System.currentTimeMillis();
System.out.println("直接插入排序执行耗时 : " + (endTime - startTime) + " 毫秒 ");
}
}
//直接选择排序
class SelectSort {
public static void sort(int[] array) {
long startTime = System.currentTimeMillis();
int temp, Kmin;
for (int i = 0; i < array.length - 1; i++) {
Kmin = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[Kmin])
Kmin = j;
}
if (Kmin != i) {
temp = array[i];
array[i] = array[Kmin];
array[Kmin] = temp;
}
}
System.out.println("直接选择排序成功");
Print.print(array);
long endTime = System.currentTimeMillis();
System.out.println("冒泡排序执行耗时 : " + (endTime - startTime) + " 毫秒 ");
}
}
//二分查找
class HalfFound {
public static void found(int[] array, int num)
{
long startTime = System.currentTimeMillis();
Arrays.sort(array);
int left = 0, right = array.length - 1; //左右指针
while (left < right)//左边的数大于右边的数循环终止
{
int mid = (left + right) >> 1;
//要找的数在中点左边
if (num < array[mid])
{
right = mid - 1;
}
else if (num > array[mid]) //要找的数在中点右边
{
left = mid + 1;
}
//否则找到了，直接跳出
else
{
System.out.println("找到了是第" + (mid + 1) + "个元素");
break;
}
}
if (left > right)
{
System.out.println("找不到元素");
}
System.out.println("二分查找耗时 : " + (System.currentTimeMillis() - startTime) + " 毫秒 ");
}
}
//打印顺序
class Print {
public static void print(int[] array)
{
for (int j : array) {
System.out.print(j + " ");
}
System.out.println();
}
}
//主方法
public class sort {
public static void main(String[] args) {
int choice = -1;
int[] array = null;
Scanner = new Scanner(System.in);
while (choice != 0)
{
System.out.println("主菜单如下");
System.out.println("1.创建测试数组");
System.out.println("2.输入待排序元素值");
System.out.println("3.直接插入排序");
System.out.println("4.直接选择排序");
System.out.println("5.冒泡排序");
System.out.println("6.递归的快速排序");
System.out.println("7.折半查找");
System.out.println("8.显示元素序列");
System.out.println("0.退出");
System.out.println("输入你的选择");
choice = scanner.nextInt(); //NoSuchElementException异常 ，因为调用函数scanner.close()了
switch (choice)
{
case 1:
System.out.println("输入生成测试数组的大小");
int num = scanner.nextInt();
array = TestArray.creat(num);
Print.print(array);
break;
case 2:
System.out.println("输入待排序的元素值");
array = CreatArray.creat();
break;
case 3:
InsertSort.sort(Arrays.copyOf(array, array.length));
break;
case 4:
SelectSort.sort(Arrays.copyOf(array, array.length));
break;
case 5:
BubbleSort.sort(Arrays.copyOf(array, array.length));
break;
case 6:
QuickSort.sorttime(Arrays.copyOf(array, array.length));
break;
case 7:
System.out.println("输入你要查找的值");
int temp = scanner.nextInt();
HalfFound.found(array, temp);
break;
case 8:
System.out.println("元素序列如下");
Print.print(array);
break;
case 0:break;
default:
System.out.println("不存在此选项，请重新选择");
}
}
scanner.close();
}
实验过程：
下面均是由生成的随机数数组来测试，暂不输入测试。
测试数据：数组大小20000 数字范围1-100000
创建测试数组：
直接插入排序：（55毫秒）
直接选择排序(148毫秒)
冒泡排序（389毫秒）
快速排序（31毫秒）
二分查找（4毫秒）
因为数据量太大，就不输出元素序列了。
实验过程中遇到的问题：
- 数组创建：因为数组大小是固定的，而我想实现创建数组像集合那样自动扩容，切输入数据时以空格分隔，回车结尾
解决方法：首先创建ArrayList用来存储数字，然后用toArray方法，但此时又有一个问题，toArray转换出来的是Object[ ]类型的，还需要把Object[ ]转换成int[ ],最后通过arrayList.stream().mapToInt(Integer::valueOf).toArray();实现。输入则设置两个Scanner, 第一个以行为单位读取数据，这样就相当于是用回车（enter）当作结束符，然后把读取到的字符串传入第二个Scanner，然后在进行处理。
- 测试数组：因为想到当数据量小的时候，几种排序算法的差别不大，且受到LeetCode上面的题启发（上面测试数组都是非常大的），便想到生成随机数的方法生成随机数组，但这种方法会生成相同的数字，用于排序并不影响，但如果用于其他比如要随机选出班上一定人数的人就必须生成不重复的数，就先遍历数组顺序赋值，再通过洗牌算法完全打乱，此方法用到这里也可以，但没有必要。
