数据结构第六章排序试卷.ppt

930 063 083 184 505 278 008 109 589 269 0 1 2 3 4 5 6 7 8 9 q.e 0 1 2 3 4 5 6 7 8 9 q.f 930 063 083 184 505 278 008 109 589 269 505 008 109 930 063 269 278 083 184 589 0 1 2 3 4 5 6 7 8 9 q.e 0 1 2 3 4 5 6 7 8 9 q.f 505 008 109 930 063 269 278 083 184 589 008 063 083 109 184 269 278 505 589 930 #define KEY_NUM … #define RADIX … #define MAX_SPACE … Typedef struct { KeyType keys[KEY_NUM]; InfoType otheritems; int next; }NodeType; Typedef struct { int f; int e; }Q_Node; Typedef Q_Node Queue[RADIX]; void Distribute(NodeType R[],int i,Queue q) { int j; for(j=0;jRADIX;j++) q[j].f=q[j].e=0; for(p=R[0].next; p ;p=R[p].next) { j=ord(R[p].keys[i]); if(!g[j].f) g[j].f=p; else R[q[j].e].next=p; q[j].e=p; } void Collect (NodeType R[];int I,Queue q) { int j; for(j=0;!q[j].f;j=succ(j)) R[0].next=q[j].f; t=q[j].e; while(jRADIX) {for(j=succ(j);jRAIX-1 !q[j] .f ;j=succ(j)); if(q[j].f) { R[t].next=q[j].f; t=q[j].e; } } } void RadxSort( NodeType R[],int n) { Queue q; for( i=0;in;i++) R[i].next=i+1; R[n].next=0; for(i=0;iKEY_NUM;i++) { Distribute( R,i,q) Collect(R,i,q) } } 基数排序的时间是线性的(即O(n))。??? 　基数排序所需的辅助存储空间为O(n+rd)。??? 　基数排序是稳定的。 (1).平均时间性能：以快速排序法最佳，但最坏情况下不如堆排序和归并排序；在n较大时，归并排序比堆排序快，但所需辅助空间最多。 (2).简单排序以直接插入排序最简单，当下列中记录“基本有序”或n值较小时，是最佳的排序方法。因此常和其他排序方法结合使用。 (3).基数排序最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则也可以先按“最高位关键字”不同将序列分成若干个子序列，而后用直接插入排序。 (4).从稳定性来看，基数排序是稳定的排序方法，大部分时间复杂度为 的简单排序法都是稳定的。然而，快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。一般来说，排序过程中的比较是 在相邻的两个记录关键字之间进行的排序方法是稳定的。大多数情况下排序是按记录的主关键字进行的，则所有的排序方法是否稳定无关紧要。当排序是按记录的次关键字进行时，则应根据问题所需慎重选择。 本章讨论的大多数算法是在顺序存储结构上进行的，因此在排序过程中要进行大量的记录的移动。当记录很大(即每个记录所占的空间很大)时，记录移动所耗费的时间也很多，此时可采用静态链表作存储结构，如表插入排序，链式