美文网首页
时间复杂度为O(n^2)的几种排序

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

作者: 乙腾 | 来源:发表于2021-01-02 22:03 被阅读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。
有序度是数组中具有有序关系的元素对的个数。

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)

相关文章

  • 算法与数据结构之排序(Swift版)

    1、冒泡排序 时间复杂度为O(n²) 2、选择排序 时间复杂度为O(n²) 3、插入排序 时间复杂度为O(n²)

  • 排序算法

    选择排序 选择排序最好的时间复杂度为:O(n^2)。选择排序的最坏时间复杂度为:O(n^2)。选择排序总的平均时间...

  • 算法基础|排序算法时间复杂度

    常见的7种排序算法时间复杂度: 1)直接插入排序,时间复杂度为O(n)~O(n²) 2)冒泡排序,时间复杂度为O(...

  • 【笔记-排序】

    排序平均时间复杂度最差时间复杂度最好时间复杂度稳定性冒泡排序O(n^2)O(n^2)O(n)稳定选择排序O(n^2...

  • 数据结构的js描述

    沈冬冬 冒泡排序 时间复杂度O(n^2) 稳定 选择排序 时间复杂度为O(n^2) 不稳定 插入排序 时间复杂...

  • 算法——排序算法

    冒泡排序 时间复杂度:O(n2) 空间复杂度:O(1) 稳定排序 选择排序 时间复杂度:O(n2) 空间复杂度:O...

  • 排序算法

    待排序列正序时,直接插入排序的时间复杂度为O(n)希尔排序的时间复杂度为O(n3/2)

  • LeetCode-排序算法

    LeetCode-排序算法 时间复杂度 排序算法平均时间复杂度冒泡排序O(n2)选择排序O(n2)插入排序O(n2...

  • 2020-11-19 排序算法一(冒泡和快排多种实现)

    主流的排序算法 时间复杂度为O(n^2):冒泡排序选择排序插入排序希尔排序(介于O(n^2)与O(nlogn)之间...

  • PHP实现冒泡排序

    冒泡排序属于交换排序,是一种稳定排序,平均时间复杂度为O(n^2),最好情况时间复杂度为O(n),最坏情况时间复杂...

网友评论

      本文标题:时间复杂度为O(n^2)的几种排序

      本文链接:https://www.haomeiwen.com/subject/ousyoktx.html