《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最大堆？最小堆？
