数据结构排序

1、第七章 排序71 排序的基本概念72 插入排序73 交换排序74 选择排序75 归并排序*76 基数排序77 内排序方法的比较 71 排序的基本概念1排序对象 由记录序列组成的文件，每一个记录又由若干数据项组成。由于文件是记录的序列，所以从逻辑结构上看它是个线性表 表7.1 学生成绩表2排序码 通常把选作排序依据的数据项的值称为排序码。3排序的定义 将一组记录按照某个排序码非递增或非递减的次序重新排列的过程。一条记录一个数据项4排序的稳定性 排序码相同的两个记录经过排序之后，其相对次序保持不变，称该排序方法是稳定的；反之，称该排序方法是不稳定的。 5内部排序与外部排序 整个排序过程全部在内存中

2、进行，这种排序称为内部排序。涉及内外存之间数据交换的排序称为外部排序。外部排序的速度比内部排序的速度要慢得多。6.排序两种基本操作： 1）比较两个记录排序码的大小；2）将记录从一个位置移动到另一个位置。7.常见排序方法：插入排序、交换排序、选择排序、归并排序、基数排序8排序方法的评价 时间复杂度，空间复杂度、稳定性和简单性等 9记录序列采用顺序存储结构，其C语言描述如下：#define N 20typedef struct int key; /*定义排序码*/ DataType other; /*定义其他数据项*/ RecType; /*记录的类型*/RecType RN+1;N为待排序记录的

3、个数，R0不存放记录，原因有两个:其一，使数组的下标和记录的序号对应；其二，将R0留作他用，比如做监视哨或者做记录交换的辅助空间。72 插入排序插入排序（Insertion Sort）的基本思想是：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。插入排序主要包括两种方法：直接插入排序和希尔（Shell）排序。721 直接插入排序 直接插入排序的基本思想：待排序的n个记录存放在数组R1Rn中，把数组分成一个有序表和一个无序表，开始时有序表中只有一个记录R1，无序表中含有n-1个记录R2Rn。在排序的过程中每一次从无序表中取

4、出第一个记录，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表成为空表，有序表就包含了全部n个记录，排序完毕。 将一个记录插入到有序表的过程称为一趟直接插入排序。 举例：排序码初始序列为（78，38，32，97，78， 30，29，17） R1 R2 R3 R4 R5 R6 R7 R8 78 38 32 97 78 30 29 17 （初始状态） 38 78 32 97 78 30 29 17 （插入38后） 32 38 78 97 78 30 29 17 （插入32后） 32 38 78 97 78 30 29 17 （插入97后） 32 38 78 78 9

5、7 30 29 17 （插入78后） 30 32 38 78 78 97 29 17 （插入30后） 29 30 32 38 78 78 97 17 （插入29后） 17 29 30 32 38 78 78 97 （插入17后） 直接插入排序过程图示直接插入排序算法的C函数如下：void insertSort (RecType R) /*对数组R中的记录进行直接插入排序*/int i,j; for(i=2;i=N;i+) /*待插入记录为R2，RN*/ R0=Ri; /*将待插入的记录Ri放入R0中*/ j=i-1; while(R0.keyRj.key) /*查找记录Ri应该插入的位置*/

6、Rj+1=Rj-; /*将排序码大于Ri.key的记录后移*/ Rj+1=R0; /*插入Ri*/ 直接插入排序算法的性能分析时间效率 最好情况下为O(n) 最坏和平均时间复杂度都为O(n2)空间效率 O(1)稳定的排序方法722 希尔排序 希尔排序的基本思想是：将待排序记录序列分成几个组，在每一组内分别进行直接插入排序，使得整个记录序列部分有序；重复此过程，直到所有记录都在同一组中，最后对所有的记录进行一次直接插入排序即可。 如何分组 将数组R1Rn的记录分为d个组，使下标距离为d的记录在同一组，即R1，R1+d，R1+2d，. 为第一组，R2,R2+d,R2+2d,. 为第二组，以此类推，

7、Rd,R2d，R3d, . 为最后一组（第d组），这里的d叫做步长（或增量值）。 这种分组在每一组内做直接插入排序的时候，记录移动一次，能跨跃较大的距离，从而加快了排序的速度。 希尔排序要对记录序列进行多次分组，每一次分组的步长d都在递减，即d1d2d3dt，直到最后一次选取步长dt =1，所有的记录都在一组中，进行最后一次直接插入排序， 我们将每一次分组排序的过程称为一趟希尔排序。举例：设排序码初始序列:(36，25，48，65，12，25，43，57，76，32) R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 36 25 48 65 12 25 43 57 76 32 （初

8、始状态） 36 25 （d1=5） 25 43 48 57 65 76 12 32 25 25 48 65 12 36 43 57 76 32 （一趟希尔排序结果） 25 65 43 32 （d2=3） 25 12 57 48 36 7625 12 36 32 25 48 43 57 76 65 （二趟希尔排序结果） 25 12 36 32 25 48 43 57 76 65 （d3=1） 12 25 25 32 36 43 48 57 65 76 （三趟希尔排序结果） 希尔排序过程图示一趟希尔排序算法的C函数：void shellInsert(RecType R,int d) /*按步长d进

9、行分组，每一组分别做直接插入排序*/int i,j; for (i=d+1;i0&Rj.keyR0.key) Rj+d=Rj; j=j-d; /*记录后移，查找插入位置*/ Rj+d=R0; /*插入记录*/ 整个希尔排序算法的C函数：void shellSort(RecType R，int d,int t) /*d0dt-1为每一趟分组的步长*/ int k; for(k=0;kt;k+) shellInsert(R,dk);希尔排序算法的性能分析当n较大时，希尔排序的平均时间复杂度在O(nlog 2n)和O(n2)之间，大约为O(n1.5)。算法的空间复杂度是O(1)。希尔排序是不稳定的。

10、73 交换排序 交换排序的基本思想是：两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。 本节主要介绍两种交换排序：起泡排序和快速排序。731 起泡排序 起泡排序的基本思想是：首先将记录R1的排序码与记录R2的排序码做比较（从上向下），若R1的排序码大于R2的排序码，则交换两个记录的位置，使排序码大的记录（重者）往下“沉”（移到下标大的位置），使排序码小的记录（轻者）往上“浮”（移到下标小的位置）；然后比较R2和R3的排序码，同样轻者上浮，重者下沉；依此类推，直到比较Rn-1和Rn的排序码，若不符合顺序就交换位置，称此过程为一趟起泡排序，结果是R1Rn中

11、排序码最大的记录沉“底”，即放入Rn中。接下来，在R1Rn-1中进行第二趟起泡排序，又会将一个排序码最大的记录沉“底”，放到Rn-1中。这样重复进行n-1趟排序后，对于n个记录的起泡排序就结束了，数组R1Rn成为有序表。 举例：设有8个记录的排序码初始序列为（36，25，48，12，25，65，43，57） R1 36 25 25 25 25 25 25 25R2 25 36 36 36 36 36 36 36R3 48 48 48 12 12 12 12 12R4 12 12 12 48 25 25 25 25R5 25 25 25 25 48 48 48 48R6 65 65 65 65

12、65 65 43 43R7 43 43 43 43 43 43 65 57R8 57 57 57 57 57 57 57 65一趟排序的过程图示R1 R 2 R 3 R4 R5 R6 R7 R 836 25 48 12 25 65 43 57 （初始状态）25 36 12 25 48 43 57 65 （1趟排序结果）25 12 25 36 43 48 57 65 （2趟排序结果）12 25 25 36 43 48 57 65 （3趟排序结果）12 25 25 36 43 48 57 65 （4趟排序结果）12 25 25 36 43 48 57 65 （5趟排序结果）12 25 25 36

13、43 48 57 65 （6趟排序结果）12 25 25 36 43 48 57 65 （7趟排序结果）起泡排序的全过程图示起泡排序算法的C函数如下：void bubbleSort(RecType R) RecType x; int i,j,flag; for (i=1;iN;i+) /*i排序的趟数，n个记录最多进行n-1趟排序*/ flag=1; /*flag表示每趟排序是否交换，比较之前置为1 ，表示无交换*/ for (j=1;jRj+1.key) x=Rj;Rj=Rj+1;Rj+1=x; flag=0; if (flag) break; /*若没有交换，表明已有序，结束循环*/ 起泡

14、排序的性能分析时间效率：起泡排序的最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，可以证明它的平均时间复杂度也为O(n2)。空间效率：在整个算法中，需要一个用于交换记录的辅助空间，所以起泡排序的空间复杂度为O(1)。稳定性：起泡排序是稳定的。732 快速排序快速排序(Quick Sort)也被称为划分排序或分区排序，它是目前所有的内部排序方法中速度最快的一种，快速排序是对起泡排序的一种改进。快速排序的基本思想是：在R1Rn中，任意选取一个记录作为“基准记录”，将整个数组划分为两个子区间：R1Ri-1和Ri+1Rn，前一个区间中记录的排序码都小于或等于基准记录的排序码，后一区间中记录的排序

15、码都大于或等于基准记录的排序码，基准记录落在排序的最终位置Ri上，我们称该过程为一次划分（或一趟快速排序）。若R1Ri-1和Ri+1Rn非空，分别对每一个子区间再重复这样的划分，直到所有子区间为空或只剩下一个记录，使整个数组达到有序。 举例：排序码初始序列为（49，14，38，74，96，65，8，49，55，27），对其进行快速排序。 一次划分的详细操作过程为：（1）选取R1为基准记录，将其复制到R0中；（2）设置两个搜索“指针”并赋初值为：low=1；high=10；（3）若lowhigh，从high位置向前搜索排序码小于R0.key的记录，如果找到，将Rhigh移动到Rlow位置，然后从

16、low位置向后搜索排序码大于R0.key的记录，如果找到，将Rlow移动到Rhigh位置，重复上述操作，直到两个“指针”相遇，即low=high，找到了基准记录的最终排序位置low，由于这个位置的原值已经被移走，可以将R0赋值给Rlow，一次划分完毕。R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 49 14 38 74 96 65 8 49 55 27 14 38 74 96 65 8 49 55 27 low=1 high=10从high向前搜索小于R0.key的记录，找到R10，将R10移到Rlow 27 14 38 74 96 65 8 49 55 low=1

17、 high=10 从low向后搜索大于R0.key的记录，找到R4，将R4移到Rhigh 27 14 38 96 65 8 49 55 74 low=4 high=10 从high向前搜索小于R0.key的记录，找到R7，将R7移到Rlow 27 14 38 8 96 65 49 55 74 low=4 high=7 从low向后搜索大于R0.key的记录，找到R5，将R5移到Rhigh 27 14 38 8 65 96 49 55 74 low=5 high=7 从high向前搜索小于R0.key的记录，两指针相遇low= high 27 14 38 8 65 96 49 55 74 low

18、 high 一次划分结束，填入基准记录：Rlow=R0，此时数组分成前后两个子区间 27 14 38 8 49 65 96 49 55 74 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 14 38 74 96 65 8 49 55 27 初始状态 27 14 38 8 49 65 96 49 55 74 第一层划分结果 8 14 27 38 49 55 49 65 96 74第二层划分结果 8 14 27 38 49 49 55 65 74 96 第三层划分结果 快速排序全过程图示一次划分的C函数如下：int partition(RecType R ,int low,i

19、nt high) /*一趟快速排序*/int k; R0=Rlow; /*以子表的第一个记录作为基准记录*/ k=Rlow.key; /*取基准记录排序码*/ while(lowhigh) /*从表的两端交替地向中间扫描*/ while(low=k) high-;if(lowhigh) /*比基准记录小的交换到前端*/ Rlow=Rhigh; while(lowhigh)&(Rlow.key=k) low+; if(lowhigh) /*比基准记录大的交换到后端*/ Rhigh=Rlow; Rlow=R0; /*基准记录到位*/ return low; /*返回基准记录所在位置*/快速排序递归

20、算法的C函数如下void QSort(RecType R,int low,int high) /*对数组R的子区间lowhigh做快速排序*/int part; if(lowhigh) part=partition(R,low,high);/*将表一分为二*/ QSort(R,low,part-1); /*对前面的子区间快速排序*/ QSort(R,part+1,high); /*对后面的子区间快速排序*/快速排序对应的二叉树起泡排序的性能分析时间效率：最好的情况下，时间复杂度为O(nlog2n）；在最坏情况下，O(n2)；平均时间复杂度仍为O(nlog2n)。空间效率：最好空间复杂度为O(l

21、og2n)；最坏空间复杂度为O(n)；平均空间复杂度也为O(log2n)。快速排序是一个不稳定的排序方法。74 选择排序 选择排序（Selection Sort）的基本思想是：每一次从待排序记录序列中选取一个排序码最小（或最大）的记录，放在待排序记录序列的最前面（或最后面），重复此过程，直到所有的记录按排序码排好序。 本节介绍直接选择排序和堆排序两种方法。741 直接选择排序直接选择排序（Straight Select Sort）的基本思想是：假定待排序的n个记录存储在数组 R1Rn中，经过比较选出排序码最小的记录，将其同R1交换，也就是将排序码最小的记录放到待排序区间的最前面，完成第一趟直接

22、选择排序（即i=1）。第i（1in-1）趟直接选择排序的结果是将RiRn中排序码最小的记录放到待排序子区间的最前面，即与Ri交换位置。经过n-1趟直接选择排序，R1Rn成为有序表，整个排序过程结束。举例：设有8个待排序记录的排序码为（25，36，48，65，25，12，43，57）。R1 R2 R3 R4 R5 R 6 R7 R 825 36 48 65 25 12 43 57 （初始状态）12 36 48 65 25 25 43 57 （第1趟排序的结果）12 25 48 65 36 25 43 57 (第2趟排序的结果）12 25 25 65 36 48 43 57 (第3趟排序的结果）1

23、2 25 25 36 65 48 43 57 (第4趟排序的结果）12 25 25 36 43 48 65 57 (第5趟排序的结果）12 25 25 36 43 48 65 57 (第6趟排序的结果）12 25 25 36 43 48 57 65 (第7趟排序的结果） 直接选择排序过程图示直接选择排序算法的C函数：void selectSort(RecType R) /*用直接选择排序对数组R中的记录进行排序*/RecType x; int i,j,k; for (i=1;iN;i+) /*共进行n-1趟排序*/ k=i; /*k保存当前排序码最小记录的下标，初值是i*/ for (j=i+

24、1;j=N;j+) if(Rj.keyRk.key) k=j;/*从当前的子区间里选择排序码最小的记录*/ if (k!=i)/*将排序码最小的记录放到子区间的第一个位置*/ x=Ri; Ri=Rk; Rk=x; 直接选择排序的性能分析时间效率：直接选择排序主要时间消耗在比较操作上，其平均时间复杂度为O(n2)。 空间效率：在整个算法中，只需要一个用于交换记录的辅助空间，所以直接选择排序的空间复杂度为O(1)。稳定性直接选择排序是不稳定的。742 堆排序一、堆的定义：设n个元素的序列为（K1，K2，Kn），当且仅当满足下述关系之一时，称之为堆。（1）KiK2i且 KiK2i+1，1i n/2（

25、2）KiK2i且 KiK2i+1，1i n/2 满足第（1）个条件的称作小根堆， 满足第（2）个条件的称作大根堆。例：（12，36，24，85，47，30，53，91），它满足堆定义的第一个条件，因此是小根堆。 （91，47，85，24，36，53，30，16），它满足堆定义的第二个条件，因此是大根堆。 二、堆与二叉树 如果把存储堆的一维数组看作是完全二叉树的顺序存储结构，就可以把堆转换为完全二叉树来表示 。12362485473053919147852436533012三、堆排序的基本思想：利用大（或小）根堆的性质不断地选择排序码最大（或小）的记录来实现排序的，利用大根堆来实现升序排列。 （

26、1）首先将R1Rn这n个记录按排序码建成大根堆。 （2）然后R1与Rn交换位置，即把排序码最大的记录放到待排序区间的最后；接着，再把R1Rn-1中的n-1个记录建成大根堆，仍然将堆顶R1与Rn-1交换位置。如此反复n-1次，每次选一个排序码最大的记录与本次排序区间的最后一个记录交换位置，最终得到一个有序序列。堆排序需解决两个问题：（1） 如何将n个待排序记录按排序码建成堆？（2） 交换堆顶记录后，对剩余的n-1个记录重新建堆的过程和前面的建堆过程是否相同？（a） 初始大根堆 （b） 91与12对换之后 （c） 12与85对换之后 （d） 12与53对换之后 交换堆顶元素之后 调整堆的过程图示举

27、例：对 (49，38，65，97，76，13，27，49) 堆排序。（a） 8个结点的初始状态（b）筛选97之后的状态（c）筛选65之后的状态（d）筛选38之后的状态（e）筛选49之后的状态 建堆过程图示“筛选法” 算法的C函数如下：void heapSift(RecType R,int i, int n) /*Ri为根结点，调整RiRn为大根堆*/ RecType rc; int j; rc=Ri; j=2*i; while(j=n) /*沿排序码较大的孩子结点向下筛选*/ if(jn & Rj.keyRj.key) break； Ri=Rj; /*记录移动到Ri */ i=j; j=j*2

28、; /*调整进入下一层 */ Ri=rc; /*找到了根结点最后应插入的位置 */ 堆排序算法heapSort()的C函数：void heapSort(RecType R,int n) /*对n个记录进行堆排序*/ int i; RecType x; for(i=n/2;i=1;i-) /*将RiRn建成堆 */ heapSift(R，i，n)； for(i=n;i1;i-)/*进行n-1趟排序*/ x=Ri; /*堆顶与最后一个记录交换位置 */ Ri=R1; R1=x; heapSift(R，1，i-1);/*将R1Ri-1重新调整为堆*/ 堆排序的性能分析如下：时间效率：堆排序的时间主要

29、消耗在筛选算法中，一共调用了n/2+n-1（约3n/2）次的筛选算法，在每次筛选算法中，排序码之间的比较次数都不会超过完全二叉树的高度，即log2n +1，所以整个堆排序过程的最坏时间复杂度为O(nlog2n)，也是其平均时间复杂度。空间效率：在整个堆排序过程中，需要1个与记录大小相同的辅助空间用于交换记录，故其空间复杂度为O(1)。堆排序是一种不稳定的排序方法。75 归并排序归并排序（Merge Sort）是利用“归并”技术实现的排序方法。所谓归并就是将两个或多个有序表合并成一个有序表的过程。如果是将两个有序表合并成一个有序表称为二路归并；同理，将三个有序表合并成一个有序表称为三路归并，以此

30、类推可以有n路归并等。本节主要讲二路归并技术实现的归并排序。二路归并方法：设数组R由两个有序子表RuRv和Rv+1Rt组成（uv,v+1t），将这两个有序子表合并之后存于数组A中，得到一个新的有序表AuAt。设i=u，j=v+1，k=u，即i，j，k分别指向三个有序表的起始下标，归并过程为：比较Ri.key和Rj.key的大小，如果Ri.keyRj.key，则将第一个有序子表的记录Ri复制到Ak中，并令i和k分别加1，指向下一个位置，否则将第二个有序子表的记录Rj复制到Ak中，并令j和k分别加1，如此循环下去，直到其中一个有序子表已到表尾，然后将另一个有序子表中剩余的记录复制到数组AkAt中，

31、至此二路归并结束。二路归并排序：首先把存储在数组R中的每个记录看成是长度为1的有序表，则n个记录构成n个有序表，接下来依次进行二路归并，归并成n/2个长度为2的有序表，当n是奇数时，还会剩余一个长度为1的有序表，通常把这个过程称为一趟归并排序。每完成一趟归并排序，都会使有序表的长度变为上一趟的2倍，但最后一个有序表的长度有可能小一些。举例：(45,53,18,36,73,45,93,15,30,48) 45 53 18 36 73 45 93 15 30 48 (初始状态）45 53 18 36 45 73 15 93 30 48 (1趟归并)18 36 45 53 15 45 73 93 3

32、0 48 (2趟归并)15 18 36 45 45 53 73 93 30 48 (3趟归并)15 18 30 36 45 45 48 53 73 93 (4趟归并) 归并排序过程图示一趟归并排序算法需要多次调用二路归并。设数组R中每个有序表的长度为len，（最后一个表长度可能小于len）,对其进行一趟归并排序，结果存于数组A中。实际处理过程中，可能有以下三种情况：（1）数组R中有偶数个长度都是len的有序表的，这时只要连续调用二路归并merge(R，A，p，p+len-1，p+len*2-1），即可完成一趟归并，这里p为有序表的起始下标；（2）数组R中前面有偶数个长度为len的有序表，两两合

33、并完成以后，还剩余两个不等长的有序表,则对最后两个不等长的有序表还要调用一次二路归并merge(R，A，p，p+len-1，n)，即可完成一趟归并；（3）数组R中前面所有长度为len的有序表两两合并以后，只剩一个有序表，把它直接复制到数组A中即可。二路归并算法的C函数描述如下：void merge(RecType R , RecType A, int u, int v, int t) /*将两个有序表RuRv和Rv+1Rt归并到有序表AuAt */int i,j,k; for(i=u, j=v+1, k=u；i=v&j=t；k+) if (Ri.key=Rj.key) Ak=Ri； i+； e

34、lse Ak=Rj；j+； while (i=v)/*处理第一个有序表中剩余的记录*/ Ak=Ri； i+; k+； while (j=t) /*处理第二个有序表中剩余的记录*/ Ak=Rj； j+; k+； 一趟归并排序算法的C函数：void mergePass(RecType R ，RecType A，int n，int len) /* 把数组R中每一个长度为len的有序子表归并到数组A中*/int p,i; for(p=1;p+2*len-1=n;p=p+2*len) /*归并长度为len等长有序表*/ merge(R，A，p，p+len-1，p+len*2-1); if (p+len-

35、1n) /*归并剩余的两个不等长的有序表*/ merge(R，A，p，p+len-1，n); else for(i=p;i=n;i+) /*把剩余的一个有序表复制到数组A中*/ Ai=Ri; 归并排序的过程就是反复地调用一趟归并排序算法，其算法的C函数如下：void mergeSort(RecType R ，int n) /*对数组R进行归并排序*/RecType AN+1； /*A是辅助数组*/ int len,i; len=1; while(lenn) mergePass(R,A,n,len); len=2*len; mergePass(A,R,n,len); len=2*len; 分析归

36、并排序的性能：时间效率：归并排序的时间复杂度应为每一趟归并排序的时间复杂度和归并趟数的乘积。对n个记录进行归并排序，归并趟数约为log2n。归并排序的时间效率主要取决于记录的移动次数。而一趟归并排序中记录的移动次数等于记录个数n，故归并排序的平均时间复杂度为O(nlog2n)。空间效率：归并排序需要一个与表等长的辅助数组空间，所以空间复杂度为O（n）。归并排序是稳定的。*76 基数排序 基数排序（Radix Sort）是与前面各类排序方法完全不同的一种排序方法，它是基于排序码的结构分解，然后通过“分配”和“收集”方法实现的排序。举例：52张扑克牌上有花色和面值（点数）。扑克牌的顺序是：A2JQKA2KA2KA2K。对扑克牌进行排序可以采用下面两种方法：方法1：首先按花色分成4堆，每一堆都具有相同花色，然后分别在每一堆内按面值从小到大排序，最后