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

1、1Agendav名次排序v选择排序v冒泡排序v插入排序v基数排序v堆排序v归并排序v快速排序21 1、名次排序、名次排序元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。例如，给定一个数组a=4, 3, 9, 3, 7作为队列，则各元素的名次为r=2,0,4,1,3。31 1、名次排序、名次排序template void Rank(T a, int n, int r) /计算a 0:n-1中n个元素的排名for (int i = 0; i n; i+)ri = 0; /初始化/逐对比较所有的元素for (int i = 1; i n; i+)

2、for ( int j = 0; j i; j+)if (a j = ai) ri+;else rj+;41 1、名次排序、名次排序template void Rearrange (T * &a, int n, int r) /按序重排数组a中的元素，使用附加数组uT *u = new Tn+1;/在u中移动到正确的位置for ( int i = 0; i n; i+)uri = ai;delete a;a=u;5根据a的元素之间所进行的比较操作来估算程序的时间复杂性。对于i的每个取值，执行比较的次数为i,所以总的比较次数为1+2+3+ +n-1 = (n-1)n/2。移动操作次数为：

3、n1 1、名次排序、名次排序62 2、选择排序、选择排序v思想：首先找出最大的元素，把它移动到an-1，然后在余下的n-1个元素中寻找最大的元素并把它移动到an-2，如此进行下去。7templateint Max(T a, int n)/ 寻找a 0 : n-1中的最大元素int pos = 0;for (int i = 1; i n; i+)if (apos ai)pos = i;return pos;每次调用Max(a,size)需要执行size-1次比较。2 2、选择排序、选择排序82 2、选择排序、选择排序template void SelectionSort (T a, int n)

4、 /对数组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 2、选择排序、选择排序10上述程序中选择排序函数的一个缺点是：即使元素已经按序排列，程序仍然继续运行。为了终止不必要的循环，在查找最大元素期间，可以顺便检查数组是否已按序排列。2

5、 2、选择排序、选择排序11templatevoid SelectionSort(T a, int n)/ 及时终止的选择排序bool sorted = false;for(int size = n; !sorted & (size 1);size-) int pos = 0;sorted = true;/ 找最大元素for (int i = 1; i size; i+)if (apos = ai) pos = i;else sorted = false; / 未按序排列Swap(apos, asize - 1 ) ; 2 2、选择排序、选择排序12v最好情况：数组a有序。v最坏情况：

6、数组a最大元素在首位，其他元素已经有序。 最好 最坏比较 n-1 n(n-1)/2移动 3 3(n-1)2 2、选择排序、选择排序133 3、冒泡排序、冒泡排序采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素大于右边的元素，则交换这两个元素。在一次冒泡过程结束后，可以确信最大的元素肯定在最右边的位置上。例: 11，15 ,3 ,9，20，7 ,1 ，在第一次冒泡过程结束后，得到？143 3、冒泡排序、冒泡排序template void Bubble (T a, int n) /把数组a0:n-1中最大的元素通过冒泡移到右边for ( int i = 0

7、; i ai+1) Swap(ai,ai+1);153 3、冒泡排序、冒泡排序template void BubbleSort (T a, int n)/对数组a0:n-1中的n个元素进行冒泡排序for ( int i = n; i1; i- -)Bubble(a,i) ;163 3、冒泡排序、冒泡排序如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒泡过程。173 3、冒泡排序、冒泡排序templatebool Bubble(T a, int n) /把a0:n-1 中最大元素冒泡至右端bool swapped = false; / 尚未发生交换for (in

8、t i = 0; i ai+1) Swap(ai, ai+1);swapped = true; / 发生了交换return swapped;183 3、冒泡排序、冒泡排序templatevoid BubbleSort(T a, int n)/ 及时终止的冒泡排序for(int i = n;i1 & Bubble(a,i);i- -) ;最坏情况下比较次数，移动次数 ?最好情况下比较次数，移动次数 ?193 3、冒泡排序、冒泡排序v最好情况：数组a最初已经有序。v最坏情况：数组a倒序。最好 最坏v比较 n-1 n(n-1)/2v移动 0 3*n(n-1)/2204 4、插入排序、插入排序

9、v算法设计： 5, 2, 4, 10, 7 5, 2, 5, 2, 4, 5, 2, 4, 5, 10, 2, 4, 5, 7, 10214 4、插入排序、插入排序v思想：因为只有一个元素的数组是一个有序数组，所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数组中，可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。v按照这种方法继续进行下去，最终将得到一个大小为n的有序数组。224 4、插入排序、插入排序templatevoid InsertionSort(T a, int n)for (int i=1; i = 0 & taj;

10、 j-)aj+1=aj;aj+1=t; 234 4、插入排序、插入排序v最好情况：数组a最初已经有序。v最坏情况：数组a倒序。 最好 最坏v比较 n-1 n(n-1)/2v移动 n-1 n-1+n(n-1)/2245 5、基数排序、基数排序一种更快的排序方法为箱子排序（bin sort）。在箱子排序过程中，节点首先被放入箱子之中，具有相同分数的节点都放在同一个箱子中，然后通过把箱子链接起来就可以创建一个有序的链表。255 5、基数排序、基数排序265 5、基数排序、基数排序voidBinSort(Chain& X, int range)/按分数排序intlen=X.Length();

11、Node x; Chain *bin;bin=new Chainrange+1;/分配到每个箱子中for(inti=1;i=0;j-)while(!binj.IsEmpty()binj.Delete(1,x);X.Insert(0,x);deletebin;275 5、基数排序、基数排序v在两个for循环中执行的每一次插入和删除操作所需要的时间均为(1)v因此第一个for循环的的复杂性为(n)，其中n为输入链表的长度v第二个for循环的复杂性为(n+range)v因此函数BinSort总的复杂性为(n+range)(如果成功的话)。285 5、基数排序、基数排序v假定对范围在0999之间的10

12、个整数进行排序。v如果使用range=1000来调用BinSort，那么箱子的初始化将需要1000个执行步，节点分配需要10个执行步，从箱子中收集节点需要1000个执行步，总的执行步数为2010。295 5、基数排序、基数排序v不直接对这些数进行排序，而是采用一些基数r来分解这些数。v在基数排序（radix sort）中，把数按照某种基数分解为数字，然后对数字进行排序。v基数r=箱子个数305 5、基数排序、基数排序315 5、基数排序、基数排序v对于一般的基数r，相应的分解式为： x%r;(x%r2)/r;(x%r3)/r2;.v当使用基数r=n对n个介于0nc-1范围内的整数进行分解时，每

13、个数将可以分解出c个数字。v因此，可以采用c次箱子排序，每次排序时取range=n。整个排序所需要的时间为(cn)= (n)（因为c是一个常量）。326 6、堆排序、堆排序先将要排序的n 个元素初始化为一个最大堆，然后每次从堆中提取（即删除）元素。各元素将按递减次序排列。初始化所需要的时间为(n)，每次删除所需要的时间为O(logn) ，因此总时间为O(nlogn) 。336 6、堆排序、堆排序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;/ 在堆的析构函数中保存数组aH.Deactivate(x) ;346