c2c模式的网站有哪些,公司网络规划与设计,网站建设分解结构,上海英文网站建设目录
一. 选择排序
#xff08;1#xff09;简单选择排序
#xff08;2#xff09;堆排序
二. 归并排序
三. 基数排序
四. 各种排序方法的比较
#xff08;1#xff09;时间性能
#xff08;2#xff09;空间性能
#xff08;3#xff09;排序方法的稳定性能…目录
一. 选择排序
1简单选择排序
2堆排序
二. 归并排序
三. 基数排序
四. 各种排序方法的比较
1时间性能
2空间性能
3排序方法的稳定性能
4关于“排序方法的时间复杂度的下限” 一. 选择排序
1简单选择排序
基本思想在待排序的数据中选出最大(小)的元素放在其最终的位置。 基本操作: 1首先通过n-1次关键字比较从n个记录中找出关键字最小的记录将它与第一个记录交换。 2再通过n-2次比较从剩余的n-1个记录中找出关键字次小的记录将它与第二个记录交换。 3重复上述操作共进行n-1趟排序后排序结束。 不难写出算法
void SelectSort(SqList L){for(i1; iL.length; i){ki; //第i趟从第i个元素开始for(ji1; jL.length; j)if(L.r[j].key L.r[k].key) kj; //记录最小值位置if(k!i) L.r[i]←—→L.r[k]; //交换}
}下面我们分析时间复杂度。对移动次数来说最好情况是0最坏情况是3(n-1)也就是每一趟都得移动每次移动需要移动3次。对比较次数来说无论待排序列处于什么状态选择排序所需进行的比较”次数都相同为。
上面的算法是不稳定排序但是可以稳定化。具体的说用数组实现的选择排序是不稳定的用链表实现的选择排序是稳定的。例如给定858*79第1次588*79第2次578*89从而可以验证它是不稳定的。
2堆排序
堆的定义若n个元素的序列满足或则分别称该序列为小根堆和大根堆。从堆的定义可以看出堆实质是满足如下性质的完全二叉树二叉树中任一非叶子结点均小于(大于)它的孩子结点。 显然大根堆的根结点是最大值小根堆的根结点是最小值。若在输出堆顶的最小值(最大值)后使得剩余n-1个元素的序列又重建成一个堆则得到n个元素的次小值次大值)....如此反复便能得到一个有序序列这个过程称之为堆排序。
那么怎么重建呢以小大根堆为例 1输出堆顶元素之后以堆中最后一个元素编号最大的元素替代之 2然后将根结点值与左、右子树的根结点值进行比较并与其中小大者进行交换 3重复上述操作直至叶子结点将得到新的堆称这个从堆顶至叶子的调整过程为“筛选”。
例如对下面的小根堆把13输出最后一个元素97作为根结点它的左右孩子是38和2727较小所以把97和27交换。此时97的左右孩子是65和4949较小把49和97交换这个时候97已经是叶子结点就不用再操作了。 写出算法如下
void HeapAdjust(elem R[], int s, int m){
/*已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义本函数调整R[s]的关键字使R[s..m]成为一个大根堆*/rc R[s];for (j2*s; jm; j * 2){ //沿key较大的孩子结点向下筛选if (j m R[j] R[j1]) j; //j为key较大的记录的下标if (rc R[j]) break; //rc大于左右孩子这个时候已经符合要求就不用做了R[s] R[j]; //较大的孩子结点往上升s j; //rc应插入在位置s上更新s}//forR[s] rc; //插入
}//HeapAdjustHeapAdjust函数是一个用于调整堆的函数。它接受一个数组R以及两个整数s和m作为参数。s表示要调整的子树的根节点的位置m表示该子树的最后一个节点的位置。
首先将根节点的值保存在变量rc中。然后通过一个循环来比较根节点和其子节点的值。在循环中变量j初始化为根节点的左子节点的位置2*s然后每次乘以2即可得到下一个子节点的位置。在循环中首先判断是否存在右子节点并且右子节点的值是否大于左子节点的值。如果满足条件则将j加1即将j指向右子节点。然后判断rc的值是否大于等于R[j]的值。如果满足条件则退出循环。如果rc的值小于R[j]的值则将R[j]的值赋给R[s]即将较大的子节点的值上移到根节点的位置。然后将s更新为j即将s指向较大子节点的位置。循环结束后将rc的值赋给R[s]即将根节点的值放到合适的位置上。这样HeapAdjust函数完成了对以s为根节点的子树的调整使其满足堆的性质。
可以看出对一个无序序列反复“筛选”就可以得到一个堆。即从一个无序序列建堆的过程就是一个反复“筛选”的过程。我们重新考察堆的定义显然单结点的二叉树是堆在完全二叉树中所有以叶子结点序号i n/2这里是整除向下取整)为根的子树也是堆。这样我们只需依次将以序号为n/2n/2 - 1.....1的结点为根的子树均调整为堆即可。即对应由n个元素组成的无序序列“筛选”只需从第n/2个元素开始。
由于堆实质上是一个线形表那么我们可以顺序存储一个堆。下面以一个实例介绍建一个小根堆的过程。例如给定关键字为4938659776132749的一组记录将其按关键字调整为一个小根堆 将初始无序的R[1]到R[n]建成一个小根堆可用以下语句实现
for(i n/2 ; i 1; i--)HeapAdjust (R, i, n);
上面我们了解了怎么建堆。若对一个无序存列建堆然后输出根。重复该过程就可以由一个无需序列输出有序序列。实质上堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。
void HeapSort(elem R[]){ //对R[1]到R[n]进行堆排序int i;for (i n/2; i 1; i--)HeapAdjust(R, i, n);//建初始堆for (i n; i 1; i--){ //进行n-1趟排序Swap(R[1], R[i]); //根与最后一个元素交换也就是把根结点输出并放在最后一个位置HeapAdjust(R, 1, i-1); //对R[1]到R[i-1]重新建堆}
}//HeapSort最后我们来研究时间复杂度。初始堆化所需时间不超过O(n)排序阶段不含初始堆化)每次重新堆化所需时间不超过O(logn)则n-1次循环所需时间不超过O(nlogn)。因此 Tw(n)O(n) O(nlogn) O(nlogn)
堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下其时间复杂度也为O(nlog2n)这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列都不会使堆排序处于最好或最坏的状态。另外堆排序仅需一个记录大小供交换用的辅助存储空间。
然而堆排序是一种不稳定的排序方法它不适用于待排序记录个数n较少的情况但对于n较大的文件还是很有效的。
二. 归并排序
基本思想将两个或两个以上的有序子序列“归并”为一个有序予列。在内部排序中通常采用的是2-路归并排序。即将两个位置相邻的有序子序列R[1..m]和R[m1..n]归并为一个有序序列R[1..n]。 这种树称为归并树。n个元素归并排序只需要趟。下面讨论怎么把两个有序序列合并成一个有序序列。这里可以参考线性表的合并算法。设R[low]-R[mid]和R[mid1]-R[high]为相邻归并成一个有序序列R1[low] - R1[high]. 若SR[i].keySR[j].key则TR[k]RS[i];k;i; 否则TR[k]SR[j];k;j;
归并排序的时间效率是O(nlog2n)空间效率是O(n)因为需要一个与原始序列同样大小的辅助序列(TR)。这正是此算法的缺点。归并排序算法是稳定的算法。
三. 基数排序
基本思想分配收集
基数排序也叫桶排序或箱排序设置若干个箱子将关键字为k的记录放入第k个箱子然后在按序号将非空的连接。基数排序的数字是有范围的均由0-9这十个数字组成则只需设置十个箱子相继按个、十、百...进行排序。例给定待排序序列(614738921485637101215530790306)。这里每一个箱子都是一个队列遵循先进先出的原则 至此排序完成基数排序的时间效率O(k*(nm))其中k:关键字个数上面有3个关键字m:关键字取值范围为m个值上面为10n元素个数。这里每一趟分配n个元素收集m个桶总共需要k遍。
空间效率:这里需要放置m个桶回收的时候回收n个元素则空间复杂度是O(nm)。基数排序是稳定的。
四. 各种排序方法的比较
1时间性能
1.按平均的时间性能来分有三类排序方法:
时间复杂度为O(nlogn)的方法有快速排序、堆排序和归并排序其中以快速排序为最好时间复杂度为O(n^2)的有直接插入排序、冒泡排序和简单选择排序其中以直接插入为最好特别是对那些对关键字近似有序的记录序列尤为如此时间复杂度为O(n)的排序方法只有基数排序。
2.当待排记录序列按关键字顺序有序时直接插入排序和冒泡排序能达到到O(n)的时间复杂度而对于快速排序而言这是最不好的情况此时的时间性能退化为O(n^2)因此是应该尽量避免的情况。 3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
2空间性能
指的是排序过程中所需的辅助空间大小. 1.所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1) 2.快速排序为O(logn)为栈所需的辅助空间 3.归并排序所需辅助空间最多其空间复杂度为O(n) 4.链式基数排序需附设队列首尾指针则空间复杂度为O(rd)
3排序方法的稳定性能
稳定的排序方法指的是对于两个关键字相等的记录它们在序列中的相对位置在排序之前和经过排序之后没有改变。
当对多关键字的记录序列进行LSD方法排序时必须采用稳定的排序方法。对于不稳定的排序方法只要能举出一个实例说明即可。快速排序和堆排序是不稳定的排序方法。
4关于“排序方法的时间复杂度的下限”
本章讨论的各种排序方法除基数排序外其它方法都是基于“比较关键字”进行排序的排序方法可以证明这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。
可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。
