1.算法的评判标准

在讲解排序算法之前,我们首先来了解一下评判一个算法一般都是从哪些角度来评判的.

这个只要是稍微懂一点算法的小伙伴一定知道.这两个标准就是时间复杂度和空间复杂度

时间复杂度

时间复杂度,这个其实很好理解,这个从字面意思来看,我们就能够很好的理解了,就是整个算法执行需要多长的时间,这个时间复杂度又有两个评判标准,其实严格来说有三个即 最好情况,平均情况,最坏情况,但是一般我们并不讨论最好的情况,因为这个没有意义.所以我们一般讨论平均情况以及最坏的情况.

并且一般情况下,时间复杂度是我们最注重的,毕竟类比到我们平常生活中我们一般在乎的都是这个软件运行速度怎么样,是不是快,慢的离谱之后,用户的体验就会特别的差.一般不会说这东西怎么又吃了我多少内存空间.

其次另外一点就是 时间复杂度是体现一个算法的最核心的地方,毕竟空间复杂度稍微大一点还是可以接受的,但是如果算法的时间复杂度降不下来,就算再怎么加空间也是解决不了问题的.

空间复杂度

空间复杂度其实也是很好理解的,指的就是在算法的执行过程中到底占用了多少的内存空间.这个大家一般并不是特别的在意空间复杂度.但是在这里给大家举一个数据结构的例子,大家就能立马了解这个概念了.

这个数据结构就是HashMap,HashMap就是一种采取牺牲空间换时间的数据结构.Map能够直接获取到你想要键的元素.

知道HashMap这么强大之后,大家就能知道为啥大厂问到数据结构的源码的时候一般都是会问HashMap的源码了,因为它这样设计是真的流弊.

2.排序算法的分类

了解完上述算法的评判标准之后,我们就需要来看看这些排序算法又是怎么进行分类的了.

主要有这么两种分类的方式.

排序类型

这里的比较就和大家平常理解的比较是一个意思,就是主要是通过比较来进行排序的.

是否稳定

这里的稳定就需要和大家稍微说一说了,这里的稳定指的是相同的元素在排序之后的相对位置对比排序之前是否是一样的,如果没有发生变化的,那么就称这个算法是稳定的.这样说的话,大家可能不是很能理解,这里我们还是通过下面的图来帮助大家加深印象.

了解完上面这些概念之后,接下来我们讲解排序算法的时候提出的一些概念大家就能比较好的理解了.

3.十大经典排序算法-冒泡排序,选择排序,插入排序

3.1-冒泡排序

算法思想:

说到冒泡,大家的第一反应可能就是下图里面金鱼吐泡泡的画面

在画面里面我们就能看出来,泡泡是越往上泡泡越大.这个就是冒泡排序的核心思想:每次循环都找出剩余排序序列中的一个最大值或最小值,并且将它置换到序列的最末尾或者是最开始的位置.举下面这个简单的例子,大家就能理解了:

这就是冒泡排序的基本思想.并且我们能稍微总结一下冒泡排序的特点:

每次排序都能至少确定一个元素的最终位置

冒泡冒泡排序是稳定的,只有当元素的大小不一样时,元素之间才会交换位置,这就使得相同元素的相对位置在排序之前以及排序之后都是不变的,所以冒泡排序是稳定的.

冒泡排序有一个极端情况,假如我们规定的排序方式是从大到小的,但是原序列的顺序是从小到大的话,那么小伙伴们这时候就会发现,我们每次比较元素之后都需要将这两个元素进行交换.这种情况就是冒泡排序最极端的情况.

算法图解:

示例代码:

  public static void main(String[] args) {
    int []num ={7,4,9,3,2,1,8,6,5,10};
    long startTime=System.currentTimeMillis();  
    for(int i=0;i<num.length-1;i++) {
      for(int j=0;j<num.length-1-i;j++) {
        if(num[j]>num[j+1]) {
          int temp=num[j+1];
          num[j+1]=num[j];
          num[j]=temp;
        }
      }
      System.out.print("第"+(i+1)+"次排序结果:");
      for(int j=0;j<num.length;j++)
        System.out.print(num[j]+" ");
      System.out.println();
    }
    long endTime=System.currentTimeMillis(); 
    System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); 
  }

复杂度分析:

理解完冒泡排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.

时间复杂度

时间复杂度我们从两个方面来评判

平均情况

平均情况下我们的算法复杂度主要就是在进行元素的比较的过程.即进 if(num[j]>num[j+1])的过程,这个过程平均下来就是我们两层for循环的次数,这个我们计算一下就能得出是n*(n-1)/2,我们去最大的次数,可以看到时间复杂度就是O(n*n)

最坏情况

最坏情况就是我们上面说的极端情况.但是极端情况只是比我们的平均情况多执行了交换元素的操作,但是比较的次数是一直不变的,所以这样算下来时间复杂度也是O(n*n)

空间复杂度

这个我们也可以看到我们整个排序的过程中值增加了一个空间,这个空间就是我们定义的temp,主要就是帮助我们进行元素的交换的.所以冒泡排序的空间复杂度即为O(1)