哈工大数据结构课件第6章内部排序方法

第6章内部排序数据结构与算法数据结构与算法数据结构与算法数据结构与算法DataStructruesandAlgorithmsg•张岩张岩•海量数据计算研究中心哈工大计算机科学与技术学院张岩Slide6-12013/12/92013/12/92013/12/9•哈工大计算机科学与技术学院第第66章章内部排序内部排序第第66章章内部排序内部排序2013/12/9Slide6-2第6章内部排序学习目标学习目标掌握排序的基本概念和常用术语熟练掌握插入排序、希尔排序；气泡排序、快速排序；选择排序、堆排序；归并排序；基数排序的基本思想、算法原理排序过程和算法实现、排序过程和算法实现。掌握各种排序算法的性能及其分析方法，以及各种排序方法的比较和选择等的比较和选择等。哈工大计算机科学与技术学院张岩Slide6-32013/12/9第6章内部排序本章主要内容本章主要内容本章主要内容本章主要内容6.1基本概念6.2气泡排序6.3快速排序6.4直接选择排序65堆排序6.5堆排序6.6（直接）插入排序67希尔排序6.7希尔排序6.8（二路）归并排序6.9基数排序本章小结哈工大计算机科学与技术学院张岩Slide6-42013/12/9第6章内部排序6161基本概念基本概念6.16.1基本概念基本概念排序（sorting）也称分类：假设给定一组n个记录序列{r1,r2,……,rn}，其相应的关键字序列为{k1,k2,……,kn}。排序是将这些记录排列成顺序为{rrr}的一个序列，使得相应的关键字的序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键字的值满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。排序的目的：方便查询和处理。排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同关键字值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，且在之前，而在排序后的序变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。哈工大计算机科学与技术学院张岩Slide6-52013/12/9称为不稳定的。第6章内部排序6161基本概念（基本概念（contcont））6.16.1基本概念（基本概念（cont.cont.））排序分类：按照排序时排序对象存放的设备，分为，内部排序:排序过程中数据对象全部在内存中的排序。外部排序:排序过程数据对象并非完全在内存中的排序按照排序是的基本操作是否基于关键字的比较？分为,按照排序是的基本操作是否基于关键字的较分为,基于比较：基本操作——关键字的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。2交换排序（气泡、快速排序）；选择排序（直接选择、堆排序）；插入排序（直接插入、折半插入、希尔排序）归并排序（二路归并排序）排序）、归并排序（二路归并排序）。不基于比较：根据根据组成关键字的的分量及其分布特征如基数排序哈工大计算机科学与技术学院张岩Slide6-62013/12/9特征，如基数排序。第6章内部排序6161基本概念（基本概念（contcont））6.16.1基本概念（基本概念（cont.cont.））排序算法的性能：基本操作。内排序在排序过程中的基本操作：比较：关键码之间的比较；比较：关键码之间的比较；移动：记录从一个位置移动到另一个位置。辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外执行算法所需要放待排序记录占用的存储空间之外，执行算法所需要的其他额外存储空间。算法本身的复杂度算法本身的复杂度。哈工大计算机科学与技术学院张岩Slide6-72013/12/9第6章内部排序6161基本概念（基本概念（contcont））6.16.1基本概念（基本概念（cont.cont.））排序算法及其存储结构：从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。我们假定采用顺序存储结构：structrecords{keytypekey;fieldsother;fieldsother;}；tdfdLIST[i]typedefrecordsLIST[maxsize];Sort（intn,LIST&A）:对n个记录的数组按照关键字不减的顺序进行排序哈工大计算机科学与技术学院张岩Slide6-82013/12/9减的顺序进行排序。第6章内部排序6262气泡排序气泡排序6.26.2气泡排序气泡排序算法的基本思想：将待排序的记录看作是竖着排列的“气泡”，关键字较小的记录比较轻，从而要往上浮。对这个“气泡”序列进行n-1遍（趟）处理。所谓一遍（趟）处理，就是自底向上检查一遍这个序列，并注意两个相比较的关键字的顺序是否正确。如果发现顺序不对，即“轻”的记录在下面，就交换它们的位置。显然，处理1遍之后，“最轻”的记录就浮到了最高位置；处理2遍之后，“次轻”的记录就浮到了次高位置。在作第二遍处理时由于最高位置上的记录已是“最轻”作第二遍处理时，由于最高位置上的记录已是“最轻”的，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的记录的关键字，因为经过前面i-1遍的处理哈工大计算机科学与技术学院张岩Slide6-92013/12/9高位置以上的记录的关键字，因为经过前面i1遍的处理，它们已正确地排好序。第6章内部排序6262气泡排序（气泡排序（contcont））6.26.2气泡排序（气泡排序（cont.cont.））算法的实现：voidBubbleSort(intn,LIST&A){for(inti=1;i=n-1;i++)for(intj=n;j=i+1;j--)if(A[j].keyA[j-1])if(A[j].keyA[j1])swap(A[j],A[j-1])}}voidswap(records&x,records&y){recordsw;w=x;x=y;y=w;哈工大计算机科学与技术学院张岩Slide6-102013/12/9}第6章内部排序6262气泡排序（气泡排序（contcont））6.26.2气泡排序（气泡排序（cont.cont.））算法（时间）性能分析：最好情况（正序）:比较次数：n-1移动次数：0时间复杂度：O(n)；时间复杂度：O(n)；最坏情况（反序）：比较次数)1(nn(i)n-1比较次数：2)1(1nn(n-i)i)1(n3nn-1移动次数：时间复杂度：O(n2)；2)1(1n3n3(n-i)i空间复杂度O(1)哈工大计算机科学与技术学院张岩Slide6-112013/12/9平均情况：时间复杂度为O(n2)。空间复杂度：O(1)。第6章内部排序6363快速排序快速排序6.36.3快速排序快速排序快速算法是对气泡排序的改进，改进的着眼点：在气泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较次数和移动次数较多。比较次数和移动次数较多。减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离•增大记录的比较和移动距离较大记录从前面直接移动到后面较小记录从后面直接移动到前面哈工大计算机科学与技术学院张岩Slide6-122013/12/9较小记录从后面直接移动到前面第6章内部排序6363快速排序（快速排序（contcont））6.36.3快速排序（快速排序（cont.cont.））算法的基本思想：是CRAH1962年提出的种划分交换排序采用的是C.R.A.Hoare1962年提出的一种划分交换排序。采用的是分治策略(一般与递归技术结合使用)，以减少排序过程之中的比较次数。中的比较次数。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。分治法的基本思想分解(划分):将原问题分解为若干个与原问题相似的子问题；求解:递归地求解子问题。若子问题的规模足够小，则直接求解;哈工大计算机科学与技术学院张岩Slide6-132013/12/9求解递归地求解子问题。若子问题的规模足够小，则直接求解;组合:将每个子问题的解组合成原问题的解。第6章内部排序6363快速排序（快速排序（contcont））6.36.3快速排序（快速排序（cont.cont.））算法的实现步骤：设被排序的无序区为设被排序的无序区为A[i],……,A[j]1.基准元素选取：选择其中的一个记录的关键字v作为基准元素控制关键字怎么选择元素(控制关键字);(怎么选择？)2.划分：通过基准元素v把无序区A[i],……,A[j]划分成左、右两部分使得左边的各记录的关键字都小于右边的右两部分，使得左边的各记录的关键字都小于v；右边的各记录的关键字都大于等于v；(如何划分？)递归求解重复分别对左边和右边部分递归地进3.递归求解：重复(1)~(2)，分别对左边和右边部分递归地进行快速排序；组合左右两部分均有序整个序列有序4.组合：左、右两部分均有序，整个序列有序。3562951413哈工大计算机科学与技术学院张岩Slide6-142013/12/93562951413第6章内部排序6363快速排序（快速排序（contcont））6.36.3快速排序（快速排序（cont.cont.））基准元素的选取：基准元素的选取是任意的，但不同的选取方法对算法性能3562951413基准元素的选取是任意的，但不同的选取方法对算法性能影响很大；一般原则：是每次都能将表划分为规模相等的两部分（最一般原则：是每次都能将表划分为规模相等的两部分（最佳情况）。此时，划分次数为log2n，全部比较次数nlog2n，交换次数(n/6)log2n。，交换次数(n/6)log2n。设FindPivot(i,j)是求A[i].key,…,A[j].key的基准元素v=A[k]，返回其下标k。vA[k]，返回其下标k。v=(A[i].key，A[(i+j)/2].key,A[j].key的中值)从A[i]k到A[j]k最先找到的两个不同关键字中v=从A[i].key到A[j].key最先找到的两个不同关键字中的最大者。（若A[i].key,…A[j].key之中至少有两个关键字不相同）优点：若无两个关键字不同，则A[i]到哈工大计算机科学与技术学院张岩Slide6-152013/12/9键字不相同）优点：若无两个关键字不同，则A[i]到A[j]已有序，排序结束。第6章内部排序6363快速排序（快速排序（contcont））6.36.3快速排序（快速排序（cont.cont.））intFindPivot(inti,intj)/*设A是外部数组*//*若A[i]A[j]的关键字全部相同，则返回0；/*若A[i],…A[j]的关键字全部相同，则返回0；否则，左边两个不同关键字中的较大者的下标。*/{ktfitkA[i]k/*第1个关键字的值A[i]k*/{keytypefirstkey=A[i].key;/*第1个关键字的值A[i].key*/intk;/*从左到右查找不同的关键字*/for(k=i+1;k=j;k++)/*扫描不同的关键字*/if(A[k].keyfirstkey)/*选择较大的关键字*/returnk;elseif(A[k].keyfirstkey)returni;return0;哈工大计算机科学与技术学院张岩Slide6-162013/12/9;}3562951413第6章内部排序6363快速排序（快速排序（contcont））6.36.3快速排序（快速排序（cont.cont.））无序区划分（分割）：设被排序的无序区为A[i]A[j]设被排序的无序区为A[i],……,A[j](1)扫描:3562951413令游标l从左端(初始时l