数据结构答案 第10章 排序学习与指导

第10章排序

10.1 知识点分析

1．排序基本概念：

（1）排序

将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定

若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序

整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序

待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序

直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序

二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序

希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序

冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序

快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。

7．简单选择排序

（1）初始状态：整个数组r划分成两个部分，即有序区（初始为空）和无序区。

（2）基本操作：从无序中选择关键字值最小的记录，将其与无序区的第一个记录交换（实质是添加到有序区尾部）。

（3）从初态（有序区为空）开始，重复步骤（2），直到终态（无序区为空）。

8．堆排序

（1）把用数组来存储待排序的记录，将R[1..n]看成是一棵完全二叉树。

（2）利用完全二叉树双亲结点和孩子结点之间的内在关系，将其建成堆，从而在当前无序区中选择关键字最大的记录，然后将最大的关键字取出。

（3）对剩下的关键字再建堆，得到次大的关键字。

如此反复进行，直到最小值，从而将全部关键字排序好为止。

9．归并排序

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。其基本思想是：（1）将n个记录的待排序序列看成是有n个长度都为1的有序子表组成。

（2）将两两相邻的子表归并为一个有序子表。

（3重复上述步骤，直至归并为一个长度为n的有序表。

10．各种排序方法的比较

评估一个排序法的好坏，除了用排序的时间及空间外，尚需考虑稳定度、最坏状况和程序的编写难易程度。以下就常用的排序法按最坏情况下所需时间、平均所需时间、是否属于稳定排序、所需的额外空间等以表10-1来表示。

10-1 排序性能比较表

10.2 典型习题分析

【例1】当初始序列已按关键字有序时，用直接插入算法进行排序，需要比较次数为（）。

A．n-1 B．log2n C．2log2n D．n2

分析：直接插入排序是每趟从待排序列中取一个元素，按关键字从有序区间的尾部向前查找插入位置。当初始序列已按关键字值有序时，则每趟比较一个就找到了正确位置，也就是本身位置，则n个元素需要进行n-1趟排序，故总的比较为n-1次，答案为A。

【例2】一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序列进行一趟归并后的结果为（）。

A．12,38,25,35,50,74,63,90 B．12,38,35,25,74,50,63,90

C．12,25,35,38,50,74,63,90 D．12,35,38,25,63,50,74,90

分析：2路归并排序是将两个有序子表合并成一个新的有序表。其基本思想是：

（1）将n个记录的待排序序列看成是有n个长度都为1的有序子表组成；

（2）将两两相邻的子表归并为一个有序子表；

（3）重复上述步骤，直至归并为一个长度为n的有序表。

初始值12 38 35 25 74 50 63 90

第一趟排序结果：12 38 25 35 50 74 63 90

答案为A。

【例3】待排序的记录初态是按码值降序排列的，若欲将其按码值升序重新排列，则直接插入排序、简单选择排序和冒泡排序哪一个更好?

解：当待排序的记录初态是按码值降序排列时，用冒泡排序法比较和交换的次数最多；而直接插入排序和简单选择排序的比较次数相近。但是直接插入排序时记录的移动次数比较多。所以，当待排序的记录初态是按码值降序排列，要按码值升序重新排列时，用简单选择排序更好。

【例4】设待排序记录的初态是按关键字值递增排列的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增进行排序，则哪种排序方法最省时间？哪种排序方法最费时间？

解：堆排序和归并排序所用时间复杂度为O(nlog2n)；当待排记录的初始状态是按关键字值递增时，用快速排序法，因为每次选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区域少一个元素，使得元素比较只比上一趟少一次，所以总的时间复杂度为O(n2)；对于冒泡排序来说，其平均所需时间和最坏所需时间都是O(n2)，但是如果在算法中设置一个标志flag，用于记录每趟排序中是否出现记录的交换。如果没有交换，则表明待排序序列已经有序，则可结束排序。

综上所述本题采用这样冒泡排序所用时间最省；采用快速排序最费时间。

【例5】设有n个互不相同的元素，试问能否用少于2n-3次的比较次数，从这n个关键字中选出最大元素和最小元素？

解：若采用先选最小元素（通过n-1次比较得到），再在剩余的n-1个元素中选最大元素（通过n-2次比较得到）的方法，则共需要(n-1)+(n-2)=2n-3次比较。

可以通过成对比较元素，来减少比较次数。具体方法如下：

先比较第1对元素，较小者送当前最小变量min，较大者送当前最大变量max；然后依次对第i对元素（i=2，3……，??2/n），进行比较。对于每一对元素，做一次比较（大

小）以后，分别将较小者和当前最小元素变量min比较；将较大者和当前最大元素变量max比较（共比较3次）。若较小者小于min，则令较小者取代当前的min；若较大者大于max，则令较大者取代当前的max。待所有元素比较完成以后，max和min分别就是最大元素和最小元素。

因为第1对元素只比较了1次，其余的各对元素分别都需要进行3次比较，所以总的

比较次数是：1+(??2/n-1)╳3=3??2/n-2，显然小于2n-3次。

【例6】已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的第一趟的结果。

分析：设待排序列的下界和上界分别为low和high，R[low]是枢轴元素，一趟快速排序的具体过程如下：

（1）首先将R[low]中的记录保存到pivot变量中，用两个整型变量i，j分别指向low和high所在位置上的记录；

（2）先从j所指的记录起自右向左逐一将关键字和pivot.key进行比较，当找到第1个关键字小于pivot.key的记录时，将此记录复制到i所指的位置上去；

（3）然后从i+1所指的记录起自左向右逐一将关键字和pivot.key进行比较，当找到第1个关键字大于pivot.key的记录时，将该记录复制到j所指的位置上去；

（4）接着再从j-1所指的记录重复以上的（2）、（3）两步，直到i=j为止，此时将pivot 中的记录放回到i（或j）的位置上。一趟快速排序完成。

排序过程如下：

462

462 87 512

462 87 275 653 512

[462 87 275 61 170] 503 [897 908 653 512]

第一趟快速排序结果是462，87，275，61，170，503，897，908，653，512。

【例7】在快速排序法中，当R[low..high]中的关键字有序时，Partition（int i,int j）（参考教材P242-243快速排序算法）的返回值是什么？此时快速排序的运行时间是多少？应该如何修改，才能使得划分的结果是平衡的？

分析：如果R[low..high]中的关键字是递增有序的，则Partition返回值是low；如果R[low..high]中的关键字是递减有序，则Partition返回值是high。在这两种情况下，快速排序的运行时间均为：O(n2)。

要使划分的结果仅可能平衡，应选取其中间位置上的记录作为划分的基准为宜。我们可以通过修改Partition来实现：在进入扫描循环之前，取R[(low+high)/2]作为划分元，将其与R[low]交换，然后进入扫描循环。但是，若R[low..high]中的所有关键字均相同，则该方法仍然不能奏效，此时可以采用如下算法：

int Partition(SeqList R,int *i,int *j)

{ int pivot=R[(*i+*j)/2].key; // *i和*j是当前无序区的下界和上界RecType temp;

while(*i<=*j)

{

while(R[*i].key

(*i)++;

while(R[*j].key>pirot)

(*j)--;

if(*i<=*j)

{

temp=R[*i];

R[*i]=R[*j];

R[*j]=temp;

(*i)++;

(*j)--;

}

}

void QuickSort(SeqList R,int low,int high) // 递归形式的快速排序

{

int i=low,j=high;

if(low

{

Partition(R,&i,$j); // 调用Partition()函数

QuickSort(R,low,j); // 对低子表递归排序

QuickSort(R,i,high); // 对高子表递归排序

}

}

【例8】利用一维数组a可以对n个整数进行排序，其中一种排序算法的处理思想是：将n个整数分别作为数组a的n个元素的值，每次（即第i次）从元素a[i]到a[n]中挑出最小的一个元素a[k](i≤k≤n)，然后将a[k]与a[i]换位。这样反复n-1次完成排序。编写实现上述算法的函数：void sort(int a[],int n)。

分析：本排序法为直接选择排序法，算法如下：

void sort(int a[],int n) // 对数组a 中n个元素进行直接选择排序

{ int i,j,x,m;

for(i=1;i<=n-1;i++)

{

min=i; // min保存当前最小元素下标，初始值为i

for(j=i+1;j<=n;j++) // 从下一个元素到最后一个元素，找最小元素，并把下标存放在min

if (a[j]

min=j;

if (i!=min) // 如果第i个元素不是当前最小元素，则将最小元素与之交换

{ x=a[i];

a[i]=a[min];

a[min]=x;

}

}

}

【例9】将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重新编写直接插入排序算法。分析：用R[n]作哨兵，则在插入数据时则是由后向前递推，即来一个待插入的数，把该数插入到其后的序列是有序的数据序列中，此时把待插入的数放到R[n]中，然后找到插入其后序列的合适位置，此时需要把后续数据中的部分逐个前移，空出适当位置后，把R[n]中保存的插入值直接放到空位置中去。

算法如下：

void InsertSort(SqList R)

{ int i,j;

for(i=n-2;i>=0;i--)

if (R[i].key>R[i+1].key)

{ R[n]=R[i]; // R[n]是哨兵

j=i+1;

do{

R[j-1]=R[j]; // 将关键字小于R[i].key的记录向右移

j++;

}while(R[j].key

R[j-1]=R[n]; // 将R[i]插入到正确位置上

}

}

【例10】奇偶交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项……，如此反复，直到整个序列全部排好序为止。

分析：根据题目要求，可设一个布尔变量BL，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若BL为1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若BL为0，表示刚才没有交换，可以结束排序。

算法如下：

OddEvenSort ( int Vector[ ],int n)

{ int i, BL,temp;

do

{ BL = 0;

for ( i = 1; i < n-1; i += 2 ) // 扫描所有奇数项

if ( Vector[i] > Vector[i+1] ) // 相邻两项比较, 发生逆序

{ BL = 1; // 作交换标记

temp=Vector[i]; // 交换

Vector[i]=Vector[i+1];

Vector[i+1]=temp;

}

for ( i = 0; i < n-1; i += 2 ) // 扫描所有偶数项

if ( Vector[i] > Vector[i+1] ) // 相邻两项比较, 发生逆序

{ BL = 1; // 作交换标记

temp=Vector[i]; // 交换

Vector[i]=Vector[i+1];

Vector[i+1]=temp;

}

} while ( BL != 0 );

}

10.3 单元练习9解答

一．判断题答案

二．填空题答案

（1）比较

（2）时间复杂度（3）内排序（4）外存

（5）n-1

（6）i-1

（7）O(n2) （8）O(n2) （9）O(log2n) （10）O(n) （11）快速排序

（12）不变

（13）插入排序

（14）直接插入

（15）冒泡排序

（16）直接插入

（17）选择排序

（18）3

（19）L2

（20）54，72，60，96，80

三．选择题答案

四．排序过程分析答案

（1）10 8 18 15 7 16

第一趟结束时结果：[8 10] 18 15 7 16

第二趟结束时结果：[8 10 18] 15 7 16

第三趟结束时结果：[8 10 15 18] 7 16

第四趟结束时结果：[7 8 10 15 18] 16

第五趟结束时结果：[7 8 10 15 16 18]

（2）18 17 60 40 07 32 73 65

第一趟结束时结果：[17 18] 60 40 07 32 73 65

第二趟结束时结果：[17 18 60] 40 07 32 73 65

第三趟结束时结果：[17 18 40 60] 07 32 73 65

第四趟结束时结果：[07 17 18 40 60] 32 73 65

第五趟结束时结果：[07 17 18 32 40 60] 73 65

第六趟结束时结果：[07 17 18 32 40 60 73] 65

第七趟结束时结果：[07 17 18 32 40 60 65 73]

（3）17 18 60 40 7 32 73 65 85

第一趟排序结果：17 18 40 7 32 60 65 73

第二趟排序结果：17 18 7 32 40 60 65

第三趟排序结果：17 7 18 32 40 60

第四趟排序结果：7 17 18 32 40

第五趟排序结果：7 17 18 32

第五趟排序过程中已无记录交换，排序结束。

（4）80 18 09 90 27 75 42 69 34

第一趟排序结果：18 09 80 27 75 42 69 34

第二趟排序结果：09 18 27 75 42 69 34

第三趟排序结果：09 18 27 42 69 34

第四趟排序结果：09 18 27 42 34

第五趟排序结果：09 18 27 34

第六趟排序结果：09 18 27

第六趟排序过程中已无记录交换，排序结束。

（5）

10 18 4 3 6 12 9 15 8

d=4 6 12 4 3 8 18 9 15 10

d=2 4 3 6 12 8 15 9 18 10

d=1 3 4 6 8 9 10 12 15 18

（6）12 02 16 30 28 10 17 20 06 18

d=5

10 02 16 06 18 12 17 20 30 28

d=2

12 02 16 06 17 12 18 20 30 28

d=1 02 06 10 12 16 17 18 20 28 30

（7）

[10] [18] [4] [3] [6] [12] [9] [15]

[10 18] [3 4] [6 12] [9 15] 第一趟排序结果

[3 4 10 18] [6 9 12 15] 第二趟排序结果

[3 4 15 18] 第三趟排序结果（8）[53 36 48 36 60 7 18 41]

（7）[36 48 36 60 53 18 41]

（7 18）[48 36 60 53 36 41]

（7 18 36）[48 60 53 36 41]

（7 18 36 36）[60 53 48 41]

（7 18 36 36 41）[53 48 60]

（7 18 36 36 41 48）[53 60]

（7 18 36 36 41 48 53）[60]

（7 18 36 36 41 48 53 60 ）

（9）

10 15

low high

7 1 15 15

low high

交换

第一趟排序结果：7 1 [10] 18 15 15

low high

（10）7 1 10 18 15 15

五．程序填空答案

（1）n

（2）n

（3）<=

（4）m=(low+high)/2

（5）R[ j ]

六．算法题答案

（1）【函数代码】

void selectsort(pointer h)

{ pointer p,q,r,s,t;

t=NULL;

while(h)

{ p=h; q=NULL;

s=h; r=NULL;

while (p)

{ if (p->keykey)

{ s=p; p=q; }

if (s==h)

h=h->link;

else

h=s;

s->link=t;

t=s;

}

h=t;

}

}

（2）【函数代码】

void InsertList(List head)

{ Lnode *p, * pprev,q,*qprev, *current;

if (!head)

return;

pprev=head;

p=head->next;

while (p)

{ q=head;

qprev=NULL;

while (q->key < p->key) // 查找插入位置

{qprev=q; q=q->next;}

if (q= =p) // p最大，无须插入

{pprev=p; p=p->next;}

else

{ current=p; p=p->next;

pprev->next=p;

current->next=q;

if (q==head) // 插在表头

head=current;

else // 插在中间某个位置上

qprev->next=current;

}

}

}

（3）【函数代码】

void part (int a[ ])

{ i=1;j=n; // 初、终下标

while (i

{ while (i=0) // 自右向左找非负数

j--;

while (i

i++;

if (i

{ t=a[i];

a[i]=a[j];

a[j]=t;

i++;

j--;

}

}

}

（4）设已排序的文件用单链表表示，再插入一个新记录，仍然按关键字从小到大的次序排序，试写出该算法。

void insert(lklist head;datatype x)

{ s=new ( node );

s->key=x;

s->next= NULL;

if (head= =NULL)

head=s;

else

{ p=head;

q= NULL;

while (( p! =NULL) && (s->key > p->key )) { q=p; p=p->next; }

if (q= =NULL)

{ s->next=head; head=s; }

else

{ if (p==NULL)

q->next=s;

else

{ s->next=q->next; q->next=s; } }

}

}

数据结构排序习题

07排序 【单选题】 1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。 A、直接插入 B、简单选择 C、希尔 D、二路归并 2. 直接插入排序在最好情况下的时间复杂度为（B）。 A、O(logn) B、O(n) C、O(n*logn) D、O(n2) 3. 设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（B）。 A、79,46,56,38,40,80 B、84,79,56,38,40,46 C、84,79,56,46,40,38 D、84,56,79,40,46,38 4. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。 A、38,40,46,56,79,84 B、40,38,46,79,56,84 C、40,38,46,56,79,84 D、40,38,46,84,56,79 5. 将两个各有n个元素的有序表归并成一个有序表，最少进行（A）次比较。 A、n B、2n-1 C、2n D、n-1 6. 下列排序方法中，排序趟数与待排序列的初始状态有关的是（C）。 A、直接插入 B、简单选择 C、起泡 D、堆 7. 下列排序方法中，不稳定的是（D）。 A、直接插入 B、起泡 C、二路归并 D、堆 8. 若要在O(nlog2n)的时间复杂度上完成排序，且要求排序是稳定的，则可选择下列排序方法中的（C）。 A、快速 B、堆 C、二路归并 D、直接插入 9. 设有1000个无序的数据元素，希望用最快的速度挑选出关键字最大的前10个元素，最好选用（C）排序法。 A、起泡 B、快速 C、堆 D、基数 10. 若待排元素已按关键字值基本有序，则下列排序方法中效率最高的是（A）。 A、直接插入 B、简单选择 C、快速 D、二路归并 11. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的两趟排序后的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 12. （A）占用的额外空间的空间复杂性为Ｏ(1)。 A、堆排序算法 B、归并排序算法 C、快速排序算法 D、以上答案都不对

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构第十章习题课

1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

中南大学数据结构与算法第10章内部排序课后作业答案

第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937

(2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为：\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

数据结构各种排序算法的时间性能

HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能学生姓名 学生学号 专业班级 指导老师李晓鸿 完成日期

设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略 二、概要设计

数据结构 各种排序算法

数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() 效率：O(N2) 2. 选择排序 selectSort public void selectionSort() { int out, in, min; for(out=0; out

swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率：O(N2) 3. 插入排序 insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item to right --in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort() 效率：比冒泡排序快一倍，比选择排序略快，但也是O(N2) 如果数据基本有序，几乎需要O(N)的时间

数据结构课程设计(内部排序算法比较 C语言)

课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------|

|-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构第九、十章 作业答案

第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索 表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1 的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

数据结构-各类排序算法总结

数据结构-各类排序算法总结 原文转自： https://www.sodocs.net/doc/e212979415.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可

能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。

南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统

—— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图：

——

main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到

目前最完整的数据结构1800题包括完整答案 第十章 排序

第10章排序 一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 （1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

数据结构课程设计(内部排序算法比较-C语言)

` 课题：内部排序算法比较… 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： !

|******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ~ 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 、 第三章系统设计 （I）友好的人机界面设计：（如图所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ： （）

数据结构第10章 内部排序习题

第10章内部排序 一、单项选择题 1．若要尽可能地完成对实数数组得排序，且要求排序是稳定的，则应选______。 A．快速排序 B．堆排序 C．归并排序 D．基数排序 2．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用______方法最快。 A．冒泡排序 B．快速排序 C．希尔排序 D．堆排序 E．简单选择排序 3．将两个各有N个元素的有序表归并成一个有序表，其最小的比较次数是______。 A．N B．2N-1 C．2N D．N-1 4．就平均性能而言，目前最好的内排序方法是______排序法。 A．冒泡排序 B．希尔排序 C．插入排序 D．快速排序 5．若需要在O(nlog2n)的时间内完成对数据的排序，且要求排序是稳定的，则可选择的排序方法是______。 A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 6．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是______。 A．选择排序法 B．插入排序法 C．快速排序法 D．堆排序法 7．数据序列｛8，9，10，4，5，6，20，1，2｝只能是下列排序算法中的（）的两趟排序后的结果。

A．选择排序 B．冒泡排序 C．插入排序 D．堆排序 8．对一组数据｛84，47，25，15，21｝排序，第一趟的排序结果为15，47，25，84，21；第二趟排序的结果为15，21，25，84，47；第三趟排序的结果为15，21，25，47，84，则采用排序的方法是______。 A．选择排序 B．冒泡排序 C．快速排序 D．插入排序 9．下列排序算法中______排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A．选择排序 B．冒泡排序 C．归并排序 D．堆排序 10．在下面的排序方法中，辅助空间为O（n）的是______。 A．希尔排序 B．堆排序 C．选择排序 D．归并排序 11．直接插入排序在最好的情况下的时间复杂度为______。 A．O（log2n） B．O(n) C． O(nlog2n) D．O(n2) 12．若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行______次比较。 A．3 B．10 C．15 Ｄ．25 13．对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经过一趟后序列变为{15，-1，4，8，20，9，7}，则该次采用的增量是 ______。 A．1 B．4 C．3 D．2 14．对下列关键字序列用快速排序法进行排序，速度最快的情形是

数据结构严蔚敏版第十章答案

第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j]

数据结构中的内部排序算法及性能分析

数据结构中的排序算法及性能分析 一、引言 排序（sorting ）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。 在此首先明确排序算法的定义： 假设n 个记录的序列为 { 1R ，2R ，…n R } （1） 关键字的序列为： { 1k ，2k ，…，n k } 需要确定1，2，…，n 的一种排列：12,n p p p ，…，使（1）式的序列成为一个按关键字有序的序列： 12p p pn k k k ≤≤≤… 上述定义中的关键字Ki 可以是记录Ri （i=1,2，…，n ）的主关键字，也可以是记录i R 的次关键字，甚至是若干数据项的组合。若在序列中有关键字相等的情况下，即存在i k =j k （1,1,i n j n i j ≤≤≤≤≠），且在排序前的序列中i R 领先于j R 。若在排序后的序列中Ri 仍领先于j R ，则称所用的排 序方法是稳定的；反之若可能使排序后的序列中j R 领先于i R ，则称所用的排序方法是不稳定的。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。 在刚才提到的时间频度中，n 称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

数据结构第九章排序习题及答案

习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

数据结构内排序实验报告

一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i=0 && temp.key

各种排序算法,数据结构中的排序算法

1.直接插入排序 //InsertSort.cpp //This function is to sort SqList # include # include # define MAXSIZE 20 # define MAX_LENGTH 100 typedef int RedType; typedef struct //define structure SqList { RedType r[MAXSIZE+1]; int length; }SqList; void InsertSort(SqList &L) //InsertSort() sub-function { int i,j; for(i=2;i<=L.length;++i) if(L.r[i]>L.length; for(i=1;i<=L.length;++i) { cout<<"Please input the "<>L.r[i]; } cout< # include