C程序设计排序

会计学1C程序设计排序概述什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的元素序列调整为“有序”的元素序列。排序的分类待排序元素关键字个数单关键字排序多关键字排序待排序元素的存储介质内部排序：排序过程不需要访问外存便能完成外部排序：排序过程需要访问外存才能完成第1页/共92页概述内部排序的类别插入类：直接插入排序、折半排序、2-路插入排序、

希尔排序分划类：冒泡排序、快速排序选择类：简单选择排序、堆排序归并类：2-路归并排序其他方法：基数排序第2页/共92页概述排序的两个基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定性待排序列{a1,a2,…,an}，其相应的关键字序列{k1,k2,…,kn}，假设ki=kj

(

1≤i,j≤n且i≠j)，且在排序前的序列中ai领先于aj。

若在排序后的序列中ai仍领先于aj，则称所用的排序方法是稳定的，反之，则称其是不稳定的。第3页/共92页7.1插入类排序插入类排序将待排序元素逐个插入到已排好序的有序表中，从而得到一个新的有序表。应用插入类排序思想的算法直接插入排序折半插入排序2-路插入排序希尔排序第4页/共92页7.1.1直接插入排序排序过程整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序第i趟直接插入排序的基本思想有序序列A[0..i-1]R[i]无序序列A[i..n-1]有序序列A[0..i]无序序列A[i+1..n-1]第5页/共92页直接插入排序例第6页/共92页7.1.1直接插入排序直接插入排序算法//直接插入排序,数组data用于存放待排序元素，n为待排序元素个数template<classElemType>voidInsertSort(ElemTypedata[],intn){ElemTypetmp;inti,j;for(i=1;i<n;i++){if(data[i]>data[i-1])continue;tmp=data[i]; //保存待插入的元素data[i]=data[i-1];for(j=i-1;j>0&&data[j-1]>tmp;j--)data[j]=data[j-1]; //元素后移data[j]=tmp; //插入到正确位置}}第7页/共92页7.1.1直接插入排序算法评价时间复杂度正序元素移动次数：0元素比较次数：n-1逆序元素移动次数：元素比较次数：平均情况O(n2)第8页/共92页7.1.2折半插入排序因为A[0..i-1]是一个按关键字有序的有序序列，则可以利用“折半查找”实现“在A[0..i-1]中查找A[i]的插入位置”，如此实现的插入排序为折半插入排序。减少元素关键字间的比较次数，但元素移动次数不变第9页/共92页折半插入排序例第10页/共92页折半插入排序算法7.1.2折半插入排序template<classElemType>voidBInsertSort(ElemTypedata[],intn){ElemTypetmp;inti,j,mid,low,high;for(i=1;i<n;i++){tmp=data[i],low=0,high=i-1;

while(low<=high){ //在data[low..high]中查找插入的位置mid=(low+high)/2; //折半if(tmp<data[mid])high=--mid; //插入点在低半区elselow=++mid; //插入点在高半区}for(j=i-1;j>=low;j--)data[j+1]=data[j]; //元素后移

data[low]=tmp; //插入到正确位置}}第11页/共92页7.1.32-路插入排序将插入区域分成大致等长的两段，选择性地插人到其中一段排序过程设置一个和原数组data同类型，同规模的是数组d，并将其视为循环数组（即位置n-1和0逻辑上相邻）d[0]=data[0]，将d[0]看作为排好序中处于中间位置的元素，从第二个元素data[1]开始做以下操作如果data[i]>d[0]，将data[i]插入d[0]之后的有序序列，并保持插入后有序；反之，将其插入d[0]之前的有序序列，并保持插入后有序

第12页/共92页2-路插入排序例第13页/共92页7.1.32-路插入排序算法评价减少约为n2/8的元素移动次数基准元素选取的好坏直接影响排序的效率第14页/共92页7.1.4希尔排序希尔排序又称缩小增量排序将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将n个记录分成d个子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]} {R[2]，R[2+d]，R[2+2d]，…，R[2+kd]} … {R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}

其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。第15页/共92页希尔排序例3428817922165524996446设增量d=516282479

22345581996446设增量d=31622245528346446997981设增量d=11622242834465564798199第16页/共92页7.1.4希尔排序希尔排序算法template<classElemType>voidShellSort(ElemTypedata[],intincrements[] ,intn,intincrementsLength){inti,j,k;ElemTypetmp;

for(k=0;k<incrementsLength;k++){ //进行以increments[k]为增量的排序for(i=increments[k];i<n;i++){tmp=data[i];for(j=i;j>=increments[k];j-=increments[k]){if(tmp>=data[j-increments[k]])break;data[j]=data[j-increments[k]];}data[j]=tmp;}}}第17页/共92页7.1.4希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的元素组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序第18页/共92页7.1.4希尔排序算法评价算法效率依赖于增量序列的选择时间复杂度在O(n3/2)到O(n7/6)之间增量序列的取法最后一个增量必须为1其他增量间保持“互质”第19页/共92页7.2分划类排序分划类排序通过一趟划分确定一个元素在序列中的位置，保证在它之前的一组元素不比它大，之后的不比它小，接着对两组元素继续分划，直至待排序列有序。应用插入类排序思想的算法冒泡排序快速排序第20页/共92页7.2.1冒泡排序排序过程将第一个和第二个元素的关键字进行比较，若为逆序，则将两元素互换；接着比较第二个和第三个元素的关键字，依次类推，直至最后两个元素的完成比较，这称为第一趟冒泡排序。第一趟排序分划出一组元素个数为n-1的待排序列和一个关键字最大的元素。第i趟对前n-i+1个的元素进行类似的排序操作，得到一组元素个数为n-i的待排序列和一个关键字次大的元素。这样不断分划直至一趟分划时无元素互换为止。第21页/共92页7.2.1冒泡排序假设在排序过程中，元素序列A[1..n]的状态为：无序序列A[1..n-i+1]有序序列A[n-i+2..n]n-i+1无序序列A[1..n-i]有序序列A[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上第i趟起泡排序第22页/共92页冒泡排序例第23页/共92页7.2.1冒泡排序冒泡排序算法template<classElemType>voidBubbleSort(ElemTypedata[],intn){intlastSwapIndex=n-1;//用于记录最后一次交换的元素下标inti,j;for(i=lastSwapIndex;i>0;i=lastSwapIndex){lastSwapIndex=0;for(j=0;j<i;j++)if(data[j]>data[j+1]){Swap(data[j],data[j+1]);lastSwapIndex=j;}}}第24页/共92页7.2.1冒泡排序算法评价最好情况（正序）移动次数：0比较次数：n-1最坏情况（逆序）移动次数：3n(n-1)/2比较次数：n(n-1)/2T(n)=O(n2)第25页/共92页7.2.2快速排序一趟快速排序选第一个待排序元素作为枢轴（或支点pivot），根据枢轴将待排序列划分为两个子列这两个子列必须满足以下条件：一个子列的元素关键字都不大于枢轴的关键字，另一个子列的元素关键字都不小于枢轴的关键字。第26页/共92页7.2.2快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的元素序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序第27页/共92页7.2.2快速排序排序过程对待排序列A进行快速排序的递归算法QuickSort(A)可以描述如下：如果A中元素的个数为0或1，则返回；否则，继续选取A中的一个元素p作为枢轴（pivot）将A中剩下的元素“划分”成两个不相交的集合：

QuickSort(A1),p,QuickSort(A2)第28页/共92页一趟快速排序例第29页/共92页7.2.2快速排序//对data[low...high]进行分划，确定枢轴的位置，并返回其所在位置//子序列中，在枢轴之前（后）的元素均不大（小）于它template<classElemType>intPartition(ElemTypedata[],intlow,inthigh){ElemTypepivot=data[low]; //用子序列的头元素作为枢轴

while(low<high){while(low<high&&data[high]>=pivot)high--;data[low]=data[high]; //比枢轴小的元素移到低端

while(low<high&&pivot>=data[low])low++;data[high]=data[low]; //比枢轴大的元素移到高端}data[low]=pivot; //确定枢轴的合适位置returnlow; //返回枢轴的位置}一趟快速排序算法第30页/共92页7.2.2快速排序快速排序算法//对data[begin...end]进行快速排序template<classElemType>voidQuickSort(ElemTypedata[],intbegin,intend){if(begin>=end) //data长度小于等于时返回return;intpivot=Partition(data,begin,end); //对data[begin...end]进行分划QuickSort(data,begin,pivot-1);//对低端子列进行递归排序QuickSort(data,pivot+1,end);//对高端子列进行递归排序}

//快速排序template<classElemType>voidQuickSort(ElemTypedata[],intn){if(n<2)return;QuickSort(data,0,n-1);}第31页/共92页7.2.2快速排序算法分析最好情况每次中间值作为枢轴T(n)=O(nlog2n)最坏情况每次总选最大或最小元素作为枢轴T(n)=O(n²)平均情况T(n)=O(nlogn)三数中值分割法第32页/共92页7.3选择类排序选择类排序逐趟扫描未排序的部分，从中选取一个元素移动到合适的位置。应用选择类排序思想的算法简单选择排序树形选择排序堆排序第33页/共92页7.3.1简单选择排序假设排序过程中，待排记录序列的状态为：有序序列A[1..i-1]无序序列A[i..n]第i趟简单选择排序从中选出关键字最小的元素有序序列A[1..i]无序序列A[i+1..n]第34页/共92页7.3.1简单选择排序排序过程第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第一个元素进行交换；第i趟，扫描待排序列中剩余n-i+1个元素，找出关键字最小的元素与序列中第i个位置上的元素交换重复上述操作,直到所有的元素都放到正确的位置上为止第35页/共92页简单选择排序例第36页/共92页简单选择排序算法7.3.1简单选择排序template<classElemType>voidSelectionSort(ElemTypedata[],intn){inti,j,min;for(i=0;i<n;i++){min=i;for(j=i+1;j<n;j++){ //选择data[i+1...n-1]中最小的元素if(data[j]<data[min])min=j;}Swap(data[i],data[min]); //将data[i]与第i小的元素交换}}第37页/共92页7.3.1简单选择排序算法分析最好情况比较次数：移动次数：0最坏情况比较次数：移动次数：3(n-1)T(n)=O(n²)第38页/共92页7.3.2树形选择排序简单选择排序中一趟排序中的比较操作可能在前一趟中已经做过，但前一趟中未保存这些比较结果，因此在后一趟的排序中又重复执行了这些操作。为了解决这个问题，树形选择排序应运而生。算法思想先将n个元素的关键字两两比较，然后将其中

个较小者两两比较，如此重复，不断的淘汰较大者，最终选出关键字最小的元素第39页/共92页树形选择排序例第40页/共92页7.3.3堆排序堆的定义：堆是满足下列性质的数列{a1,a2,…，an}：或(小顶堆)(大顶堆){12,36,27,65,40,34,98,81,73,55,49}小顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆第41页/共92页7.3.3堆排序若将该数列视作完全二叉树，则r2i

是ri

的左孩子；r2i+1

是ri的右孩子aia2i

a2i+1

1236276549817355403498不是堆14第42页/共92页7.3.3堆排序堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。建大顶堆{98,53,55,18,4,22,24}{24,53,55,18,4,22,98}交换98和24重新调整为大顶堆{55,53,24,18,4,22,98}{22,18,53,98,4,24,55}经过筛选第43页/共92页7.3.3堆排序排序过程将待排序列A[0…n-1]调整为大顶堆；将堆顶元素A[0]（即关键字最大的元素）与堆尾元素（即堆中最后一个元素）交换，从堆中除去堆尾元素(即关键字最大的元素)，同时调整堆中剩余元素，使它们恢复堆属性；反复进行步骤2，直至堆中元素个数为1。第44页/共92页7.3.3堆排序堆排序需解决的两个问题：如何将初始的待排序列调整为一个堆？因堆顶元素与堆尾元素交换后，新的堆顶元素可能破坏了堆属性，如何再调整成为堆？第二个问题解决方法输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中较大者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”第45页/共92页例堆排序调整例第46页/共92页堆排序调整例第47页/共92页7.3.3堆排序第一个问题解决方法从最后一个非叶子结点（即第

个元素）开始对所有非叶子结点调整操作第48页/共92页建堆例含7个元素的无序序列（22,18,53,98,4,24,55）2218552449822551853244982255985324418985522532441853第49页/共92页调整堆算法7.3.3堆排序//将data[i..n-1]中的元素调整为大顶堆template<classElemType>voidHeapAdjust(ElemTypedata[],inti,intn){ElemTypetmp;intchild;

for(tmp=data[i];LeftChild(i)<n;i=child){child=LeftChild(i);if(child!=n-1&&data[child+1]>data[child]) //取较大的孩子结点child++;if(tmp<data[child])data[i]=data[child];elsebreak;}data[i]=tmp;}第50页/共92页7.3.3堆排序堆排序算法//堆排序template<classElemType>voidHeapSort(ElemTypedata[],intn){inti;for(i=n/2;i>=0;i--) //建堆HeapAdjust(data,i,n);

//将堆的根结点与最后的一个叶结点交换,并进行调整for(i=n-1;i>0;i--){ Swap(data[0],data[i]);HeapAdjust(data,0,i);}}第51页/共92页7.3.3堆排序算法评价最好情况：O(n)最坏情况：O(nlogn)平均：O(nlogn)第52页/共92页7.4归并类排序归并将两个有序列合并成为一个新的有序列2-路归并排序将相邻的元素两两归并，得到

个长度为2或1的有序子序列，再将这些子序列两两归并，如此重复，直至得到一个长度为n的有序列为止第53页/共92页2-路归并排序例第54页/共92页“归并”算法//将数组data中，[lptr...rptr-1][rptr...rightEnd]两部分的元素进行合并//tmpArr为合并时的辅存空间template<classElemType>voidMerge(ElemTypedata[],ElemTypetmpArr[],intlptr ,intrptr,intrightEnd){intleftEnd=rptr-1;intptr,i;ptr=i=lptr;

while(lptr<=leftEnd&&rptr<=rightEnd)if(data[lptr]<=data[rptr])tmpArr[ptr++]=data[lptr++];elsetmpArr[ptr++]=data[rptr++];

while(lptr<=leftEnd)tmpArr[ptr++]=data[lptr++];while(rptr<=rightEnd)tmpArr[ptr++]=data[rptr++];

for(;i<=rightEnd;i++)data[i]=tmpArr[i];}第55页/共92页2-路归并排序算法template<classElemType>voidMPass(ElemTypedata[],ElemTypetmpArr[],intn,intmergeLength){inti=0;

while(i<=n-2*mergeLength){Merge(data,tmpArr,i,i+mergeLength,i+2*mergeLength-1);i=i+2*mergeLength;}if(i+mergeLength<n)Merge(data,tmpArr,i,i+mergeLength,n-1);}//2-路归并算法非递归实现template<classElemType>voidMergeSortNonRecursion(ElemTypedata[],intn){intmergeLength=1; //mergeLength记录每趟归并的步长ElemType*pArr=NULL;pArr=newElemType[n]; //pArr为合并时的辅存空间

while(mergeLength<n){MPass(data,pArr,n,mergeLength);mergeLength*=2;}delete[]pArr;}第56页/共92页7.4归并类排序算法评价T(n)=O(nlogn)缺点空间复杂度为O(n)算法中需要较多的拷贝工作第57页/共92页7.5基数排序无须比较关键字通过“分组”和“收集”两个过程来完成排序任务借助“多关键字排序”的思想第58页/共92页7.5.1多关键字的排序假设待排序列{a1,a2,…,an}中每个元素ai有d个关键字

，该序列对关键字

有序是指：

对序列中任意两个元素ai和aj(1≤i＜j≤n)都满足下列有序关系：

当两个元素的所有关键字都相等时，则必须保持其稳定性。其中

称为最主位关键字，

称为最次位关键字。第59页/共92页7.5.1多关键字的排序排序方法最高位优先法（MSD）先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值接着让每个子序列对次关键字k2排序，又分成若干更小的子序列依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法（LSD）从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列第60页/共92页7.5.1多关键字的排序MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序第61页/共92页7.5.2基数排序基数排序依次根据各关键字分量进行“分配”、“收集”完成排序在单关键字排序中，一个关键字可以看作由若干个关键字分量复合而成，如整数可视为若干数位的集合。第62页/共92页基数排序例第63页/共92页7.5.2基数排序用数组实现的基数排序算法voidRadixSort(intdata[],intn){constintradix=10;constintdigits=10;

inti,j,k,factor;

queue<int>queues[radix];

for(i=0,factor=1;i<digits;i++,factor*=radix){for(j=0;j<n;j++)queues[(data[j]/factor)%radix].push(data[j]);//分配for(k=j=0;j<radix;j++,k++)//收集while(!queues[j].empty()){data[k]=queues[j].front();queues[j].pop();}}}第64页/共92页7.5.2基数排序用数组实现基数排序的缺点虽然不需要进行“比较”操作，但仍需要大量的元素移动操作还需要额外的空间来存放10个队列链式基数排序用链表作存储结构的基数排序第65页/共92页7.5.2基数排序链式基数排设置10个队列，front[i]和rear[i]分别为第i个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变元素的指针值，将链表中的元素分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列第66页/共92页链式基数排序（第一趟）例第67页/共92页静态链表classSLList{structNode{intkey[DIGITS];intinfo;intnext;};friendostream&operator<<(ostream&os,SLList&s);public:SLList():data(NULL),length(0){};~SLList();voidArrange();//重排voidInit(intarr[],intn);voidRadixSort();//链式基数排序private:voidDistribute(int[],int[],int);//分配voidCollection(int[],int[],int);//收集Node*data;intlength;};第68页/共92页7.5.2基数排序voidSLList::Distribute(intfront[],intrear[],intdigit){inti,index;for(i=0;i<RADIX;i++)front[i]=0;

for(i=data[0].next;i>0;i=L.data[i].next){index=data[i].key/(int)pow(10.0,digit)-data[i].key/(int)pow(10.0,digit+1)*10;if(front[index]==0)front[index]=i;elsedata[rear[index]].next=i;

rear[index]=i;}}链式基数排序——“分配”算法第69页/共92页链式基数排序——“收集”算法7.5.2基数排序voidSLList::Collection(intfront[],intrear[],intdigit){inti,current;for(i=0;front[i]==0;i++); //找到第一个非空子表data[0].next=front[i]; //头结点指向第一个非空子表中第一个结点current=rear[i++];

for(;i<RADIX;i++){if(front[i]==0)continue;data[current].next=front[i]; //链接两个非空子表current=rear[i];}data[current].next=0;}第70页/共92页链式基数排序算法7.5.2基数排序//用SLList实现的基数排序voidSLList::RadixSort(){inti;intfront[RADIX],rear[RADIX];

//从最低位优先依次对各关键字进行分配收集for(i=0;i<DIGITS;i++){Distribute(front,rear,i);Collection(front,rear,i);}}第71页/共92页7.5.2基数排序重排链式基数排序产生的是一个有序循环链表，只能对它进行顺序访问，无法进行随机访问，因此有时需要对元素重新排列，将元素按照链表结点中next域的值调整位置使其顺序存储具体做法顺序扫描有序链表，将链表中第i个结点移动至静态链表中的第i个分量第72页/共92页重排例第73页/共92页重排算法7.5.2基数排序voidSLList::Arrange(){inti,tmp;intcurrent=data[0].next; //current存放第一个元素的当前位置

for(i=1;i<length;i++){while(current<i) //找到第i个元素，并用current存放其在静态 //链表中当前位置current=data[current].next;tmp=data[current].next;if(current!=i){Swap(data[current],data[i]);//第i个元素调整到位data[i].next=current;//指向被移走的元素}current=tmp;//为找第i+1个元素做准备}}第74页/共92页7.5.2基数排序算法分析空间复杂度O(r+n)时间复杂度 T(n)=O(d(n+r))

其中，n为待排序元素个数，d为元素的关键字分量数，r为基数第75页/共92页7.6内部排序的比较排序方法平均情况最好情况最坏情况基数排序O(d(n+r))O(d(n+r))O(d(n+r))2-路归并排序O(nlogn)O(nlogn)O(nlogn)堆排序O(nlogn)O(n)O(nlogn)快速排序O(nlogn)O(nlogn)O(n2)希尔排序O(n)直接插入排序O(n2)O(n)O(n2)简单选择排序O(n2)O(n2)O(n2)第76页/共92页7.6内部排序的比较从平均性能而言，快速排序最佳，但最坏情况下不如堆排序