选择排序算法的速度测试 [数据结构][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 SelectSortSpeedTest {
    public static void main(String[] args) {
        //创建一个长度为80000的随机值数组
        //这里我们先创建一个长度为80000的数组
        int [] arr =  new int [80000];

        //然后给这个数组中的每个位置都赋上随机值
        for (int i = 0; i < 80000; i++) {
            //这里的Math.random()*8000000就是生成一个随机的[0,8000000)之间的数值
            arr[i] = (int)(Math.random()*8000000);
        }


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

        //调用选择排序的方法,将我们的待排序数组传入我们的选择排序的方法中
        ArraySort.selectSort(arr);

        //创建一个排完序之后的date类型的对象
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间是: "+ date2Str);
    }
}
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
37

• 这个时候我们执行出来的结果是用时2秒左右的时间

我们可以发现对于同样的长度为80000的随机值数组,我们使用冒泡排序的时候是用了12秒作用的时间,而我们使用选择排序的时候只是使用了2秒左右的时间,那么为什么选择排序会比冒泡排序快?

有的人会说我们的冒泡排序的时间复杂度是o(n2),而我们的选择排序的时间复杂度也是O(n2),这个时候我们使用选择排序为什么会比使用冒泡排序快这么多?

• 这个时候虽然我们的选择排序和我们的冒泡排序的算法时间复杂度都是O(n2),但是我们的选择排序中发生交换的次数要比使用冒泡排序少的多,因为我们的冒泡排序是是相邻的两个元素进行比较,比价一次就有可能交换一次两个位置的数值 —> 也即是我们的冒泡排序中可能一趟中会发生n-1次交换,而我们的使用选择排序的时候一趟排序中就是选取一个最小值,这个时候我们一趟排序中如果遇到比当前假定的最小值的元素小的数据,这个时候我们不会交换,而是记录这个位置的数值和下标,只有等到一趟排序完了之后我们才会去交换最小值元素的位置和最小值元素应该出现的位置,所以我们的选择排序明显就是比冒泡排序要快的
  • 我们从代码层面来看就是冒泡排序的交换元素值的操作是在双层for循环之内,而我们的选择排序中的交换元素的操作发生在外层for循环和内层for循环之间
    • 也就是对于我们的冒泡排序的交换操作的时间复杂度是O(n2),而对于我们使用选择排序的方式的交换操作的时间复杂度是O(n),所以这个时候显然我们的选择排序是比较快的
      • 但是这个时候有的人就会说:那么选择排序中双层for循环之中不是也执行了两条语句?
        • 那这个时候我们的冒泡排序中的双层for循环之中还执行了四条语句,这个执行四条语句的效率肯定比执行一条语句的效率要低