时间复杂度为O(n^2)的几种排序

痛定思痛。 2021-09-18 07:18 257阅读 0赞

# 分析排序算法的三个角度 #

## 分析执行效率 ##

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。  
有序度是数组中具有有序关系的元素对的个数。

![18721752-8343cf8c1bfff9cf.png][]

image.png

满有序度  
一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n (n-1)/2  
逆序度：  
逆序元素对：a\[i\] > a\[j\], i < j。  
逆序度此时等于本次需要交换的次数。

![18721752-44e6a0b69899cefd.png][]

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)

[18721752-8343cf8c1bfff9cf.png]: /images/20210918/fcfd1aba3ac1441fa8f44078ce7284cb.png
[18721752-44e6a0b69899cefd.png]: /images/20210918/a3eb69790f87485b94ab29be59c314a3.png