资源简介

(共16张PPT)
5-3-2 排序算法的应用
5-3-2 排序算法的应用
穷举算法
递归算法
动态规划算法
算法
数据存储
数组
链表
跳跃表算法
遍历
线性遍历
树结构遍历
平衡树
排序算法的发展变化
解决n个数的升序排列问题
冒泡排序
依次比较前后两个元素，如果逆序就交换两个位置上的元素，将最小数交换到最前面，这样的过程重复n-1遍即可实现，算法的时复杂度为O(n2)。
n个元素冒泡排序的比较次数是n(n-1)/2，最坏情况下的交换次数要达到n(n-1)/2，交换频繁，影响效率。
选择排序
如果不交换元素位置，待找到无序区中的最小元素后，直接把最小元素交换到有序区的末位位置，这样就减少了交换的次数，但时间复杂度依然为O(n2)。
插入排序
在访问无序区元素的过程中，将当前访问的元素直接在有序区中找一个合适的位置插入即可。
希尔排序
既然插入排序在基本有序的情况下性能相对较好，那就想办法达到这样的状态，于是有人想出了跳跃分割的方式，将相距某个增量的数据组成一个子序列，这样就能保证在子序列内分别进行插入排序后，得到的结果基本有序。
排序算法的发展变化
解决n个数的升序排列问题
快速排序和归并排序
快速排序和归并排序都利用了分治思想，核心在于“分而治之，各个击破“
快速排序计算过程：
（1）从数值队列中选择一个基准元素。
（2）将队列中的其他元素与基准元素比较，比基准元素小的元素放在基准元素的左边，比基准元素大的放在右边，则队列被基准元素分为左右两个区间。
（3）对两个区间的值分别递归步骤（2），使其最终形成有序的序列。
排序算法的发展变化
解决n个数的升序排列问题
例1
对于队列数值“4、3、6、2、5”采用快速排序进行升序排序
以上采用的排序方法都属于内排序，内排序是指能够在内存中完成的排序，当计算机内存小于数据本身大小时，无法一次性将数据加载到内存，这时候就需要采用外排序的方式。
外排序主要是针对大文件的排序，将需要排序的数据文件存放到存储器中，每次加载部分数据到内存，不断进行内存和外部存储器之间的数据交换，最终保证文件中的每个数据都完成排序。
例2 有4GB的数据文件需要进行排序，当前操作系统的有效可用内存为1GB，则需要按照外归并排序的流程完成排序。
（3）采用四路归并的方式进行归并排序：在4个1GB文件中，分别读取200MB数据存入内存的输入缓冲区，共占用计算内存800MB，将剩余的200MB作为输出缓冲区，如图所示。
（1）将4GB的数据文件平均拆分为4个1GB的数据文件
（2）将每份1GB数据文件加载到内存，采用内排序的方式（如快速排序）在内存中完成对该数据文件的排序，并将排序后的结果写入文件。
（4）将输入缓冲区的四路数据进行归并排序，依次存入输出缓冲区，当输出缓冲区满时，则写入文件，当缓冲区中某路数据输入完毕后，则再向文件中读取200MB数据存入输入缓冲区，不断进行该过程直到所有的数据通过四路归并的方式完成排序。
例2 有4GB的数据文件需要进行排序，当前操作系统的有效可用内存为1GB，则需要按照外归并排序的流程完成排序。
设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，请写出按二路归并方法对该序列进行升序排序的过程。
问题与讨论
Q D F X A P N B Y M C W
Q D F X A P
N B Y M C W
Q D F
X A P
N B Y
M C W
Q D
X A
F
P
D
Q
X
A
N B
M C
Y
W
N
B
M
C
D Q
A X
B N
C M
F
P
Y
W
D F Q
A P X
B N Y
C M W
A D F P Q X
B C M N W Y
A B C D F M N P Q W X Y
F
P
Y
W
分治法
分解成子问题
分别解决
合并答案
4.1.2 立足系统架构的算法发展
并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。
它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。
4.1.2 立足系统架构的算法发展
从程序和算法设计的角度来看，并行计算可分为任务并行和数据并行。
任务并行是不同的CPU执行不同的任务，处理相同的数据。
数据并行是每个核心执行相同的命令，处理不同的数据。
在现有算法不适应时，要善于发掘和利用现有串行算法中的并行性，合理地选择算法，并且合理地设置阈值，能够十分有效地提高计算机的运行效率。
4.1.2 立足系统架构的算法发展
4.1.3 基于大数据和人工智能的算法发展
课堂小结
思考与练习
题目描述：给定一个由数字组成的序列，编程实现利用归并排序将其按照从小到大的顺序进行排序。
输入数据：7,6,3,8,2,9,1,4,5
输出结果：1,2,3,4,5,6,7,8,9

展开更多......

收起↑