Java数据结构与算法--测试希尔排序(交换法)花费的时间
程序员文章站
2022-04-29 17:31:13
用80000个数据测试希尔排序(交换法)的速度。希尔排序法是改进的插入排序法,但是经过测试后发现并没有比插入排序法更快,原因在于使用交换法时耗费了很多时间。一、代码package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class ShellSort {public static void main(String[] args) {//用...
用80000个数据测试希尔排序(交换法)的速度。
一、代码
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class ShellSort {
public static void main(String[] args) {
//用80000个随机数据测试希尔排序算法的速度
int[] arr = new int[80000];
for(int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 80000);//随机生成一个[0, 80000)之间的整数
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("希尔排序前的时间:" + date1Str);
shellSortByChange(arr);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("希尔排序后的时间:" + date2Str);
}
public static void shellSortByChange(int[] arr) {
for(int gap = arr.length / 2; gap > 0; gap /= 2) {
for(int i = gap; i < arr.length; i++) {
//遍历各组中所有的元素(共5组,每组有2个元素),步长是5
for(int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长后的那个元素,则交换
if(arr[j] > arr[j + gap]) {
int temp = arr[j];//优化时,temp的声明可以放在第一个for循环外面
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
}
二、结果
1. 第1次测试耗时8秒
希尔排序前的时间:2020-07-21 14:11:48
希尔排序后的时间:2020-07-21 14:11:56
2. 第2次测试耗时7秒
希尔排序前的时间:2020-07-21 14:12:33
希尔排序后的时间:2020-07-21 14:12:40
3. 第3次测试耗时6秒
希尔排序前的时间:2020-07-21 14:13:53
希尔排序后的时间:2020-07-21 14:13:59
本文地址:https://blog.csdn.net/GTboy100/article/details/107487677
下一篇: 深入理解Promise.all