vlambda博客
学习文章列表

极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序

目录

  • 排序算法衡量指标

  • 冒泡排序

  • 选择排序

  • 插入排序


排序算法衡量指标

关于排序算法的重要性我就不啰嗦了,不重要你也遇不到这篇文章。安利一个学习算法免费看动画的网站,该文的动图都来自这个网站 https://visualgo.net/zh/sorting ,感谢站长。

那么多的经典和野鸡排序算法,讲之前我们先关注一下排序算法的衡量指标:

  1. 时间复杂度

  2. 空间复杂度

  3. 最好情况

  4. 最坏情况

  5. 比较次数,交换次数

  6. 稳定性

    脱离了实际运用的数据结构是没有意义的,真正软件开发中,我们要排序的往往不是单纯的整数,而是一组对象,我们需要按照对象 的某个key来排序。

    比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有10万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,我们怎么来做呢?

    • 直接思路:我们先按照金额对订单数据进行排序,然后,再遍历排序之后的订单数据,对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难,但是实现起来会很复杂。

    • 稳定排序算法思路:这个问题可以非常简洁地解决,我们先按照下单时间给订单排序,注意是按照下单时间,不是金额。排序完成之后,我们用稳定排序算法,按照订单金额重新排序。两遍排序之后,我们得到的订单数据就是按照金额从小到大排序,金额相同的订单按照下单时间从早到晚排序的。

    • 为什么呢?稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。第一次排序之后,所有的订单按照下单时间从早到晚有序了。在第二次排序中,我们用的是稳定的排序算法,所以经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。

    • 稳定性解释:比如我们有一组数据2,9,3,4,8,3,按照大小排序之后就是2,3,3,4,8,9。这组数据里有两个3。经过某种排序算法排序之后,如果两个3的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。

    • 为什么要关注稳定性?

  7. 是否原地(原址,就地)排序

    维基百科说的原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。简单理解为,允许借助几个变量,不需要额外开数组。

    属于原地排序的是:希尔排序、冒泡排序、插入排序、选择排序、堆排序、快速排序,他们都会有一项比较且交换操作(swap(i,j))的逻辑在其中;而合并排序,计数排序,基数排序等不是原地排序。

  8. 十大经典排序算法江山图

十大经典排序算法

排序方式In-Place指的是原地排序,Out-place指的非原地排序

看了江山图之后,我们先来看江山图里混成了最底层的弟弟们,冒泡排序,选择排序和插入排序,这几个是时间复杂度最高的排序。

冒泡排序

这个排序不简单,大学里面每个学校都必教的一个排序

  • 算法描述

给定一个N个元素的数组,冒泡法排序将:

  1. 比较一对相邻元素(a,b);
  2. 如果元素大小关系不正确,交换这两个数;
  3. 重复步骤1和2,直到我们到达数组的末尾(最后一对是第(N-2)和(N-1)项,因为我们的数组从零开始)
  4. 第一次循环比较结束,最大的元素将在最后的位置。然后我们将N减少1,并重复步骤1,直到N = 1。
  • 算法思想

    一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

    交换旗帜变量 = 假 (False)

    从 i = 1 到 最后一个没有排序过元素的指数

    如果 左边元素 > 右边元素

    交换(左边元素,右边元素)

    交换旗帜变量 = 真(True)

    while 交换旗帜变量
  • 动图演示

    冒泡排序动画

极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序

    • 动图解释,后面所有的动图颜色代表的意思一样

    • 黄色的条代表已经排好序的元素;

    • 绿色的代表此算法正在操作,进行比较交换的元素

    • 蓝色代表还没有排序的

  • 代码实现

public class BubbleSort {
    public static int[] bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        // 第一层循环,每循环一次,排好一个元素,在最右边
        for (int i = 0; i < n; i++) {
          // 第二层循环,到右边第一个没有排序过元素地方结束,进行比较交换
            for (int j = 0; j < n -i - 1; j++) {
              // 比较,大于小于号决定是按照从大到小排还是从小到大排
                if (arr[j + 1] < arr[j]) {
                // 交换
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }
        }
        return arr;
    }
)

可知第二层循环是进行比较交换的核心逻辑,第一层循环用来确定排好了几个元素,决定了第二层循环的比较次数,n-i-1之所以减去一,是因为比如剩下10个元素没有排序,10个元素只有9对,需要比较九次。

  • 稳定性分析

    稳定。只有交换才可以改变两个元素的前后顺序,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。如果代码交换逻辑改成

    if (arr[j + 1] <= arr[j]),加了个=,那么就不稳定了。

  • 时间复杂度分析

    • 最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是O(n)。

    • 而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行n次冒泡操作,所以最坏情况时间复杂度为O(n2)。

      关于最好情况下只需要冒泡一次,我们可以将这个冒泡算法优化一下来更加直观的看到,优化的根据:假如从开始的第一对到结尾的最后一对,相邻的元素之间都没有发生交换的操作,这意味着右边的元素总是大于等于左边的元素,此时的数组已经是有序的了,我们无需再对剩余的元素重复比较下去了。代码如下:

      public void bubbleSort(int[] a, int n) {
       for (int i = 0; i < n; ++i) {
          // 提前退出冒泡循环的标志位
          boolean flag = false;
          for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j+1]) { 
              // 交换 
              int tmp = a[j];
              a[j] = a[j+1];
              a[j+1] = tmp;
            }}
          // 表示有数据交换
          flag = true
      }}if (!flag) break; // 没有数据交换,提前退出

      直接能看到,最好情况就是n次比较。

选择排序

  • 算法描述

    给定 N 个项目和 L = 0 的数组,选择排序将:

    1. [L ... N-1] 范围内找出最小项目 X 的位置,
    2. 用第 L 项交换X,
    3. 将下限 L 增加1并重复步骤1直到 L = N-2。
  • 算法思想

    选择排序分已排序区间和未排序区间,其实就是从头遍历,要排第几个元素,每次从剩余未排序元素里面找最小的元素,交换位置。

    重复(元素个数-1)次

      把第一个没有排序过的元素设置为最小值

      遍历每个没有排序过的元素

        如果元素 < 现在的最小值

          将此元素设置成为新的最小值

      将最小值和第一个没有排序过的位置交换
  • 动图演示

    选择排序

极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序

    红色表示当前遍历到的最小值。其他三个颜色和上面一样。

  • 代码实现

public class SelectSort {
    public static int[] selectSort(int[] a) {
        int n = a.length;
        // 从头开始遍历,选定某个元素待排序
        for (int i = 0; i < n - 1; i++) {
          // 将这个元素设为最小值
            int min = i;
            // 遍历所有未排过序的元素,从第i个元素右边开始
            for (int j = i + 1; j < n; j++) {
              // 如果元素小于当前最小值,那么最小值改为当前值
                if(a[min] > a[j]) 
                 min = j;
            }
            // 以上得到了当前最小值,将当前最小值提到前面
            //交换
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        return a;
    }
}
  • 稳定性分析

    不稳定。从动画当中可以看出,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

    如果你还是难以理解,那么举个栗子,比如4,6,4,2,7这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素2,与第一个5交换位置,那第一个4和中间的4顺序就变了,所以就不稳定 了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。

  • 时间复杂度分析

    最好和最坏情况都是n的平方,因为每次都是去查寻最小的元素,第二层的遍历无论如何也要做,避免不了,因此选择排序可谓是弟中弟。

插入排序

  • 算法描述

    插入排序类似于大多数人安排扑克牌的方式。

    极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序
    插扑克牌之插入排序
    1. 从你手中的一张牌开始,
    2. 选择下一张卡并将其插入到正确的排序顺序中,
    3. 对所有的卡重复上一步。
  • 算法思想

    插入排序和选择排序一样,都分已排序区和位排序区。

    将第一个元素标记为已排序

    遍历每个没有排序过的元素

     “提取” 元素 X

     i = 最后排序过元素的指数 到 0 的遍历

      如果现在排序过的元素 > 提取的元素

       将排序过的元素向右移一格

      否则:插入提取的元素
  • 动图演示

    插入排序




    红色代表选中的需要排序的。

  • 代码实现

    public class InsertSort {
        public static int[] insertSort(int[] arr) {
            if(arr == null || arr.length < 2)
                return arr;

            int n = arr.length;
            // 下标为0的数默认是有序的,从下标为1的数开始遍历,将其放入他该去的地方
            for (int i = 1; i < n; i++) {
                // 申请一个变量记录要插入的数据,也就是动图中红色的元素
                int tmp = arr[i];

                // 从已经排序的序列最右边的开始比较,找到比其小的数,即动图中绿色的元素序号
                int j = i;
                // 红色元素下标大于0,要插入元素与遍历到的元素满足大小关系,遍历到的元素往后挪位腾位置        // 继续遍历,直到不满足大小关系停止,这个地方就是它的位置
                // 即红色元素小于绿色元素时,绿色元素挪位
                while (j > 0 && tmp < arr[j - 1]) {
                  // 绿色元素往后挪一位
                    arr[j] = arr[j - 1];
                    j--;
                }

                // 存在比其小的数,插入
                if (j != i) {
                    arr[j] = tmp;
                }
            }
            return arr;
        }
    }
  • 稳定性分析

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

  • 时间复杂度分析

    如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为O(n)。注意,这里是从尾到头遍历已经有序的数据。

    如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为O(n2)。

下一篇写希尔,归并,快排和堆排序,还是按照这种格式,有收获的三连走起,欢迎关注我,我是小魔女阿甘,扫码有惊喜哦。