冒泡排序、插入排序、选择排序

排序算法分析方法

分析排序算法的执行效率
- 最好情况、最坏情况、平均情况时间复杂度以及原始数据的有序度(有序度不同对排序的执行时间有影响)
- 时间复杂度反应的是大规模数据的增长趋势，实际中规模小需要考虑系数、常数、低阶
- 元素比较次数和交换/移动次数（基于比较的排序算法）
排序算法的内存消耗（空间复杂度）
- 原地排序算法：空间复杂度为O(1)的排序算法。
排序算法的稳定性
- 稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。稳定的排序算法||不稳定的排序算法

插入排序和冒泡排序的时间复杂度相同，都是O(n²)

冒泡排序 ¹

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

冒泡过程只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为O(1)，属于原地排序算法。
冒泡排序中只有交换才改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，属于稳定的排序算法。
时间复杂度
- 最好情况时间复杂度是O(n)，数据有序，进行一次冒泡操作;
- 最坏情况时间复杂度O(n²)，数据倒序，进行n次冒泡操作。
- 平均时间复杂度：对于包含n个数据的数组，这n个数据有n!种排序方式。不同的排列方式，冒泡排序执行的时间不同。用概率论方法定量分析平均时间复杂度较复杂。
有序度：数组中具有有序关系的元素对的个数。有序元素对：a[i] <= a[j];i<j。
倒序排列的数组，有序度为0;
完全有序的数组，有序度n(n-1)/2. 满有序度。
*逆序度**。逆序元素对：a[i] > a[j];i<j。
逆序度 = 满有序度 - 有序度。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度。

冒泡排序包含两个操作原子，比较&交换。每交换一次，有序度加1，交换次数是确定的，为逆序度：n(n-1)/2 - 初始有序度。
对于包含n个数据的数组进行冒泡排序，最坏情况下，初始状态的有序度是0，要进行n(n-1)/2次交换；最好情况下，初始状态的有序度是n(n-1)/2，不需要进行交换。取中间值n(n-1)/4来表示初始有序度。平均情况下要进行n(n-1)/4次交换操作，比较操作比交换操作多，复杂度的上限是O(n²)，所以*平均情况下的时间复杂度是O(n²)**。

插入排序 ²

动态的往有序集合中添加数据，遍历数组找到数据应该插入的位置进行插入，保持集合中的数据一直有序。

将数组中的数据分为两个区间：已排序区间&未排序区间。初始已排序区间只有一个元素-数组的第一个元素。插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入排序包含两种操作：元素的比较，元素的移动。将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素一次比较大小，找到合适的插入位置。找到插入点之后，需要将插入点之后的元素往后移动一位，腾出位置给元素a插入。不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的，但对于一个给定的初始序列，移动操作的次数是固定等于逆序度。

插入排序算法的运行并不需要额外的存储空间，空间复杂度是O(1)，属于原地排序算法。
在插入排序中，对值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样可以保证原有的前后顺序不变，插入排序是稳定的排序算法。
时间复杂度
- 最好时间复杂度O(n)，数据有序，不需要搬移任何数据。如果从尾到头在有序数组里面查找插入位置，每次只需要比较一个数据（当前元素与其前一个元素比较，当前大不小于不用动）就能确定插入的位置。（内层循环只执行一次就break）
- 最坏时间复杂度O(n²)，数据倒序，每次插入都相当于在数据的第一个位置插入新的数据，需要移动大量的数据。
- 平均时间复杂度：在数组中插入一个数据的平均时间复杂度是O(n)（详见数组篇）。对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，平均时间复杂度为O(n²)。

选择排序 ³

选择排序类似插入排序，分为已排序区间&未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

空间复杂度为O(1)，原地排序算法。
时间复杂度：最好、最坏、平均时间复杂度都为O(n²)。
选择排序是一种不稳定的排序算法。选择排序每次都要找到剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

插入与冒泡对比

冒泡跟插入不管怎么优化，元素移动的次数是一个固定值，等于原始数据的逆序度。
冒泡的数据交换要比插入的数据移动复杂，3个赋值操作>1个赋值操作。

参考&扩展

- [1] 冒泡排序：

public void bubbleSort(int[] a) {
    int n = a.length;
    if(n <= 1) return;
    //未排序区间+已排序区间
    for (int i = 0; i < n; i++) {
        boolean flag = false;
        //从第一个元素开始进行比较，选出前面剩余未排序区间（n-i-1）元素的最大值
        for(int j = 0; j < n - i -1; j++) {
            //当前元素大于下一个元素值，交换两个元素位置
            if(a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                //有数据交换交换需要继续进行
                flag = true;
            }
        }
        if(!flag) break;
    }
    for (int i : a)
        System.out.print(i);
}

- [2]插入排序：

public void insertionSort(int[] a) {
    int n = a.length;
    if(n <= 1) return;
    //已排序区间+未排序区间
    for (int i = 1; i < n; i++) {
        //当前要排序（插入）的元素值
        int temp = a[i];
        //从已排序区间(i-1)元素最大下标，倒着一一进行比较
        int j = i - 1;
        for (; j >= 0; j--) {
            if (a[j] > temp) {
                //已排序区间目前元素值大于当前元素值，则交换位置，继续与前一个元素值比较
                a[j+1] = a[j];
            } else {
                break;
            }
        }
        //for循环中与j--之后的元素比较后break，最终移入的下标应为j++
        a[j+1] = temp;
    }
    for (int i : a)
        System.out.println(i);
}

- [3]选择排序：

public void selectSort(int[] a) {
    int n = a.length;
    if(n <= 1) return;
    //已排序区间+未排序区间
    for(int i=0;i<n;i++){
         int min=i;
         //查找未排序区间最小元素的下标值
         for(int j=i+1;j<n;j++){
              if(a[j] < a[min]) min=j;
         }
         //将最小元素放到当前已排序区间的最后一位
         if(min != i){
              int temp=a[i];
              a[i]=a[min];
              a[min]=temp;
         }
    }
    for (int i : a)
        System.out.println(i);
}

排序算法分析方法

冒泡排序 1

插入排序 2

选择排序 3

插入与冒泡对比

参考&扩展

冒泡排序 ¹

插入排序 ²

选择排序 ³