利用随机函数产生N个随机整数，对这些数进行多种方法进行排序

Question

至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
最好带注解的，免得我有些地方看不懂

Answer 1

给你个代码：
/*
利用随机函数产生N个随机整数，对这些数进行多种方法进行排序
*/
#include <stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 10000
void main()
{
int i,j,k,n;
int n1,t;
int a[N],b[N];
FILE *fp;
clock_t start,finish;
int time1,time2,time3;
printf("输入要产生的随机数个数:");
scanf("%d",&n);
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
a[i]=rand();
for(i=0;i<n;i++)b[i]=a[i];
printf("**************************\n");
printf("\t插入排序\n");
printf("**************************\n");
start=clock();
for(i=1;i<n;i++)
{
t=b[i];
for(j=i-1;j>=0&&t<b[j];j--)
b[j+1]=b[j];
b[j+1]=t;
}
finish=clock();
time1=finish-start;
printf("插入排序耗时%d毫秒!\n\n\n",time1);
fp=fopen("output1.txt","w");
for(i=0;i<n;i++)
fprintf(fp,"%d ",b[i]);
fclose(fp);

for(i=0;i<n;i++)b[i]=a[i];
printf("**************************\n");
printf("\t选择排序\n");
printf("**************************\n");
start=clock();
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(b[k]>b[j])k=j;
t=b[i];
b[i]=b[k];
b[k]=t;
}
finish=clock();
time2=finish-start;
printf("选择排序耗时%d毫秒!\n\n\n",time2);
fp=fopen("output2.txt","w");
for(i=0;i<n;i++)
fprintf(fp,"%d ",b[i]);
fclose(fp);

for(i=0;i<n;i++)b[i]=a[i];
printf("**************************\n");
printf("\t冒泡排序\n");
printf("**************************\n");
start=clock();
n1=n-1;
while(n1>0)
{
j=0;
for(i=0;i<n1;i++)
if(b[i]>b[i+1])
{
t=b[i];
b[i]=b[i+1];
b[i+1]=t;
j=i;
}
n1=j;
}
finish=clock();
time3=finish-start;
printf("冒泡排序耗时%d毫秒!\n\n\n",time3);
fp=fopen("output3.txt","w");
for(i=0;i<n;i++)
fprintf(fp,"%d ",b[i]);
fclose(fp);
}

运行结果：
输入要产生的随机数个数:10000
**************************
插入排序
**************************
插入排序耗时125毫秒!

**************************
选择排序
**************************
选择排序耗时203毫秒!

**************************
冒泡排序
**************************
冒泡排序耗时485毫秒!

Press any key to continue

Answer 2

快速排序 最好 这个是测试结果 当基数很大时，可以看出他的优势
输入要产生的随机数个数:100000
**************************
插入排序
**************************
插入排序耗时14844豪妙!

**************************
选择排序
**************************
选择排序耗时18093豪妙!

**************************
冒泡排序
**************************
冒泡排序耗时71797豪妙!

**************************
快速排序
**************************
快速排序耗时32豪妙!

Answer 3

import java.io.RandomAccessFile;
import java.util.Vector;

import sun.misc.Sort;

public class TestSort {

/**
* @param args
*/
public static void main(String[] args) {
try {
//创建对象
Vector arr = new Vector();
String strs="";
int count=10000;
for (int i = 0; i < count; i++) {
arr.add(i + 1); //把 1-9 存入
}
for (int i = 0; i < count; i++) {
int id=(int)(Math.random()*count);//随即取里面的数值 count控制随即大小
strs+=arr.get(id)+",";
arr.remove(id); //删除已经取走的值
count--;
}
Long d=0l;
strs="";
Long s1= sort1(arr);
d=s1;
strs="方法2,方法3 最快";
Long s2= sort2(arr);
if(d<s2){
d=s2;
strs="方法1,方法3 最快";
}
Long s3= sort3(arr);
if(d<s3){
strs="方法1,方法2 最快";
}
System.out.println(strs+" \n排序ok!已经生成文件到指定位置!");
} catch (Exception e) {
e.printStackTrace();
}
}

/**
* 方法1 这是选择排序：选择最小的和第i个交换
*/
private static Long sort1(Vector arr) {
try{
String str="";
Long temp = 0l;
long dstart = System.currentTimeMillis();
for (int i = 0; i < arr.size() - 1; i++) {
for (int j = i + 1; j < arr.size(); j++) {
if (Long.parseLong(arr.get(i).toString()) > Long.parseLong(arr.get(j).toString())) {
temp = Long.parseLong(arr.get(j).toString());
arr.add(j, arr.get(i));
arr.add(i, temp);
}
}
}
long dend = System.currentTimeMillis();
System.out.println("选择排序算法用时：" + (dend - dstart) +" 毫秒");
for(int i=0; i<arr.size(); i++){
//System.out.print(arr.get(i)+",");
str=str+arr.get(i)+",";
}
RandomAccessFile rf1=new RandomAccessFile("E:\\tt\\sort1.txt", "rws");
rf1.write(str.getBytes("GB2312"));//把数据写到文件里 如果该文件存在 就会在文件的内容后面 追写进去内容,不存在就新建一个文件写内容
rf1.close();//关闭流
return (dend - dstart);
}catch(Exception e){
e.printStackTrace();
return 0l;
}
}

/**
* 方法2 冒泡排序算法实现
*/
private static Long sort2(Vector arr) {
try {
String str = "";
Long temp = 0l;
long dstart = System.currentTimeMillis();
for (int i = 0; i < arr.size() - 1; i++) {
for (int j = 0; j < arr.size() - i - 1; j++) {
if (Long.parseLong(arr.get(j).toString()) > Long.parseLong(arr.get(j + 1).toString())) {
temp = Long.parseLong(arr.get(j).toString());
arr.add(j, arr.get(j + 1));
arr.add(j + 1, temp);
}
}
}
long dend = System.currentTimeMillis();
System.out.println("冒泡排序算法用时：" + (dend - dstart)+" 毫秒");
for (int i = 0; i < arr.size(); i++) {
// System.out.print(arr.get(i)+",");
str = str + arr.get(i) + ",";
}
RandomAccessFile rf2 = new RandomAccessFile("E:\\tt\\sort2.txt","rws");
rf2.write(str.getBytes("GB2312"));
rf2.close();// 关闭流
return (dend - dstart);
}catch(Exception e){
e.printStackTrace();
return 0l;
}
}
/**
* 方法3 插入排序算法实现
*/
private static Long sort3(Vector arr) {
try{
String str="";
int searchCount = 0;
long dstart = System.currentTimeMillis();
for (int out = 1; out < arr.size(); out++) {
System.out.println();// 不要注释这句话 就可以看到方法3的执行时间
if (Long.parseLong(arr.get(out).toString()) > Long.parseLong(arr.get(out-1).toString())) {
continue;
}
int start = 0;
int end = out - 1;
while (start <= end) {
searchCount++;
int searchIndex = (start + end) / 2;
if (Long.parseLong(arr.get(out).toString()) > Long.parseLong(arr.get(searchIndex).toString())) {
start = searchIndex + 1;
} else if (Long.parseLong(arr.get(out).toString()) < Long.parseLong(arr.get(searchIndex).toString())) {
if (searchIndex == 0 || (searchIndex != 0 && Long.parseLong(arr.get(out).toString())> Long.parseLong(arr.get(searchIndex - 1).toString()))){//移动数据
Long changeTemp = Long.parseLong(arr.get(out).toString());
for (int i = out; i > searchIndex; i--) {
arr.add(i, arr.get(i - 1));
}
arr.add(searchIndex, changeTemp);
break;
} else {
end = searchIndex - 1;
continue;
}
} else {//移动数据
Long changeTemp = Long.parseLong(arr.get(out).toString());
for (int i = out; i > searchIndex; i--) {
arr.add(i, arr.get(i - 1));
}
arr.add(searchIndex, changeTemp);
break;
}
}
}
long dend = System.currentTimeMillis();
System.out.println("插入排序算法用时：" + (dend - dstart)+" 毫秒");

for(int i=0; i<arr.size(); i++){
str=str+arr.get(i)+",";
// System.out.print(arr.get(i)+",");
}
RandomAccessFile rf3=new RandomAccessFile("E:\\tt\\sort3.txt", "rws");
rf3.write(str.getBytes("GB2312"));
rf3.close();//关闭流
return (dend - dstart);
}catch(Exception e){
e.printStackTrace();
return 0l;
}
}

}

Answer 4

楼上的回答正确，我这周的课设就是这个题目