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

作者: 麦兜的夏天 | 来源:发表于2019-06-14 22:38 被阅读0次

js 常见排序算法（快速排序，选择排序等）
C语言中排序方法的使用
冒泡&插入&选择三种排序法哪个好
选择排序，冒泡排序，插入排序（二分法）
php实现几种常见的排序方法
关于JavaScript-2:基本排序算法
PHP四种基础算法详解
OC中的排序算法
冒泡排序、插入排序、选择排序
iOS算法

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

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$ )。
平均时间复杂度就是加权平均期望时间复杂度，涉及的数学推理和计算会很复杂。我们使用“有序度”和“逆序度”进行分析。

有序度：数组中具有有序关系的元素对的个数。
例如：[2,4,3,1,5,6]这组数据的有序度为11。因为其有序元素对为11个，分别是：(2,4)(2,3)(2,5)(2,6)(4,5)(4,6)(3,5)(3,6)(1,5)(1,6)(5,6)
对于倒序排列的数组，[6,5,4,3,2,1]它的有序度为0，
对于完全有序的数组，[1,2,3,4,5,6]它的有序度为 $\frac{n\times(n-1)}{2}$ ，也就是15，我们将这种完全有序的数组的有序度叫做满有序度。（等差数列前 n 项和公式： $\frac{n\times(a_1+a_n)}{2}$ ）
逆序度：数组中具有逆序关系的元素对的个数。
逆序度 = 满有序度 - 有序度
冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度加1。无论算法如何改进，交换次数总是确定的，即逆序度，也就是 $\frac{n\times(n-1)}{2} - 初始有序度$
那么对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？
最坏情况下，初始有序度是 0，所以要进行 $\frac{n\times(n-1)}{2}$ 次交换。最好情况下，不需要交换。我们可以取中间值 $\frac{n\times(n-1)}{4}$ ，来表示平均情况。

我们已经认为平均情况需要 $\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