欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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