排序算法效率比较（Java实训）

实训目的：

数组、Java API的应用

实训要求：

随机生成10000个10000以内的实数，分别用选择、冒泡、快速排序等算法进行排序，计算各种排序所需时间并比较算法的效率。

bubbleSort.java

package program4

//冒泡排序
public class bubbleSort {
	public void bubbleSort(double[] arr) {
		for (int i = 0 i < arr.length - 1 i++) {
			for (int j = 0 j < arr.length - 1 - i j++) {
				if (arr[j] > arr[j + 1]) {
					double temp = arr[j]
					arr[j] = arr[j + 1]
					arr[j + 1] = temp
				}
			}
		}
	}
}

quick_sort.java

package program4

//快速排序
public class quick_sort {
	public void quick_sort(double[] s, int l, int r) {
		if (l < r) {
			int i = l, j = r
			double x = s[l]
			while (i < j) {
				while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
					j--
				if (i < j)
					s[i++] = s[j]

				while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
					i++
				if (i < j)
					s[j--] = s[i]
			}
			s[i] = x
			quick_sort(s, l, i - 1) // 递归调用
			quick_sort(s, i + 1, r)
		}
	}
}

Test.java

package program4

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		double [] s=new double [100005]
		double [] t=new double [100005]
		double [] u=new double [100005]
		for(int i=0i<10000i++)
		{
			s[i]=(double) (Math.random()*100000)
			t[i]=u[i]=s[i]
		}
		long st1=System.currentTimeMillis()
		xuanzeSort x=new xuanzeSort()
		x.xuanzeSort(t)
		long end1=System.currentTimeMillis()
		System.out.println("选择排序耗时:"+(end1-st1))
		long st2=System.currentTimeMillis()
		bubbleSort b=new bubbleSort()
		b.bubbleSort(s)
		long end2=System.currentTimeMillis()
		System.out.println("冒泡排序耗时:"+(end2-st2))
		long st3=System.currentTimeMillis()
		quick_sort q=new quick_sort()
		q.quick_sort(u,0,9999)
		long end3=System.currentTimeMillis()
		System.out.println("快速排序耗时:"+(end3-st3))
	}

}

xuanzeSort.java

package program4

//选择排序
public class xuanzeSort {
	public void xuanzeSort(double[] array) {
		for (int i = 0 i < array.length i++) {
			int temp = i
			for (int j = i + 1 j < array.length j++) {
				if (array[temp] > array[j]) {
					temp = j
				}
				double t = array[temp]
				array[temp] = array[i]
				array[i] = t
			}
		}
	}
}

最后结果：