C++程序中各种排序实现详解PPT

Agenda,名次排序选择排序冒泡排序插入排序基数排序堆排序归并排序快速排序,1、名次排序,元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。例如，给定一个数组a=4,3,9,3,7作为队列，则各元素的名次为r=2,0,4,1,3。,1、名次排序,templatevoidRank(Ta,intn,intr)/计算a0:n-1中n个元素的排名for(inti=0;in;i+)ri=0;/初始化/逐对比较所有的元素for(inti=1;in;i+)for(intj=0;ji;j+)if(aj=ai)ri+;elserj+;,1、名次排序,templatevoidRearrange(T*,根据a的元素之间所进行的比较操作来估算程序的时间复杂性。对于i的每个取值，执行比较的次数为i,所以总的比较次数为1+2+3+n-1=(n-1)n/2。移动操作次数为：n,1、名次排序,2、选择排序,思想：首先找出最大的元素，把它移动到an-1，然后在余下的n-1个元素中寻找最大的元素并把它移动到an-2，如此进行下去。,templateintMax(Ta,intn)/寻找a0:n-1中的最大元素intpos=0;for(inti=1;i1;i-)Bubble(a,i);,3、冒泡排序,如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒泡过程。,3、冒泡排序,templateboolBubble(Ta,intn)/把a0:n-1中最大元素冒泡至右端boolswapped=false;/尚未发生交换for(inti=0;iai+1)Swap(ai,ai+1);swapped=true;/发生了交换returnswapped;,3、冒泡排序,templatevoidBubbleSort(Ta,intn)/及时终止的冒泡排序for(inti=n;i1最坏情况下比较次数，移动次数?最好情况下比较次数，移动次数?,3、冒泡排序,最好情况：数组a最初已经有序。最坏情况：数组a倒序。最好最坏比较n-1n(n-1)/2移动03*n(n-1)/2,4、插入排序,算法设计：5,2,4,10,75,2,5,2,4,5,2,4,5,10,2,4,5,7,10,4、插入排序,思想：因为只有一个元素的数组是一个有序数组，所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数组中，可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。按照这种方法继续进行下去，最终将得到一个大小为n的有序数组。,4、插入排序,templatevoidInsertionSort(Ta,intn)for(inti=1;i=0,4、插入排序,最好情况：数组a最初已经有序。最坏情况：数组a倒序。最好最坏比较n-1n(n-1)/2移动n-1n-1+n(n-1)/2,5、基数排序,一种更快的排序方法为箱子排序（binsort）。在箱子排序过程中，节点首先被放入箱子之中，具有相同分数的节点都放在同一个箱子中，然后通过把箱子链接起来就可以创建一个有序的链表。,5、基数排序,5、基数排序,voidBinSort(Chain,5、基数排序,在两个for循环中执行的每一次插入和删除操作所需要的时间均为(1)因此第一个for循环的的复杂性为(n)，其中n为输入链表的长度第二个for循环的复杂性为(n+range)因此函数BinSort总的复杂性为(n+range)(如果成功的话)。,5、基数排序,假定对范围在0999之间的10个整数进行排序。如果使用range=1000来调用BinSort，那么箱子的初始化将需要1000个执行步，节点分配需要10个执行步，从箱子中收集节点需要1000个执行步，总的执行步数为2010。,5、基数排序,不直接对这些数进行排序，而是采用一些基数r来分解这些数。在基数排序（radixsort）中，把数按照某种基数分解为数字，然后对数字进行排序。基数r=箱子个数,5、基数排序,5、基数排序,对于一般的基数r，相应的分解式为：x%r;(x%r2)/r;(x%r3)/r2;.当使用基数r=n对n个介于0nc-1范围内的整数进行分解时，每个数将可以分解出c个数字。因此，可以采用c次箱子排序，每次排序时取range=n。整个排序所需要的时间为(cn)=(n)（因为c是一个常量）。,6、堆排序,先将要排序的n个元素初始化为一个最大堆，然后每次从堆中提取（即删除）元素。各元素将按递减次序排列。初始化所需要的时间为(n)，每次删除所需要的时间为O(logn)，因此总时间为O(nlogn)。,6、堆排序,templatevoidHeapSort(Ta,intn)/利用堆排序算法对a1:n进行排序/创建一个最大堆MaxHeapH(1);H.Initialize(a,n,n);/从最大堆中逐个抽取元素Tx;for(inti=n-1;i=1;i-)H.DeleteMax(x);ai+1=x;/在堆的析构函数中保存数组aH.Deactivate(x);,6、堆排序,堆排序的初始化策略：从第一个具有孩子的节点开始，这个元素在数组中的位置为i=n/2，如果以这个元素为根的子树已是最大堆，则此时不需