插入排序算法的速度测试 [数据结构][Java]

插入排序算法的速度测试

创建一个长度为80000的随机值数组来对我们的插入排序算法的速度做一个测试:

给出测试代码:

package com.ffyc.util.arraysortspeedtest;

import com.ffyc.util.ArraySort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class InsertSortSpeedTest {
    public static void main(String[] args) {
        //声明一个长度为80000的数组
        int [] arr = new int[80000];

        //给数组中赋上随机值
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }

        //创建一个当前时间的Date对象
        Date date1 = new Date();
        //创建一个SimpleDateFormat类型的对象用来格式化当前的时间的Date对象
        SimpleDateFormat simpleDateFormat  = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str =  simpleDateFormat.format(date1);
        System.out.println("排序前的时间为: "+ date1Str);

        //调用我们的插入排序算法
        ArraySort.insertSort(arr);

        //创建一个排序后时间的Date对象
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间为: " + date2Str);

        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 我们使用直接插入排序处理长度为80000的随机值数组需要的时间大概是1秒

选择排序算法和插入排序算法和冒泡排序的效率的比较:

我们在插入排序中一旦从后往前在有序表中找到比待插入元素大的值,那么该有序表中的对应大的值就要后移,这里我们每当执行一次后移操作就会进行一次赋值操作,并且如果遇到完全逆序的情况这个时候每一次的待排序元素都要和前面的有序表中的所有的元素进行交换位置

• 但是注意:我们这里其实是一种优化过的冒泡排序,我们这里是进行了一个后移,但是这个时候执行的效率还是很低,因为每次比较都是要进行一次赋值操作,就有些类似于冒泡排序,我们的冒泡排序在完全逆序的情况下就是比较一下就可能交换一次,并且在冒泡排序的时候我们直接是执行的交换而不是后移,所以我们要进行两次赋值操作,所以我们的插入排序算法的执行效率比我们的冒泡排序的效率高

而选择排序中每次都是找最小值,都要将数组遍历一次,但是在选择排序中交换时整体发生在内层for循环之外的, 在内层for循环之中只是进行了修改,而对于插入排序则是在内层for循环中进行了数组元素的移动,我们认为数组赋值的速度比变量赋值的速度要慢,所以我们认为在完全逆序(或者说数组混乱度比较大)的情况下我们的插入排序的速度是比选择排序的速度要慢的

• 但是我们的插入排序如果找到带插入位置之后就会提前终止这一趟排序,所以在我们的数组趋于有序的情况下我们的插入排序算法的执行效率甚至要比一些nlogn阶的排序算法的执行效率都要高

结论: 插入排序算法执行效率 > 选择排序算法执行效率 > 冒泡排序算法执行效率

• 但是这个只是一般情况之下的
  • 如果在数组中的元素为 6,1,2,3,4,5的情况之下这个时候我们的插入排序其实也就是要将我们的整个待排序数组都遍历一遍,这个时候由于数组元素赋值要比临时变量赋值满,所以我们这种情况之下选择排序的效率相对来讲要高一些