大学《数据结构》第七章：排序-第三节-交换排序

第三节交换排序当前讲授交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。一、冒泡排序1、排序思想通过相邻元素之间的比较和交换，使关键字较小的元素逐渐从底部移向顶部，关键字较大的元素逐渐下移(后移)，小的上浮，大的下沉，所以冒泡排序又被称为"起泡"排序。第一趟扫描：依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。然后再对R[n]～R[2]的记录进行第二趟排序，使次小关键字的元素被上浮到R[2]中，重复进行，n-l趟后，整个冒泡排序结束。2、实例分析【例】有8个记录的关键字序列为(36，28，45，13，67，36，18，56)，如下图所示为该序列起泡排序的全过程.3、算法描述voidBubbleSort(SeqListR，intn){//采用自底向上扫描数组R[1．．n]做冒泡排序inti，j，flag；for(i=1；i<n；i++)//最多做n-1趟排序{flag=0；//flag表示每一趟是否有交换，先置0for(j=n；j>=i+1；j--)//进行第i趟排序if(R[j].key<R[j-1].key){R[0]=R[j-1]；//R[0]作为交换时的暂存单元R[j-1]=R[j]；R[j]=R[0]；//相邻两个元素完成交换flag=1；//有交换，flag置1}if(flag==0)return；}}4、算法分析（1）算法的最好时间复杂度若待排序记录为有序(最好情况)，则一趟扫描完成，关键比较次数为n-1次且没有移动，比较的时间复杂度为O(n)。（2）算法的最坏时间复杂度若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。总的比较次数为：（n-1）+（n-2）+…+1=n(n-1)/2；总的移动次数为3n(n-1)/2。在平均情况下，比较和移动记录的总次数大约为最坏情况下的一半，所以，冒泡排序算法的时间复杂度为O(n2)。（3）算法的空间复杂度冒泡排序的空间复杂度为O(1)，是就地排序（4）算法稳定性冒泡排序是稳定的。【例】设计一个修改冒泡排序算法以实现双向冒泡排序的算法。【2009年1月考算法填空】双向冒泡排序则是交替改变扫描方向，即一趟从下向上通过两个相邻关键字的比较，将关键字最小的记录换至最上面位置，再一趟则是从第二个记录开始向下通过两个相邻记录关键字的比较，将关键字最大的记录换至最下面的位置；然后再从倒数第二个记录开始向上两两比较至顺数第二个记录，将其中关键字较小的记录换至第二个记录位置，再从第三个记录向下至倒数第二个记录两两比较，将其中较大关键字的记录换至倒数第二个位置，依此类推，直到全部有序为止。【算法描述】voidDbubbleSort(SeqListR，intn){//自底向上、自顶向下交替进行双向扫描冒泡排序inti=l，j；RecTypet；//t作为排序交换记录的中间变量intNoSwap；//表示一趟扫描是否有交换，为假无交换NoSwap=1；//首先假设有交换，表无序while(NoSwap)//当有交换时做循环{NoSwap=0；//置成无交换for(j=n-i+1；j>=i+l；j--)//自底向上扫描if(R[j].key<R[j-1].key)//若反序(后面的小于前一个)，即交换{t=R[j]；R[j]=R[j-1]；R[j-1]=t；NoSwap=1；//说明有交换｝for(j=i+1；j<=n-i；j++)//自顶向下扫描if(R[j].key>R[j+1].key)//若反序(前面的大于后一个)，即交换{t=R[j]；R(j]=R[j+1]；R[j+1]=t；NoSwap=1；//说明有交换｝i=i+1；｝}二、快速排序1、排序思想快速排序的基本思想是：首先在当前无序区R[low…high]中任取一个记录作为排序比较的基准(不妨设为x)，用此基准将当前无序区划分为两个较小的无序区R[low…i-1]和R[i+1…high]，并使左边的无序区中所有记录的关键字均小于等于基准的关键字，右边的无序区中所有记录的关键字均大于等于基准的关键字，而基准记录x则位于最终排序的位置i上，这个过程称为一趟快速排序(或一次划分)。当R[low…i-1]和R[i+1…high]均非空时，分别对它们进行上述划分，直到所有的无序区中的记录均已排好序为止。一趟快速排序的具体操作是：设两个指针i和j，它们的初值分别为low和high，基准记录x=R[i]，首先从j所指位置起向前搜索找到第一个关键字小于基准x.key的记录存入当前i所指向的位置上，i自增l，然后再从i所指位置起向后搜索，找到第一个关键字大于x.key的记录存入当前j所指向的位置上，j自减1；重复这两步，直至i等于j为止。2、实例分析依次可得各趟排序结果如下：3、算法描述intPartition(SeqListR，inti，intj){//对R[i]…R[j]区间内的记录进行一次划分排序RecTypex=R[i]；//用区间的第一个记录为基准while(i<j){while(i<j&&R[j].key>=x.key)j--；//从j所指位置起向前(左)搜索if(i<j){R[i]=R[j]；i++；//后面大的数往前移动}while(i<j&&R[i].key<=x.key)i++；//从i所指位置起向后(右)搜索if(i<j){R[j]=R[i]；j--；//前面小的数往前移动｝｝R[i]=x；//基准记录x位于最终排序的位置i上returni；｝voidQuickSort(SeqListR，intlow，inthigh)｛//对顺序表R中的子区间进行快速排序intp；if(low<high)//长度大于1{p=Partition(R，low，high)；//做一次划分排序QuickSort(R，low，p-1)；//对左区间递归排序QuickSort(R，p+l，high)；//对右区间递归排序｝｝4、算法分析（1）算法时间复杂度快速排