时间排序_⼏种常见排序⽅法的实现及时间对⽐（JAVA）
⾸先贴出⼯具类
ArrayUtil:
import org.apachemons.lang3.time.StopWatch;
public class ArrayUtil {
//交换数组元素
public static void swap(Comparable[] array, int left, int right) {
Comparable tempValue = array[left];
array[left] = array[right];
array[right] = tempValue;
}
//⽐较元素
public static boolean less(Comparable v, Comparable w) {
return vpareTo(w) < 0;
}
//打印
public static void show(Comparable[] array) {
StringBuilder sb = new StringBuilder();
for (Comparable a : array) {
sb.append(a).append(" ");
}
System.out.println("排序后：" + sb.toString());
}
/
/判断是否有序
public static boolean isSort(Comparable[] array) {
for (int i = 1; i < array.length; i++) {
if (less(array[i], array[i - 1])) {
return false;
}
}
return true;
}
//选择排序⽅式，计算时间
public static double runTime(String method, Comparable[] array) throws Exception {        StopWatch watch = new StopWatch();
watch.start();
switch (method) {
case "Insertion": {
InsertSort.sort(array, 0, array.length);
break;
}java生成随机数的方法
case "Selection": {
SimpleSelectionSort.sort(array);
break;
}
case "Shell": {
ShellSort.sort(array);
break;
}
case "Quick": {
QuickSort.optimizeSort(array, 0, array.length - 1);
break;
}
//快速排序的三向切分
case "Quick3Way":{
QuickSort.quick3way(array,0,array.length-1);
break;
}
case "Heap": {
HeapSort.sort(array);
break;
}
case "Bubble": {
BubbleSort.sort(array);
break;
}
//⾃顶向下归并
case "Merge": {
Comparable[] aux = new Comparable[array.length];
break;
}
//⾃底向上归并
case "MergeBU": {
break;
}
default: {
throw new Exception("error");
}
}
watch.stop();
if (isSort(array)) {
NanoTime();
}
throw new RuntimeException(method+"排序不成功");
}
/**
* @param method 使⽤排序⽅法的名称
* @param count  ⽣成⼏组数据
* @param length 每组数据的长度
* @return total 平均使⽤时间单位ms
* @throws Exception e
*/
public static void timeRandomInput(String method, int count, int length) throws Exception {        double total = 0.0;
Comparable[] array = new Comparable[length];
for (int i = 0; i < count; i++) {
for (int j = 0; j < length; j++) {
array[j] = StdRandom.uniform() * 100;
}
total += runTime(method, array);
}
double ms = total/count/100000;
String formatMs = String.format("%.2f", ms);
System.out.println(method+" 平均运⾏时间:"+formatMs);
}
}
随机数⽣成类:
import java.util.Random;
/**
* 此类提供⼀系列产⽣随机数的⽅法，以满⾜不同⽤例需要 *
* @author crazyMonkey
*/
public final class StdRandom {
//随机数对象
private static Random random;
//⽤于产⽣随机数的种⼦
private static long seed;
// 静态初始化区域
static {
//产⽣随机数种⼦
seed = System.currentTimeMillis();
random = new Random(seed);
}
private StdRandom() {
}
/***********************************************************
* 产⽣基本的随机数
***********************************************************/
/**
* 获取此类实例的伪随机种⼦⽣成器
*/
public static void setSeed(long s) {
seed = s;
random = new Random(seed);
}
/**
* 获取此类实例提供的伪随机种⼦⽣成器
*/
public static long getSeed() {
return seed;
}
/**
* 返回⼀个随机的范围在[0,1)之间的double类型的数
*/
public static double uniform() {
Double();
}
/**
* 返回⼀个随机的范围在[0,N)之间的int类型的数
*/
public static int uniform(int N) {
Int(N);
}
/**
* 返回⼀个范围在 [0, 1)的实数
*/
public static double random() {
return uniform();
}
/**
* 返回⼀个范围在 [a, b)的int类型值
*/
public static int uniform(int a, int b) {
return a + uniform(b - a);
}
/**
* 返回⼀个范围在 [a, b)的实数
*/
public static double uniform(double a, double b) {
return a + uniform() * (b - a);
}
}
快速排序
它的基本思想是：通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以递归进⾏，以此达到整个数据变成有序。
代码:
public class QuickSort {
public static void optimizeSort(Comparable[] array, int left, int right) {
optimizeAdjust(array, left, right);
}
/**
* @param array 待排序数组
* @param left  数组的左界

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。