文档章节

数据结构与算法系列十四(归并排序)

yhhitall
 yhhitall
发布于 04/14 10:30
字数 1744
阅读 61
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
	面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
	你真的愿意做一辈子CRUD Boy吗
#理由三:
	不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
	数组、链表、栈、队列
	散列表、二叉树、堆
	跳表、图
5.常用算法
	递归、排序、二分查找
	搜索、哈希、贪心、分治
	动态规划、字符串匹配

2.考考你

前面几篇内容,我们看了最基础的排序算法:冒泡排序,插入排序、选择排序。之所以说它们是基础的排序算法,是因为这几个排序算法的时间复杂度有点高,是O(n^2)适合于小规模的数据排序

这一篇我们来看一个高效一点的算法,也就是今天的主角:归并排序,时间复杂度是O(nlogn)

#考考你:
1.你知道归并排序的核心思想吗?
2.你能用java实现归并排序吗?

3.案例

3.1.归并排序核心思想

假设有一个待排序序列:[4, 5, 6, 3, 2, 1]。我们需要按照升序进行排序,排序后的序列是这 样的:[1, 2, 3, 4, 5, 6]。

如何通过归并排序实现呢?

归并排序核心思想:

归并排序算法,利用分而治之思想,包含两个过程:分解、合并

分解:将一个大的待排序序列,分成两个小的待排序序列;再将小的待排序序列,继续分解成更小的待排序序列......一直到问题不能分解为止

合并:将分解过程中层层分解后的小的待排序序列,再层层从小到大合并,在合并过程中实现排序......最终完成整个排序

用文字描述,稍微有点抽象,我们看一个图,你应该就明白了。

归并排序分解、合并过程:

3.2.归并排序代码实现

3.2.1.入口函数

/**
* 归并排序入口
* @param array  待排序数组
* @param n  数据规模
*/
public static void sort(Integer[] array,int n){
   // 如果数据规模小于等于1,直接返回
   if(n <= 1){
     return;
   }

  // 归并排序函数
  mergeSort(array,0,n-1);
}

3.2.2.分解函数

/**
* 归并排序函数(递归实现)
* @param array  待排序数组
* @param left  数组起始下标
* @param right    数组结束下标
*/
public static void mergeSort(Integer[] array,int left,int right){
   if(left >= right){
     System.out.println("满足left>=right,退出递归:   left="+left+",right="+right);
     return;
   }

   // 求解中间下标
   int mid = (left + right) / 2;
   System.out.println("当次排序:left="+left+",right="+right+",mid="+mid);

    // 分解后的左边待排序序列
    mergeSort(array,left,mid);
    // 分解后的右边待排序序列
    mergeSort(array,mid+1,right);

    // 合并函数
    merge(array,left,mid+1,right);

}

3.2.3.合并函数

/**
* 合并函数
* @param array
* @param left
* @param mid
* @param right
*/
public static void merge(Integer[] array,int left,int mid,int right){
  // 左边数组大小(临时数组)
  int[] leftA = new int[mid-left];
  // 右边数组大小(临时数组)
  int[] rightA = new int[right-mid+1];

  // 左边数组填充数据
  for(int i=left;i<mid;i++){
     leftA[i-left]=array[i];
  }

  // 右边数组填充数据
  for(int j=mid;j<=right;j++){
      rightA[j-mid]=array[j];
  }

  // 定义两个位置指针,标记左右数组,合并元素位置
  int L_INDEX=0,R_INDEX=0;
  // 当次合并,array数组中元素起始位置
  int k=left;

  // 比较两个数组的值,将小的一个元素
  // 放入数组array中,实现排序
   while(L_INDEX<leftA.length &&
         R_INDEX<rightA.length){
      // 谁比较小,谁将元素放入大数组中,移动指针,继续比较下一个
      if(leftA[L_INDEX] <= rightA[R_INDEX]){
          array[k++]=leftA[L_INDEX++];
       }else{
           array[k++] = rightA[R_INDEX++];
       }

   }

   // 收尾工作:如果左边的数组有剩余元素,继续填充
   while(L_INDEX<leftA.length){
      array[k++] = leftA[L_INDEX++];

   }

   // 收尾工作:如果右边的数组有剩余元素,继续填充
   while(R_INDEX<rightA.length){
        array[k++] = rightA[R_INDEX++];
   }
}

3.3.测试代码

public static void main(String[] args) {
  // 初始化测试数组
 Integer[] array = {4,5,6,1,2,3};
 // 排序前
 System.out.println("1.排序前数组:" + Arrays.deepToString(array));

 // 2.排序
 System.out.println("2.开始排序-------------------------------");
 sort(array,array.length);

 // 排序后
 System.out.println("3.排序后数组:" + Arrays.deepToString(array));
}

测试结果:

D:\02teach\01soft\jdk8\bin\java 
    com.anan.algorithm.sort.MergeSort
1.排序前数组:[4, 5, 6, 1, 2, 3]
2.开始排序-------------------------------
当次排序:left=0,right=5,mid=2
当次排序:left=0,right=2,mid=1
当次排序:left=0,right=1,mid=0
满足left>=right,退出递归:left=0,right=0
满足left>=right,退出递归:left=1,right=1
满足left>=right,退出递归:left=2,right=2
当次排序:left=3,right=5,mid=4
当次排序:left=3,right=4,mid=3
满足left>=right,退出递归:left=3,right=3
满足left>=right,退出递归:left=4,right=4
满足left>=right,退出递归:left=5,right=5
3.排序后数组:[1, 2, 3, 4, 5, 6]

Process finished with exit code 0

4.讨论分享

 

#考考你答案:
1.你知道归并排序的核心思想吗?
  1.1.归并排序,利用分治思想
  1.2.有两个过程:分解、合并
  1.3.分解过程:
    将大的待排序序列,分解成小的待排序序列,层层分解,直到不能再分解为止
  1.4.合并过程:
     将分解后的小的待排序序列,从小到大,层层合并,在合并过程中实现排序

2.你能用java实现归并排序吗?
  2.1.参考【3.2】节代码实现

 

yhhitall
粉丝 0
博文 37
码字总数 60294
作品 0
梅州
架构师
私信 提问
加载中
请先登录后再评论。
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.4K
6
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.3K
1
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.5K
0
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.2K
1

没有更多内容

加载失败,请刷新页面

加载更多

什么是移动语义? - What is move semantics?

问题: I just finished listening to the Software Engineering radio podcast interview with Scott Meyers regarding C++0x . 我刚刚结束了对Scott Meyers进行的有关C ++ 0x的Software En......

技术盛宴
36分钟前
24
0
算法与数据结构体系课

算法与数据结构体系课【超清原画】 下载地址:百度云盘 从0到工作5年,面试、进大厂、搭建知识体系、拓展技术上限 你不再需要其它算法与数据结构课程了 为什么学算法已经是一个不应该问的问题...

1930133570
今天
21
0
如何停止跟踪并忽略对Git中文件的更改? - How to stop tracking and ignore changes to a file in Git?

问题: I have cloned a project that includes some .csproj files. 我已经克隆了一个包含一些.csproj文件的项目。 I don't need/like my local csproj files being tracked by Git (or bei......

富含淀粉
今天
25
0
Redis阻塞

可能存在问题 内在原因:API或数据结构使用不合理、CPU饱和、持久化阻塞等 外在原因:CPU竞争、内存交换、网络问题等 问题处理: API或数据结构使用不合理,可能存在慢查询或者大对象: 发现...

游泳鸟
今天
17
0
OSChina 周五乱弹 —— 来人,上幼儿园老师跳舞的图!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑:《奇跡の海》- 坂本真綾 《奇跡の海》- 坂本真綾 手机党少年们想听歌,请使劲儿戳(这里) 巴蜀(@巴拉迪维)最近有点闹心了, @巴...

小小编辑
今天
64
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部