《c++程序中各种排序实现详解》由会员分享,可在线阅读,更多相关《c++程序中各种排序实现详解(37页珍藏版)》请在金锄头文库上搜索。
1、1Agendav名次排序v选择排序v冒泡排序v插入排序v基数排序v堆排序v归并排序v快速排序21、名次排序元素在队列中的名次(rank)可定义为队列中所有 比它小的元素数目加上在它左边出现的与它相同 的元素数目。例如,给定一个数组a=4, 3, 9, 3, 7作为队 列,则各元素的名次为r=2,0,4,1,3。31、名次排序template void Rank(T a, int n, int r) /计算a 0:n-1中n个元素的排名for (int i = 0; i void Rearrange (T * /在u中移动到正确的位置for ( int i = 0; i int Max(T a,
2、 int n)/ 寻找a 0 : n-1中的最大元素int pos = 0;for (int i = 1; i void SelectionSort (T a, int n) /对数组a 0:n-1中的n个元素进行排序for ( int size = n; size 1; size- -) int j= Max(a, size); /size-1次比较Swap( aj,asize-1 ) ; /移动3次9按照元素的比较次数来估算函数的时间复杂性 。每次调用Max(a,size)需要执行size-1次比较, 所以总的比较次数为:1+2+3+n-1= (n-1)n/2。移动次数为:3(n-1)2、
3、选择排序10上述程序中选择排序函数的一个缺点是:即使 元素已经按序排列,程序仍然继续运行。为了终止不必要的循环,在查找最大元素期间 ,可以顺便检查数组是否已按序排列。2、选择排序11template void SelectionSort(T a, int n) / 及时终止的选择排序 bool sorted = false; for(int size = n; !sorted size-) int pos = 0; sorted = true; / 找最大元素 for (int i = 1; i void Bubble (T a, int n) /把数组a0:n-1中最大的元素通过冒泡移到右边
4、for ( int i = 0; i ai+1) Swap(ai,ai+1);153、冒泡排序template void BubbleSort (T a, int n)/对数组a0:n-1中的n个元素进行冒泡排序for ( int i = n; i1; i- -)Bubble(a,i) ;163、冒泡排序如果在一次冒泡过程中没有发生元素互换,则说明数组已经按序排列,没有必要再继续进行冒泡过程。173、冒泡排序templatebool Bubble(T a, int n) /把a0:n-1 中最大元素冒泡至右端bool swapped = false; / 尚未发生交换for (int i =
5、0; i ai+1) Swap(ai, ai+1);swapped = true; / 发生了交换return swapped;183、冒泡排序templatevoid BubbleSort(T a, int n)/ 及时终止的冒泡排序for(int i = n;i1 i- -) ;最坏情况下比较次数,移动次数 ? 最好情况下比较次数,移动次数 ?193、冒泡排序v最好情况:数组a最初已经有序。 v最坏情况:数组a倒序。最好 最坏 v比较 n-1 n(n-1)/2 v移动 0 3*n(n-1)/2204、插入排序v算法设计: 5, 2, 4, 10, 7 5, 2, 5, 2, 4, 5, 2
6、, 4, 5, 10, 2, 4, 5, 7, 10214、插入排序v思想:因为只有一个元素的数组是一个有序数组 ,所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数组中 ,可以得到一个大小为2的有序数组。插入第三 个元素可以得到一个大小为3的有序数组。v按照这种方法继续进行下去,最终将得到一个大 小为n的有序数组。224、插入排序templatevoid InsertionSort(T a, int n)for (int i=1; i = 0 Node x; Chain *bin; bin=new Chainrange+1; /分配到每个箱子中 for(inti=
7、1;i=0;j-) while(!binj.IsEmpty() binj.Delete(1,x); X.Insert(0,x); deletebin; 275、基数排序v在两个for循环中执行的每一次插入和删除操作 所需要的时间均为(1)v因此第一个for循环的的复杂性为(n),其中n为输入链表的长度v第二个for循环的复杂性为(n+range)v因此函数BinSort总的复杂性为(n+range)(如 果成功的话)。285、基数排序v假定对范围在0999之间的10个整数进行排序。v如果使用range=1000来调用BinSort,那么箱子的初始化将需要1000个执行步,节点分配需要10个执行
8、步,从箱子中收集节点需要1000个执 行步,总的执行步数为2010。295、基数排序v不直接对这些数进行排序,而是采用一些基数r来 分解这些数。v在基数排序(radix sort)中,把数按照某种基 数分解为数字,然后对数字进行排序。v基数r=箱子个数305、基数排序315、基数排序v对于一般的基数r,相应的分解式为:x%r;(x%r2)/r;(x%r3)/r2;.v当使用基数r=n对n个介于0nc-1范围内的整数进行 分解时,每个数将可以分解出c个数字。v因此,可以采用c次箱子排序,每次排序时取 range=n。整个排序所需要的时间为(cn)= (n) (因为c是一个常量)。326、堆排序先
9、将要排序的n 个元素初始化为一个最大堆 ,然后每次从堆中提取(即删除)元素。各元素将按递减次序排列。初始化所需要的时间为(n),每次删除所需 要的时间为O(logn) ,因此总时间为 O(nlogn) 。336、堆排序template void HeapSort(T a, int n) / 利用堆排序算法对a1:n 进行排序 / 创建一个最大堆 MaxHeap H(1); H.Initialize(a,n,n) ;/ 从最大堆中逐个抽取元素 T x; for (int i = n-1; i = 1; i-) H.DeleteMax(x) ; ai+1 = x; / 在堆的析构函数中保存数组a H.Deactivate(x) ; 346、堆排序堆排序的初始化策略:从第一个具有孩子的节点开始,这个元素在数组中的位置为i=n/2,如果以这个元素为根的子 树已是最大堆,则此时不需调整,否则必须调整 子树使之成为堆。随后,继续检查以i-1,i-2等节点为根的子树, 直到检查到整个二叉树的根节点(其位置为1) 。356、堆排序6、堆排序376、堆排序11,20,15,7,2,9,28,32,1,18最大堆?最小堆?