分析排序算法的三个角度

分析执行效率

1.最好，最坏，平均时间复杂度。
2.比较次数和交换次数。
3.时间复杂度的系数，常数，低阶。

分析排序内存消耗

空间复杂度为O(1) 的排序算法。

分析算法的稳定性

相等元素排序之后原有顺序不变。
case:
比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

Bubble Sort

code

public static void bubbleSort(int[] arr){
    boolean isBreak = true;
    //todo 进行arr.length-1排序
    //n个元素需要进行n.length次排序
    for (int i = 0; i < arr.length-1; i++) {
        //todo 每次排序遍历比较相邻值
        //遍历让每个元素和相邻的元素比较
        for (int j = 0; j < arr.length-1; j++) {
            if (arr[j]>arr[j+1]){
                int tempVal = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tempVal;
                isBreak = false;
            }
        }
        if (isBreak){
            break;
        }
    }
}

内存消耗

空间复杂度为 O(1)

稳定性

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

执行效率

时间复杂度（执行最多的单元执行的次数）。
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

notice:

这里提供另一个分析时间复杂度的角度：

分析逆序度（定量分析）
逆序度 = 满有序度 - 有序度

有序度：
有序元素对：a[i] <= a[j], i < j。
有序度是数组中具有有序关系的元素对的个数。

image.png
满有序度
一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n(n-1)/2
逆序度：
逆序元素对：a[i] > a[j], i < j。
逆序度此时等于本次需要交换的次数。
image.png
冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。
对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度是 n(n-1)/2，就不需要进行交换。我们可以取个中间值 n(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 n(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。

Insert Sort

code

 public static void insertSort(int[] arr){
      if (arr.length == 0)
           return array;
        //todo 将数组分为两个部分，一个有序，一个无序,最后一个元素需也需要寻找插入的位置，所以i < arr.length
        for (int i = 1; i < arr.length; i++) {
            //将无序数组中的当前索引位的元素和有序数组中的元素比较，寻找要插入的位置
            int willIndsertValue = arr[i];
            int insertIndex = i-1;
            //todo 在有序数组中寻找要插入的位置
            for (; insertIndex >= 0; insertIndex--) {
                //和有序数组中的元素比小，这样可以一边比较一边将有序数组的元素向后移动
                if (willIndsertValue <arr[insertIndex]){
                    //本次和带插入元素比较的元素向后移动
                    arr[insertIndex+1] =arr[insertIndex];
                }else {
                    break;
                }
            }
            //此时insertIndex+1为其要插入的位置
            arr[insertIndex+1] = willIndsertValue;
        }
    }

内存消耗

空间复杂度为 O(1)

稳定性

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

执行效率

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

notice:

以上写法，最佳情况O(n2)，并不是O(n)
改成如下这样写更加清晰。

public static void insertSort(int[] arr){
        if (arr.length == 0)
           return array;
        //有序数组中的索引位
        int orderlyArrIndex = 0;
        int insertValue = 0;
        for (int i = 1; i < arr.length; i++) {
            orderlyArrIndex = i-1;
            insertValue = arr[i];
            //寻找索引位的前一位，并完成有序数组的扩张，当前值和有序数组中的元素进行比较，若小于某个元素，则该元素右移。
            while (orderlyArrIndex >= 0 && insertValue < arr[orderlyArrIndex]){
                arr[orderlyArrIndex+1] = arr[orderlyArrIndex];
                orderlyArrIndex--;
            }
            //判断要插入的索引位 orderlyArrIndex+1 是否需要插入替换
            if (orderlyArrIndex+1 != i){
                arr[orderlyArrIndex+1] = insertValue;
            }

        }
    }

SelectSort

code

public static void selectSort(int[] arr){
    if (arr.length == 0)
        return array;
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        int minVal = arr[i];
        for (int j = i+1; j < arr.length; j++) {
            if (minVal>arr[j]){
                minIndex = j;
                minVal = arr[j];
            }
        }
        if (minIndex!=i){
            arr[minIndex] = arr[i];
            arr[i] = minVal;
        }
    }
}

内存消耗

空间复杂度为 O(1)

稳定性

比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

执行效率

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)