首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >温故而知新:对排序算法的新认识

温故而知新:对排序算法的新认识

作者头像
用户6557940
发布2022-07-24 16:33:15
2050
发布2022-07-24 16:33:15
举报
文章被收录于专栏:Jungle笔记Jungle笔记

首次认识排序算法还是在大二的《数据结构》课程上听老师介绍的。那时候颇不理解,不仅不理解这些排序算法,更不理解为什么机械学院要开设《数据结构》这门课程。后来在大四以及此后的硕士项目过程中,我真有用到排序算法,不过当时图方便,而且数据量不大,我使用的冒泡排序(编码简单)。之后与排序算法结缘,是准备秋招。为了考试,为了项目,为了秋招,回顾这几次与排序算法的近距离接触,我并没有真正理解各类排序算法的原理

求解数组中的逆序对

这两天看到一道题目:求解数组中的逆序对。

难度标记为“困难”,一上来就被吓住了,一定很难,除了暴力解决,多半是用些什么炫酷的算法,动态规划?分治算法?回溯……脑海里过了几部电影后,经过bobo点播,竟然是用归并排序!而且只在归并排序源代码里增加一行代码即可!

归并排序算法

归并排序采用分治策略,将一个待排序数组一分为二,把每部分递归使用归并排序,再将两部分合并成一个序列,这也是“归并” 由来,也是其时间复杂度为O(nlogn)的原因。合并的时候需要额外申请空间,这是归并排序空间复杂度为O(n)的原因。直接上归并排序的代码:

#ifndef _MERGE_SORT_
#define _MERGE_SORT_

// 归并排序:额外使用O(n)的空间, 时间复杂度O(nlogn)

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
  T *aux = new T[r - l + 1];
  for (int i = l; i <= r; i++){
    aux[i - l] = arr[i];
  }

  int i = l, j = mid + 1;
  for (int k = l; k <= r; k++){
    if (i > mid){
      arr[k] = aux[j - l];
      j++;
    }
    else if (j > r){
      arr[k] = aux[i - l];
      i++;
    }
    else if (aux[i - l] < aux[j - l]){
      arr[k] = aux[i - l];
      i++;
    }
    else{
      arr[k] = aux[j - l];
      j++;
    }
  }
  delete[] aux;
}

// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
  if (l >= r){
    return;
  }

  int mid = (l + r) / 2;
  __mergeSort(arr, l, mid);
  __mergeSort(arr, mid + 1, r);
  if (arr[mid] > arr[mid + 1]){
    __merge(arr, l, mid, r);
  }
}

template<typename T>
void MergeSort(T arr[], int N){
  __mergeSort(arr, 0, N - 1);
}

#endif // _MERGE_SORT_

使用归并排序求解逆序对

那么如何解上面那个逆序对的问题呢?试想,合并之前左右两个子序列已经有序,合并时候的关键在于比较左右两个序列的元素大小。以上述代码中的变量为例:

[4,7,9,10]为左边有序子序列,[1,3,5,6]为右边有序子序列,现在要合并为一个有序序列。l和r分别代表左右边界。按照上述代码的__merge中的逻辑,现在考察arr[i]和arr[j],显然9>3,所以构成了一个逆序对。别着急,因为左边序列是有序的了,即i后面的元素比arr[i]大,肯定也和arr[j]构成逆序对。当然上图例子只有10。所以逆序对的数量可以直接增加(mid-i+1)。声明一个全局的变量times,在__merge函数的arr[i-l]>arr[j-l]的逻辑分支里加上下面一行代码,最后归并排序完成后返回times即可:

else{
      nums[k] = aux[j - l];
      times = times + mid - i + 1;// 增加这一行代码即可
      j++;
    }

O(n2)的排序算法

归并排序时间复杂度为O(nlogn),还有些时间复杂度为O(n2)的排序算法,比如冒泡排序、选择排序、插入排序和希尔排序)。一提到O(n2),就感觉这类算法很low,不高级,不优雅

其实不是。我前几次接触排序算法,都是从时间复杂度为O(n2)的排序算法起步的。bobo总结得很好,为什么要学习O(n2)的排序算法:

  • 基础
  • 编码简单,易于实现,是一些简单情景的首选
  • 简单的排序算法思想衍生出复杂的排序算法
  • 作为子过程,改进更复杂的排序算法

一些O(n2)的排序算法,性能甚至好过O(nlogn)的排序算法,比如希尔排序,插入排序。插入排序对于少量数据排序的高性能,甚至可以作为O(nlogn)的排序算法优化的一部分,改进O(nlogn)的排序算法的时间性能。比如,判断到某个子序列可能只有十几个元素,那么可以直接使用插入排序

温故而知新,很多基础知识,经典算法,前人早已总结完毕。这些东西一定是有道理的,如果觉得它没用,那一定是还没感悟到其中的道理。

不限于此,很多人生哲学道理,古人早已总结完毕。清代乾隆年间,纪晓岚主编《四库全书》。他曾经说过:“世间的道理与事情,都在古人的书中说尽,现在如再著述,仍然超不过古人的范围,又何必再多著述。”所以,纪晓岚一生之中,从不著书,只是编书——整理前人的典籍,将中国文化作系统的分类,以便于以后的学者们学习。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-04-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Jungle笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云点播
面向音视频、图片等媒体,提供制作上传、存储、转码、媒体处理、媒体 AI、加速分发播放、版权保护等一体化的高品质媒体服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档