8二维数组和常见排序算法.docx

1、8二维数组和常见排序算法这次课我们学习数组中的二维数组，和一些常见的排序算法。在理解上不容易理解，希望大家耐心学习。考验你们逻辑思维的时候到了 学算法，要冷静中带一点嗨。 所谓二维的维，指的是一个“维度. 通俗的讲，如果一维是单一的一条线，那么二维可以看作是一个面。例如，可以用图来比照一下它们：一维数组：二维数组： 对于二维数组，我们可以理解在一维数组当中，每一个格子里又存了一个一维数组。也可以干脆形象一点的理解，二维数组类似于我们画表格的n行n列方式1：int arr = new int52; 定义名称为arr的二维数组，我们简单点理解成5行2列。但果能够理解为大小为5的一维数组里，每个格子

2、放了一个大小为2的一维数组会更好些，因为有利于对内存的理解。 对第一行的第一个格子赋值的写法为： arr00=80; 注意，数组的角标依然是从0开始 方式2：int arr = new int3; 定义了一个名称为arr 的二维数组，定义了3行，但是没有定义列。如果我们用n行n列的思维去理解，这里就不容易理解了，为什么它可以只定义了行却先不定义列？ 所以这里需要用回格子的思维，定义了3个格子，但每个格子里放多大的一维数组先不定义。这样就好理解了。如图： 看上图，每一个格子里再放入一维数组，是不是就成了二维数组？ 神奇的是，每个格子里可以放不同大小的一维数组。如图：图比拟丑，不要嫌弃它用代码表现

3、出来就是：arr0 = new int3;arr1 = new int1;arr2 = new int2; 方式3：int arr = 1,2,8,3,1,2; 第三种方式最为直观，定义了大小为3的二维数组，然后每个格子里放着不同大小的一维数组。但这种方式比拟死板. 1.3 二维数组的应用实际开发当中，二维数组主要用于一些简单的小的数据的分类存储.例如，有这样一个需求：将软件部，产品部，财务部门本月四周的财务数据存到数组里。 很显然，我们可以用一维数组，将3个部门的数据都存到里边。但是这样太杂乱，难以区分哪些数据分别输入哪个部门，如果部门有10个，那显然一维数组里的这一堆数据就更混乱。所以，我

4、们就需要用二维数组： 定义一个大小为3个二维数组，arr0用来存软件部，arr1用来存产品部，arr2用来存财务部. 那么有同学会问我怎么记得住哪个下标属于什么部门。这个简单，用变量标识就可以了，例如定义软件的整型变量 int ruanJianBu = 0; 然后再数组下表中引用它：arrruanJianBu = 2,3,6; 这样不就一目了然了么？ 同志们，学完了以上章节， java的入门根底语法知识就告一段落了。不知道你们感触如何呢？如果你坚持完成了每一次的课后练习，相信你已经有所收获接下来，要跟大家介绍一些常见的排序算法。算法，实际项目开发当中其实用的并不多用，但如果你立志将来往数据分析

5、大牛方向走，还是要从点滴做起，把算法学好。2. 常见的排序算法 首先大家要理解，什么是算法。通俗的理解就是为了得到某个结果的一种计算方法，或者说是一种游戏规如此，通过这些不同的规如此我们能够获得同样的结果。 其次，要学会简单对2个变量进展交换数值，最简单的方式是，设置一个中间临时变量temp,例如int a = 2; int b = 3; 如何将它们交换，把3赋值给a,把2赋值给b? 有些同学说直接int a =3 ;int b=2; 不就可以了？不要这么嗨. 如果数值是用户输入的变量呢？ 常见的做法是设置一个中间变量temp, 然后 temp = a; a=b; b=temp;这样就达到了两

6、个变量相互交换的效果。这方式虽然笨拙，但却最容易看懂，也谈不上耗内存资源，开发中经常使用。2.1 排序算法的分类 排序算法大致可分为以下几类。(1)插入排序：直接插入排序，希尔排序(2)交换排序：冒泡排序，快速排序(3)选择排序：直接选择排序，堆排序(4)归并排序(5)分配排序：基数排序我们这里先学习前面3类. 已经足够大家折腾了.2.2 直接插入排序 直接插入排序法主要思想类似于玩扑克牌时按从小到大整理牌的过程，第一趟比拟最前面的2个数，排序好。然后第二趟用第三个数与前面排序好的2个数进展比拟，进展插入排序；第三趟用第4个数与前面排序好的3个数进展比拟，插入到他们当中去.以此类推。如图：那么

7、如何用java来实现呢？很明显，如此重复的动作，用for循环是最适合的了。用多少个for循环？我们可以这样思考，在这个过程中，主要有2个动作： (1)参加第nX牌，也就是待比拟插入的牌 (2)与前面排序好的数值(我们称之为有序数列)进展比拟所以，我们可以用2个for循环来写这个算法：图比拟小，看不清的同学放大文档就可以看清楚了。有些同学可能会问，为什么第二层循环里，temp变量假如不小于arrj，就会停止这一层的循环。举个列子就明白了， 假设有序数列为 1 , 5,7 参加一个比拟数字为 8，这个8相当于待比拟的temp变量，本身，1,5,7就是一个从小到大排好序的数列，那么是不是只要用8与这

8、个数列的最后一位开始比就可以省事了呢？2.3 希尔排序 希尔排序也是插入排序的一种，可以看作是直接插入排序的优化。为什么说它优化了直接插入排序，因为希尔排序采用了先分组，再在各组里进展插入排序。 希尔排序的玩法是这样的：先取一个小于n的整数d1作为第一个增量，把文件的全部记录都分组。即所有距离为d1倍数的都放在同一组中，现在各组内进展“直接插入排序。然后，取第二个增量d2d1,重复进展增量为d1时的做法，直到增量为1也就是说所有数都已经放在了同一组中进展排序之后终止。 通常增量d，取的是 数组长度的二分之1. 即所 a.length/2 运算。看完上面这段，相信大局部同学都吐血了吧. 作为要画

9、图的我，也有股血液从胸口涌出.Java代码实现如下：要想理解希尔排序，首先要理解好直接插入排序，希尔排序改良了直接插入排序时每次只能将数据移动一位的低效做法。但希尔排序是不稳定的，当有个一样的数字被分在不同的组里时，可能会被屡次移动。其稳定性会就被打乱。 有同学会问，为什么代码中出现“语句1，语句2, 没错，那个是留给大家的作业，只要理解了算法，就能填写完整。2.4 简单项选择择排序 它的根本思想十分容易理解： 在待排序的一组数中，选择最小的一个数与第一个位置的数交换；接着在剩下的数当中再找出最小的数与第二个位置的数交换，直到倒数第二个数和最后后一个数比拟为止。JAVA算法的实现 这个地方同样

10、的留给大家来完成. 不要怕，要先理解好算法思想，再下周，这个算法并不难。2.5 堆排序 堆排序是一种树结构的选择排序，是对直接选择排序的改良。在开始介绍堆排序之前，首先大家要理解“树的概念。 树是一种非常非常重要的数据结构。画 出来就是如下图：图丑见谅而堆排序是利用了树当中的“完全二叉树，所谓完全二叉树，就是指除了最后一层外，每一层上的结点数均达到了最大值；在最后一层上只缺了假如干个右结点(或者说右孩子)如图：大家看，它最后一层少了一个右孩子，而其他层都是满的，即有左孩子又有右孩子.如果是用数组来存储树结构的话，要理清下脚标存的分别是什么. 假设某个元素为序号为x, 我们用n来表示元素的总数，

11、那么x的X围是 0到n-1 。 如果这个元素有左孩子，那么左孩子的位置是 2x+1；如果有右孩子，右孩子的位置是2x+2,如果有父结点点.(例如途中1号就为2,3的父结点)同时我们又分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。(这句话是堆算法的精髓) 而堆排序也可以看作是冒泡，选择排序的一种类似算法，只是选取最大元素的过程就是用最大堆。而且最大堆的最大元素一定在第0位置，构建好堆之后，交换0位置元素与顶. 我们通过画图来模拟这个过程：例如我们要对数组16,7,3,20,17,8,进展堆排序。那么：步骤一：构建完全二叉树，得到 就是根据完全二叉树除

12、了最后一层之外，其他层结点数达到最大值，来进展构建步骤二：构造初始堆，即任何一非叶节点的数值不大于或者不小于其左右孩子节点的数值(这里我们只考虑后一种情况：任何一非叶节点的数值不小于其左右孩子节点的)调整之后： 步骤三：开始排序 也就是说此时数组里的存储是这样的：我们可以看出，通过步骤二之后，顶点的肯定是所有数里面最大的数. 此事，便可将它与最后一个数字的位置交换(因为从小到大排序的话肯定最后一格是最大了嘛).因此就会变成：此时可以将 20结点去掉了。剩下：但是这个时候，又不满足父结点要大于左右结点了，怎么办，再次调整为： 数组变成： 好了，这回最顶上的17是最大了吧，继续将它与最后一个结点交

13、换，并放到数组里.此时数组里的样子已经变成：去掉17号，树的样子变成了：好了，又不满足父结点要大于左右结点了，再次调整，然后再把顶部最大的选出来就这样来回折腾，最后就能将这串数给排序好.经过上面几段文字和图画，想必大家已经快吐血了吧。那么用代码怎么实现呢？不要害怕，只要理清了思路，写代码只是在键盘上敲字母的事情，哈哈。思路如下：(1)构建最大堆(2)选择末尾项，并与最顶上的元素交换(即下标为0的元素)(3)由于步骤2可能会破坏了最大堆的性质，即最顶上的已经不再是最大的元素，需要写一个方法maxHeap来调整堆，然后再重复第二步.而maxHeap，就是整个算法的核心方法在看代码之前，如果对自己有

14、信心，大家不妨试试自己动手先挑战一下，一定会有很大收获！2.6 冒泡排序 冒泡排序的主要思想是对于当前还没有排序好的所有数，自上而下对相邻的两个数依次进展比拟和调整，让较大的数往下沉，较小的数往上冒。这样一来就很形象的表现出了冒泡这个现象。 需要大家注意的是：冒泡排序是比拟根底的排序算法，通常在公司面试时，都会要求写出冒泡排序，所以是必须要掌握的算法。 我们来看下面这个： 例如图中的数字3，就是不断的从底部与它前面的数字比拟，只要比它前面的数字小，就交换。不断的往上冒.那么写成java代码就是：冒泡排序还是比拟容易理解，但它的效率不高. 我们做这样一个假设，假设有一组数组是1,2,3,4,5

15、,它本身就是有序的，那么如果采用冒泡，是不是同样又要去一个一个的比拟？那么我们需要用什么样的方式可以优化一下冒泡排序？思考一下，这个问题将留到作业让大家解决.2.7 快速排序主要的思想：选择一个基准元素，常用的做法是选择第一元素或者最后一个元素，通过一趟扫描，将待排序的数组分成2局部，一局部比基准元素小，一局部大于等于基准元素，此时基准元素在其排好序之后的正确位置，然后用同样的方式递归的排序划分的两局部.快速排序的思想理解起来是比拟绕的，关键要理解基准数的作用. 代码如下：算法的核心在于2点：(1)用每组开头的数作为基准，分别从前后进展扫描排序之后，基准数左边的值都小于基准数右边的值.2递归的

16、调用这个这扫描的过程不断的对上下位表进展排序。递归算法是非常重要算法，也是非常神奇的算法，虽然递归并不难理解，但不要小看递归，能够很好的理解和运用递归，是一个算法好手的标准。在日常的开发当中，巧妙的运用递归会让同事对你刮目相看。学习完以上几个算法，是不是满脑子发蒙？想吐血，或者想放弃学习java？ 其实不用担心，经常学习算法，数据结构，可以开拓我们的逻辑思维，学不好也没有关系，平时开发当中运用复杂算法的情况并不多见。写得复杂了，同事维护起来是件很痛苦的事情。但是简单的冒泡排序,直接插入排序要会。剩下的归并排序，和基数排序，感兴趣的同学可以继续找资料学习，或者与我交流. 简单提一下，归并算法用的是2个数或者2个以上的数进展合并之后排序，直到合并所有的数为止；基数排序如此分别利用数值的个，十，百.位串起来进展排序。