Question

利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序。

利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序。具体要求如下：
1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、选择排序、希尔排序、快速排序、合并排序、堆排序）。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

Answer 1

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 2

插入排序：
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 　　1. 从第一个元素开始，该元素可以认为已经被排序 　　2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 　　3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 　　4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 　　5. 将新元素插入到下一位置中 　　6. 重复步骤2