排序算法的复杂度及稳定性详解(内含记忆小窍门)

简介: 排序算法的复杂度及稳定性详解(内含记忆小窍门)

一、排序算法分类

二、概念

算法的复杂性体现在运行该算法时的计算机所需资源的多少,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度

2.1 时间复杂度

是一个定性描述该算法的运行时间的函数。

作用: 指执行算法所需要的计算工作量。

2.2 空间复杂度

是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

比如直接插入排序的时间复杂度是O(n2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。

2.3 稳定性

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

三、表格比较

注意

1:希尔排序的平均时间复杂度,还有一种表示为O(n1.3)

2:基数排序时间复杂度O(N*M),其中N为数据个数,M为数据位数。

3:归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。

4:关于logn的底数看下面的解释

5:分治法和树形,时间复杂度是nlogn

62ab56b9d6444f589abc5e7eee9c89ab.png

四、部分排序分析

正序选择插入和冒泡,只比较,不交换反之,倒序时尽量不选择插入和冒泡

有序时尽量不选择快排,因为使用不到分治。

4.1 直接插入排序

图示


代码

public class InsertSort {
    //核心代码---开始
    public static void sort(Comparable[] arr){
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素 arr[i] 合适的插入位置
            for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    //核心代码---结束
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args) {
        Integer[] arr = {1,9,6,5,7,6,8,2,4};
        sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

4.2 冒泡排序

图示

代码

//冒泡排序
void BubbleSort(int* arr, int n)
{
  int end = n;
  while (end)
  {
    int flag = 0;
    for (int i = 1; i < end; ++i)
    {
      if (arr[i - 1] > arr[i])
      {
        int tem = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = tem;
        flag = 1;
      }
    }
    if (flag == 0)
    {
      break;
    }
    --end;
  }
}

4.3 快速排序

图示

代码

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

五、结构化记忆(小窍门)

5.1 结构化

指将逐渐积累起来的知识加以归纳和整理,使之条理化、纲领化,做到纲举目张。知识是逐渐积累的,但在头脑中不应该是堆积的。知识是有组织、有系统的,知识点按层次排列,而且知识点之间有内在联系,具有结构层次性。


5.2 我的结构化

我们都知道数据结构,数据结构指相互之间存在一种或多种特定关系的数据元素的集合,我们也可以把身边一切东西放在一起,去创造它们之间的关系。

现在就给大家分享一下我对七种比较排序的时间复杂度、空间复杂度和稳定性进行的“胡乱”结构化,请结合上面的二维表:

先来看时间复杂度(平均时间复杂度、最好时间复杂度、最坏时间复杂度):

1、找共性:

首先看到有些排序这三个复杂度一样,分别是直接选择排序,堆排序和归并排序,其中直接选择排序、堆排序属于选择排序,我提取了它们的首字母(归并、选择=GX),GX让我想到了共享,这不是刚好符合它们的特征吗,共享同一个时间复杂度。他们三个的区别是,直接选择排序是O(n2),归并和堆排序是nlogn。

2、找联系:

我们顺着nlogn继续往下找,快速排序也是nlogn,但是它不属于第一分类的“共享”,说明三者不一样,那哪个不一样呢,是最坏时间复杂度为n2。(n2>nlogn)

3、排除:

七个排序还剩下三个(冒泡、直接插入和希尔排序),这三个又有什么特点呢?

冒泡、直接插入和希尔排序他们在数组基本有序的情况下,只需要执行n次逻辑代码,最好时间复杂度都是O(n),冒泡、直接插入最坏和平均都是n2。剩下一个希尔,因为有步长,所以比较特殊,单独理解就好。

总结一下整个过程就是:

gx–nlogn–(7-4)–2+1

f1be35ad77ec4d98a3587244e82193a8.png

再说空间复杂度:找到的共性是大部分都是O(1),只有两个比较特殊,一个是归并,一个是快排,(这个结构化的过程交给你来了,试试吧小伙伴,你会发现很有意思);

稳定性:快选希堆不稳定,其余稳定。


整个过程就是这么有意思~~~~


六、总结

时间复杂度和空间复杂度咋一看确实比较麻烦,如果想要记忆,首先要理解概念,然后要理解每种复杂度代表的含义,最后一点,知识从来不枯燥,想象力创造力可以让本来没有意义的内容变得有意思,包括写代码,所以,不要枯燥的学习了,让我们一起“造”起来吧~


相关文章
|
6月前
|
机器学习/深度学习 存储 算法
1 .算法的复杂度(超全)
1 .算法的复杂度(超全)
|
2月前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
26 0
|
3月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
63 4
|
3月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
47 1
|
4月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
28 1
|
4月前
|
搜索推荐
九大排序算法时间复杂度、空间复杂度、稳定性
九大排序算法的时间复杂度、空间复杂度和稳定性,提供了对各种排序方法效率和特性的比较分析。
162 1
|
5月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
77 1
【数据结构】算法的复杂度
|
5月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
【7月更文挑战第23天】在Python编程中,掌握算法复杂度—时间与空间消耗,是提升程序效能的关键。算法如冒泡排序($O(n^2)$时间/$O(1)$空间),或使用Python内置函数找最大值($O(n)$时间),需精确诊断与优化。数据结构如哈希表可将查找从$O(n)$降至$O(1)$。运用`timeit`模块评估性能,深入理解数据结构和算法,使Python代码更高效。持续实践与学习,精通复杂度管理。
66 9
|
6月前
|
算法 搜索推荐
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
51 0