排序概述.ppt
排序概述排序概述一、概述数据处理的核心运算就是排序，如果数据数据处理的核心运算就是排序，如果数据是按关键字大小有序排列的，就可以提高是按关键字大小有序排列的，就可以提高处理数据的效率。处理数据的效率。排序是计算机程序中一种基础性操作，研排序是计算机程序中一种基础性操作，研究和掌握各种排序方法是非常重要的。究和掌握各种排序方法是非常重要的。排序是程序设计中一种重要的运算，功能排序是程序设计中一种重要的运算，功能是将一个数据元素（记录）的任意序列重是将一个数据元素（记录）的任意序列重新排列成一个按关键字有序的序列。新排列成一个按关键字有序的序列。一、概述排序定义：排序定义：给定具有给定具有n n个记录个记录Rl，R2，Rn的文件，每个记录的文件，每个记录Ri都有一都有一个关键字个关键字K Ki i (1in)(1in)且对任意两个关键字且对任意两个关键字Ki和和Kj都有如下都有如下关系：关系：KiKj 或或 KiKj 或或 KiKj排序问题就是按照关键字值的某种关系，寻找一个排列排序问题就是按照关键字值的某种关系，寻找一个排列S S，使得使得 KS(i)KS(i+1)或或 KS(i)KS(i+1)(1in-1)(1in-1)从而可得到文件中各记录的一种排序：从而可得到文件中各记录的一种排序：(RS(1)，RS(2)，RS(n)。排序就是按关键字值的递减排序就是按关键字值的递减（K KS(i)S(i)KKS(i+1)S(i+1)）或递增（或递增（K KS(i)S(i)KKS(i+1)S(i+1)）次序，把文件中的）次序，把文件中的各记录一次排列起来，可使得一个无序的各记录一次排列起来，可使得一个无序的文件变成有序文件的一种操作。文件变成有序文件的一种操作。一、概述上述排序定义中的关键字上述排序定义中的关键字Ki可以是记录可以是记录Ri的的一个关键字或者是若干数据项的组合。若一个关键字或者是若干数据项的组合。若Ki是唯一的，则排序后得到的结果是唯一的；是唯一的，则排序后得到的结果是唯一的；果果Ki是不唯一的，假设是不唯一的，假设Ki=Kj，且在排序钱，且在排序钱序列中若序列中若Ri领先于领先于Rj，若在排序后的系列中，若在排序后的系列中Ri仍领先于仍领先于Rj，则称所用的排序方法是稳定，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中的；反之，若可能使排序后的序列中Rj领先领先于于Ri，则称所用的排序方法是不稳定的。，则称所用的排序方法是不稳定的。一、概述在排序的过程中需要进行下列两种基在排序的过程中需要进行下列两种基本操作：本操作：（1）比较两个关键字的大小）比较两个关键字的大小（2）将记录从一个位置移至到另一个位置。）将记录从一个位置移至到另一个位置。一、概述要排序文记录序列，有三种常见的存储表示方要排序文记录序列，有三种常见的存储表示方法：法：（1）顺序结构）顺序结构要排序的初始文件的各个记录，按其自然顺序要排序的初始文件的各个记录，按其自然顺序存放在连续的一块内存空间中。排序时要移动存放在连续的一块内存空间中。排序时要移动记录才行。记录才行。（2）链式结构）链式结构将要排序的每个记录（数据元素）作为链表结将要排序的每个记录（数据元素）作为链表结构存储，并按原始次序链接起来。排序时，不构存储，并按原始次序链接起来。排序时，不需要移动记录元素，而只需要修改指针。需要移动记录元素，而只需要修改指针。一、概述（3）地址向量结构）地址向量结构待排序记录存放在一组地址连续的存储待排序记录存放在一组地址连续的存储单元，同时另设一个指示各个记录存储单元，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录记录本身，而移动地址向量中这些记录的的“地址地址”，在排序结束后，再按照地，在排序结束后，再按照地址向量中的值调整记录的存储位置。址向量中的值调整记录的存储位置。一、概述内部排序内部排序整个排序过程都在内存进行的排序称为内排序。整个排序过程都在内存进行的排序称为内排序。外部排序外部排序待排序的数据元素量大，以致内存一次不能容待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。问的排序称为外排序。一、概述二、插入排序基本思想：在一个已排好序的记录子集的基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到序地插入到已排好序的记录子集中，直到将所有待排序的记录全部插入为止。将所有待排序的记录全部插入为止。直接插入排序直接插入排序*折半插入排序折半插入排序*2路插入排序路插入排序表插入排序表插入排序希尔排序希尔排序*1、直接插入排序直接插入排序是一种最简单的排序方法，直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数的有序表中，从而得到一个新的，记录数增增1的有序表。的有序表。插入前：（插入前：（1 3 5 8）2 7 4 9 6 有序有序 无序无序 插入后：（插入后：（1 2 3 5 8）7 4 9 6 有序有序 无序无序1、直接插入排序初始关键字：初始关键字：45 62 35 77 92 55 14 45 62 35 77 92 55 14 3535 i=2 45 62 35 77 92 55 14 i=2 45 62 35 77 92 55 14 3535i=3 35 45 62 77 92 55 14 i=3 35 45 62 77 92 55 14 3535i=4 35 45 62 77 92 55 14 i=4 35 45 62 77 92 55 14 3535i=5 35 45 62 77 92 55 14 i=5 35 45 62 77 92 55 14 3535i=6 35 45 55 62 77 92 14 i=6 35 45 55 62 77 92 14 3535i=7 14 35 45 55 62 77 92 i=7 14 35 45 55 62 77 92 3535i=8 14 35 i=8 14 35 3535 45 55 62 77 92 45 55 62 77 92 图9.4直接插入排序示例例子例子:39,28,55,80,75,6,17,45,281、直接插入排序时间复杂度：时间复杂度：O(n2)直接插入排序是稳定的排序方法。直接插入排序是稳定的排序方法。直接插入排序算法简便，比较适合于待排直接插入排序算法简便，比较适合于待排序记录数目较少且基本有序的情况。当待序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能排记录数目较大时，直接插入排序的性能不是很好。下面在直接插入排序的基础上，不是很好。下面在直接插入排序的基础上，为减少为减少“比较比较”和和“移动移动”这两种操作的这两种操作的次数，对排序算法进一步改进。次数，对排序算法进一步改进。1、直接插入排序2、二分插入排序直接插入算法虽然简单，但当记录数目比直接插入算法虽然简单，但当记录数目比较大时，比较次数将会大大增加，对于有较大时，比较次数将会大大增加，对于有序表为了减少关键字的比较次数，可采用序表为了减少关键字的比较次数，可采用二分插入排序。二分插入排序。基本思想：用二分查找法在有序表中找到基本思想：用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插正确的插入位置，然后移动记录，空出插入位置，再进行插入。入位置，再进行插入。若有若有8 8个记录已排序，插入新的关键字为个记录已排序，插入新的关键字为6536531 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 6060 87 170 275 503 512 897 90887 170 275 503 512 897 908low=1 low=1 high=8 high=8 mid=(low+high)/2=(1+8)/2=4 mid=(low+high)/2=(1+8)/2=42、二分插入排序若有若有8 8个记录已排序，插入新的关键字为个记录已排序，插入新的关键字为6536531 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 6060 87 170 275 503 512 897 90887 170 275 503 512 897 908 low=4 low=4 high=8 high=8 mid=(low+high)/2=(5+8)/2=6 mid=(low+high)/2=(5+8)/2=62、二分插入排序若有若有8 8个记录已排序，插入新的关键字为个记录已排序，插入新的关键字为6536531 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 6060 87 170 275 503 512 897 90887 170 275 503 512 897 908 low=1 high=8 low=1 high=8 mid=(low+high)/2=(7+8)/2=7 mid=(low+high)/2=(7+8)/2=72、二分插入排序（1 1）取关键字）取关键字653653，与序列中间位置的关键字，与序列中间位置的关键字比较，比较，653275653275，在后半区找继续；，在后半区找继续；（2 2）再与后半区中间位置的关键字比较，）再与后半区中间位置的关键字比较，653512653512，再继续在后半区找；，再继续在后半区找；（3 3）再与后半区中间位置的关键字比较，）再与后半区中间位置的关键字比较，653897653897，经三次比较找到插入位置，然后插入，经三次比较找到插入位置，然后插入653653。2、二分插入排序二分插入仅减少了比较次数，而记录的移二分插入仅减少了比较次数，而记录的移动次数不变，时间复杂度仍为动次数不变，时间复杂度仍为O(n2)。二分插入排序时稳定的排序方法。二分插入排序时稳定的排序方法。2、二分插入排序3、希尔排序希尔排序（希尔排序（ShellShells metheds methed）又称）又称“缩小增量排序缩小增量排序”，是一种基于插入，是一种基于插入思想的排序方法，但在时间效率上较思想的排序方法，但在时间效率上较前述几种排序方法有较大的改进。它前述几种排序方法有较大的改进。它利用了直接插入排序的最佳性质。利用了直接插入排序的最佳性质。将待排序的关键字序列分成若干个较将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入小的子序列，对子序列进行直接插入排序，再改变分组进行组内排序，直排序，再改变分组进行组内排序，直到使整个待排序序列有序。在时间耗到使整个待排序序列有序。在时间耗费上，较直接插入排序法的性能有较费上，较直接插入排序法的性能有较大的改进。其算法时间复杂度为大的改进。其算法时间复杂度为O(n2)，但是，若待排记录序列为但是，若待排记录序列为“正序正序”时，时，其时间复杂度可提高至其时间复杂度可提高至O(n)。3、希尔排序3、希尔排序基本思想：基本思想：先将待排序记录序列分割先将待排序记录序列分割成若干个成若干个“较稀疏的较稀疏的”子序列，分别子序列，分别进行直接插入排序。经过上述粗略调进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入最后再对全部记录进行一次直接插入排序。排序。具体实现时，首先选定两个记录间的距离具体实现时，首先选定两个记录间的距离d d1 1，在整个待排序记录序列中将所有间隔为在整个待排序记录序列中将所有间隔为d d1 1的的记录分成一组，进行组内直接插入排序，记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离然后再取两个记录间的距离d d2 2d d1 1，在整个，在整个待排序记录序列中，将所有间隔为待排序记录序列中
