冒泡&插入&选择三种排序法哪个好

2019-06-14  本文已影响0人  麦兜的夏天

一、分析一个排序算法,需要从几方面考量?

1.时间复杂度(排序算法的执行效率)

1.最好情况、最坏情况、平均情况时间复杂度
2.需要考虑复杂度的系数、常数、低阶。因为我们排序的可能是小规模的数据,所以在对同一阶时间复杂度的排序算法性能对比的时候,就要考虑系数、常数、低阶
3.比较和交换的次数

2.空间复杂度(排序算法的内存消耗)

3.排序算法的稳定性
稳定性:如果待排序的序列中存在值相等的元素,经过排序后,相等元素之间原有的先后顺序不变。

二、使用上面的方式对这三种排序法进行分析

1.冒泡排序:

描述:冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

代码:

  public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    flag = false;
                }
            }

            // 如果一轮冒泡之后,发现没有数据交换,说明已经排好序了,不需进行下一轮冒泡
            if (flag) {
                break;
            }

        }
    }

分析:
1.冒泡的过程中只需要常量级的临时空间,所以它的空间复杂度为 O(1)。
2.相邻的两个元素大小相等的时候,不做交换,所以冒泡排序是稳定的排序算法。

3.1 最好的情况是,已经排好序了,只需要进行一次冒泡操作,就可以结束了,所以最好时间复杂度是 O(n)。
3.2 最坏的情况是,数据刚好是倒序排列,需要进行 n 次冒泡操作,所以最坏时间复杂度是 O(n^2)
3.3 平均情况下的时间复杂度就是 O(n^2)。
平均时间复杂度就是加权平均期望时间复杂度,涉及的数学推理和计算会很复杂。我们使用“有序度”和“逆序度”进行分析。

我们已经认为平均情况需要 \frac{n\times(n-1)}{4} 次交换操作,而比较操作肯定要比交换操作多,而复杂度的上限是 O(n^2),所以平均情况下的时间复杂度就是 O(n^2)。

2.插入排序:

描述:将未排序区的数据一个个拿出来,放入排序区中适合它的位置。例如:排序区为:1,3,6,8 从未排序区拿到的数据为4,那么它会被插入到3和6之间。

对于一组待排序的数据而言,第一个数据就是排序区,后面的数据属于未排序区。

代码:

 public void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];

            int j = i - 1;
            for (; j >= 0; j--) {
                if (a[j] > temp) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }

            a[++j] = temp;
        }
    }

分析:
1.插入排序的过程中并不需要额外的存储空间,所以空间复杂度为 O(1)
2.由第七行可以看出,对于值相同的元素,后面出现的元素会插入到前面出现的元素的后面,这样可以保持原有的前后顺序不变,所以插入排序法是稳定的。

3.1 最好情况是已经排好序了,插入排序会寻找每个元素应该插入的位置,会从头遍历已经有序的数据,所以时间复杂度为 O(n)
3.2 最坏情况是数组倒序,显然最坏时间复杂度为O(n^2)
3.3 平均时间复杂度:向数组中插入数据的时间复杂度为 O(n),插入排序要循环 n 次插入操作,所以平均时间复杂度为 O(n^2)

3.选择排序:

描述:每次从未排序区中找到最小的元素,将其放到已排序区的末尾。

代码:

  public void selectSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int index = i;

            // 选出最小的记录
            for (int j = index + 1; j < a.length; j++) {
                if (a[j] < a[index]) {
                    index = j;
                }
            }

            // 执行交换
            int temp = a[i];
            a[i] = a[index];
            a[index] = temp;
        }
    }

分析:
1.选择排序的空间复杂度为 O(1)
2.稳定性:例如4,5,4,1,9这个数组,第一次找到最小元素1,与第一个4交换位置,那么第一个4和第二个4的顺序发生了变化,所以不稳定。
3.无论是最好还是最坏情况,都需要先找出未排序区的最小值,然后将这样的操作执行 n 次,所以选择排序的最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度均为 O(n^2)

总结:

通过对三种排序方式的分析,首先很明显的看出,选择排序没有其他两种排序方式好。冒泡排序和插入排序从上面三个维度分析,很难分出谁好谁坏,需要对比具体的代码了

  //冒泡排序排序中数据交换操作
   for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            flag = false;
        }
    }

  //插入排序中数据移动操作
    for (; j >= 0; j--) {
        if (a[j] > temp) {
            a[j + 1] = a[j];
        } else {
            break;
        }
    } 

显然冒泡排序执行的操作更多,消耗的时间会更多,所以说插入排序法比冒泡排序法好。

数据量大的时候,效率上的差距还是比较明显的。通过下面的代码进行验证:

    //分别使用两种算法对两万个数组进行排序,每个数组有两百个元素
    public static void main(String[] args) {

        Random rd = new Random();

        long start1 = System.currentTimeMillis();
        for (int i = 0; i < 20000; i++) {
            int[] nums = new int[200];
            for (int j = 0; j < 200; j++) {
                nums[j] = rd.nextInt(200);
            }
            insertionSort(nums);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("插入排序法耗时:" + (end1 - start1));

        //-------------

        long start2 = System.currentTimeMillis();
        for (int i = 0; i < 20000; i++) {
            int[] nums = new int[200];
            for (int j = 0; j < 200; j++) {
                nums[j] = rd.nextInt(200);
            }
            bubbleSort(nums);
        }
        long end2 = System.currentTimeMillis();
        System.out.println("冒泡排序法耗时:" + (end2 - start2));
    }
    
    
某次的执行结果:
  插入排序法耗时:392
  冒泡排序法耗时:1936
上一篇 下一篇

猜你喜欢

热点阅读