第8章怎样研究算法:排序算法示例
1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。
(A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多；
(B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多；
(C)对无序数据集合，两个算法X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢；
(D)上述说法有不正确的；
答案：C
解释：
本题考核排序算法的研究
在大规模数据集合中查找，有序数据集合有利算法进行和判断，要比无序数据集合查找的快，对于（C）选项，Y算法尽管需要排序后再处理，但排序处理后的数据查找更加快捷，因此可能Y算法比X算法更快。
具体内容请参考排序算法以及第八章课件。
2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 1. 假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；
Step 2. 计算中间记录位置I = (Start+Finish)/2，读取第I条记录。
Step 3. 判断第I条记录的成绩与给定查找分数：
(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；
(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；
(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。
End of algorithm A3
针对上述三个算法，回答下列问题：
(1)关于算法A1, A2, A3的快慢问题，下列说法正确的是_____。
(A)算法A1快于算法A2，算法A2快于算法A3；
(B)算法A2快于算法A1，算法A2快于算法A3；
(C)算法A3快于算法A2，算法A2快于算法A1；
(D)算法A1快于算法A3，算法A3快于算法A2；
(E)上述都不正确。
答案：C
解释：
本题考核排序算法的研究
首先，数据是有序排列的，从大到小。
算法A1依次搜索，穷举。
算法A2与A1一样，穷举，不同的是它利用数据是从大到小排序的特点，因此，如果当前数据比如果小于目标数，那么说明只有的也一定小于，则目标不在序列中。因此，A2比A1快。
算法A3利用数据有序特点，采用二分查找，每次将目标数与中间值比较，缩小搜索范围，因此A3比A2快。
综上，答案选（C）。
具体内容请参考排序算法以及第八章课件。
(2)关于算法A3，下列说法正确的是_____。
(A)对数据表中的任何数据，算法A3都适用；
(B)对数据表中任何已排序的数据，算法A3都适用；
(C)对已按成绩排序的数据表，算法A3都适用；
(D)对已按成绩进行降序排列的数据表，算法A3都适用；
(E)上述都不正确。
答案：D
解释：
本题考核排序算法的研究
算法A3需求的数据应该是排序的，而且是对成绩排序的，因此排除（A）（B）。其次，按照算法A3，应该是降序排序的数据才可用，因为升降序决定了算法二分查找的重订搜索范围实在中间值的左边还是右边，对于算法A3,要求是降序的。因此选择（D）。
具体内容请参考排序算法以及第八章课件。
(3)关于算法A3和算法A1，下列说法正确的是_____。
(A)如果数据表中记录数越多，则算法A3相比算法A1的优势越明显，即查找时间越短；
(B)如果数据表中记录数越多，则算法A1相比算法A3的优势越明显；即查找时间越短；
(C)算法A3和算法A1的执行时间差异不会随数据表中记录数多少而变化；
(D)上述都不正确。
答案：A
解释：
本题考核排序算法的研究
数据越多，算法A1穷举，查找时间正比增加，算法A3二分查找，每次可缩小一半的查找范围，数据越多，优势越明显，算法A1时间复杂度是O(n), 算法A3时间复杂度是O(log2n)，因此选择（A）。
具体内容请参考排序算法以及第八章课件。
(4)关于三个算法的复杂性，下列说法正确的是_____。
(A)算法A1、A2和A3的时间复杂性都为O(n)；
(B)算法A1和A2的时间复杂性为O(1)，算法A3的时间复杂性为O(n)；
(C)算法A1的时间复杂性为O(n)，算法A2的时间复杂性为O(n/2)，算法A3的时间复杂性为O(n/4)；
(D)算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为O(log2 n)；
(E)上述都不正确。
答案：D
解释：
本题考核排序算法的研究
数据越多，算法A1穷举，线性查找，平均比较次数(n+1)/2，时间复杂度O(n)。算法A2同样是线性查找，只是多了对剩余数据的判断，时间复杂度和A1一样，同样是O(n)。
算法A3二分查找，每次可缩小一半的查找范围，算法A3时间复杂度是O(log2n)，因此选择（D）。
具体内容请参考排序算法以及第八章课件。
(5)针对按成绩降序排列的数据表，假设记录数为n，关于算法A2，下列说法正确的是_____。
(A)算法A2在任何情况下都需要读取n条记录，才能得到结果；
(B)算法A2在任何情况下都需要读取n/2条记录，才能得到结果；
(C)算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果；
(D)算法A2在任何数据分布情况下，平均要读取n/2条记录才能得到结果；
(E)上述都不正确。
答案：C
解释：
本题考核排序算法的研究
对于算法A2，最好情况：读取1条记录，刚好等于目标数，算法结束；或者读取1条记录，该记录小于目标数，因成绩降序排列，剩余数据都小于目标，所以记录中没有目标查询数，算法结束。
最坏情况：读取了n条记录，最后一条记录等于，则返回结果，不等于，则不在记录中。算法结束。
综上，选择（C）。
具体内容请参考排序算法以及第八章课件。
3、关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。
(1)若要在n个全文文档中(n可能很大)查找有无某个关键词的文档，为提高检索效率，最好的做法是_____。
(A)直接用给定关键词来匹配每一份文档中的每一个词汇。若该文档存在匹配成功的词汇，则输出该文档；否则，不输出该文档。
(B)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。
(C)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”。
(D)选项(B)(C)比选项(A)的做法好，但选项(B)(C)没有效率上的差别。
答案：C
解释：
本题考核排序算法的研究
由题意知，n个全文文档数据量很大，若全文搜索，检索效率会很低，因此排除（A）。建立“关键字”索引表，并包含“文档编号”，可以有效的缩小查找范围。同时，对索引表进行排序，可以有效的提高查找效率。因此，选择（C）。
具体内容请参考查找，排序算法以及第八章课件。
(2)若要在n个全文文档中(n可能很大)查找与某个关键词最相关的文档，为提高检索效果和检索效率，最好的做法是_____。
(A)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”。
(B)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。
(C)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。
(D)选项(B)(C)比选项(A)的做法好，但选项(B)(C)在执行效果和执行效率方面没有什么差别。
答案：C
解释：
本题考核排序算法的研究
由题意知，要寻找与关键词最相关的文档，做法是以关键词出现次数为评判标准。建立索引表，包含“关键词”，因要查找与关键词最相关的文档，所以需求相关文档中出现的“次数”，故而排除（A）选项，对于（B）（C），（C）选项中对关键词相同的文档进一步按“次数”进行降序排序，可以提高检索效率，因此选择（C）选项。
具体内容请参考查找，排序算法以及第八章课件。
(3)针对下列问题求解方法：对n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找次数最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。问该方法涉及到几类算法，说法正确的是_____。
(A)涉及字符串的字母序排序算法；
(B)涉及数值属性排序算法；
(C)涉及字符串匹配算法；
(D)涉及数值属性查找算法；
(E)涉及上述全部算法；
答案：E
解释：
本题考核排序算法的研究
查找关键词，设计字符串匹配算法。对索引表按关键字进行字母序的排序，设计字符串的字母序排序算法。关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序，涉及数值属性排序算法。寻找次数最多的m个索引项，涉及数值属性查找算法。综上，选择（E）。
具体内容请参考查找算法以及第八章课件。
(4)上图给出了一种“自动获取文档关键词”的方法，关于该方法的表述，最好的是_____。
(A)文档中出现次数最多的词汇必定是关键词；
(B)文档中去掉标点符号后，出现次数最多的词汇必定是关键词；
(C)文档中去掉标点符号和一些辅助词汇，出现次数最多的词汇必定是关键词；
(D)文档中去掉标点符号和一些辅助词汇，出现次数最多且次数达到一定数值的词汇必定是关键词；
(E)上述说法都不正确；
答案：D
解释：
本题考核排序算法的研究
“自动获取文档关键词”的方法是一个充分不必要条件。
关键词应排除标点符号和辅助词汇，因此排除（A）（B）。出现次数最多，但不能对单个文档而言就凭次数判断关键词，必须达到一定的标准，故而选择（D）。
具体内容请参考排序算法以及第八章课件。
4、关于“内排序”算法和“外排序”算法，下列说法不正确的是_____。
(A)“内排序”算法通常是内存中数据排序常用的算法，而“外排序”算法通常是大规模数据排序常用的算法；
(B)“内排序”算法由于内存排序应用的频繁性，所以算法要考虑用尽可能少的步骤，而“外排序”算法由于要利用磁盘保存中间结果，所以算法主要考虑尽可能少的读写磁盘；
(C)无论是“内排序”算法，还是“外排序”算法，都需要考虑读写磁盘的代价问题；
(D)对一组需要排序的数据，能应用“内排序”算法时，尽量不用“外排序”算法；
答案：C
解释：
本题考核排序算法的研究
内排序：待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据；
外排序：待排序的数据保存在磁盘上，不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理；
由上可知（A）（B）正确，（C）错误。
具体内容请参考排序算法以及第八章课件。
5、下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答下列问题。
INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3．for j=i+1 to N
4. { if A[j] 5. if k<>i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j+1]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } (1)关于INSERTION-SORT算法的基本思想，下列说法正确的是_____。 (A)一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。 (B)一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。 (C)一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。 (D)上述说法都不正确。 答案：A 解释： 本题考核排序算法的研究 （A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。 具体内容请参考内排序算法以及第八章课件。 (2)关于SELECTION-SORT算法的基本思想，下列说法正确的是_____。 (A)一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。 (B)一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元 素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。 (C)一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。 (D)上述说法都不正确。 答案：B 解释： 本题考核排序算法的研究 （A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。 具体内容请参考内排序算法以及第八章课件。 (3)关于BUBBLE-SORT算法的基本思想，下列说法正确的是_____。 (A)一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。 (B)一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。 (C)一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。 (D)上述说法都不正确。 答案：C 解释： 本题考核排序算法的研究 （A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。 具体内容请参考内排序算法以及第八章课件。 (4)关于排序的选择法和冒泡法，下列说法不正确的是_____。 (A)“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别； (B)“选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素； (C)虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。这样来看，选择法比冒泡法要快一些； (D)上述说法有不正确的。 答案：A 解释： 本题考核排序算法的研究 “选择”与“冒泡”都是每轮查找出最小值，方法不同（B）选项是正确的，但效率是有不同的，（C）中描述正确，选择排序调用swap要比冒泡排序少，因此，选择（A）具体内容请参考内排序算法以及第八章课件。 (5)关于三种排序算法，下列说法正确的是_____。 (A)三种算法的时间复杂度都为O(n2)，所以三种算法的执行效率是一样的； (B)尽管三种算法的时间复杂度都为O(n2)，但细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些； (C)尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的； (D)尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行。 答案：D 解释： 本题考核排序算法的研究 三种算法的时间复杂度都是O(n2)，但是细致比较是有差别的，（A）错误，如果被排序的记录很大，执行交换所需时间是客观的，将远远大于比较关键字和计算数组下标的时间。冒泡和插入排序调用次数最多，为n(n-1)/2，选择排序每遍只在选出最小记录后进行一次交换，需调用n-1次，因此（B）错误，有因为内排序算法要被频繁执行，因此这种差别对内排序问题而言是重要的，故而选择（D）。 具体内容请参考内排序算法以及第八章课件。 (6)阅读INSERTION-SORT算法，关于第4.行至第6.行间程序段的作用，下列说法正确的是_____。 (A)将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置； (B)将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置。 (C)将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向前移动一个位置。 (D)将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置。 答案：D 解释： 本题考核排序算法的研究 插入排序，算法中J从I-1到1，递减，排除（B）（C），将大于key的元素依次向后移动，因而选择（D）。 具体内容请参考内排序算法以及第八章课件。 (7)阅读SELECTION-SORT算法，关于第3.行至第4.行间程序段的作用，下列说法正确的是_____。 (A)循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中； (B)循环地在未排序元素集合中找最小值元素，该元素保存在变量k中； (C)循环地在未排序元素集合中找最大值元素的位置，该位置保存在变量k中； (D)循环地在未排序元素集合中找最大值元素，该元素保存在变量k中； 答案：A 解释： 本题考核排序算法的研究 选择排序，算法中k记录的是最小元素的位置，交换条件：A[j] 具体内容请参考内排序算法以及第八章课件。 (8)阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。 (A)第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较； (B)第4轮次，是将第1个元素至第20个元素之间的元素，相邻者进行比较； (C)第8轮次，是将第20个元素至第12个元素之间的元素，相邻者进行比较； (D)第11轮次，是将第20个元素至第1个元素之间的元素，相邻者进行比较； 答案：A 解释： 本题考核排序算法的研究 冒泡排序，每遍找出最小元素，方法是依次将相邻元素两两比较，逐渐分成两个部分：已排和未排，N=20，第5次时，16至20号元素已排序完成，需要将是将第1个元素至第15个元素之间的元素，相邻者进行比较，选择（A）。 具体内容请参考内排序算法以及第八章课件。 (9)阅读BUBBLE-SORT算法，下列说法正确的是_____。 (A)该算法在N=20时，必定要执行20个轮次的内循环； (B)该算法在N=20时，必定要执行19个轮次的内循环； (C)该算法在N=20时，最多要执行20个轮次的内循环； (D)该算法在N=20时，最多要执行19个轮次的内循环； 答案：D 解释： 本题考核排序算法的研究 冒泡排序，内循环是两两相邻元素依次比较，其中如果发生交换，即元素大小次序不满足要求，变量haschange为true，若haschange为false，则说明经过一次遍历之后，没有发生过相邻元素交换，即当前序列满足排序的要求，说明任务已完成，算法结束，不需要执行 内循环。因此，当N=20时，i到N-1，最多需要执行19次内循环。因此选择（D）。 具体内容请参考内排序算法以及第八章课件。 (10)阅读BUBBLE-SORT算法，其中关于haschange变量的作用，下列说法不正确的是_____。 (A)haschange用于标记每个轮次的相邻元素比较中，是否有“交换”发生； (B)haschange用于判断至某个轮次时是否已完成排序，以便提前结束算法； (C)haschange需要在每轮次之前置初始值为假，表示没有“交换”发生； (D)涉及haschange的语句全部去掉，算法仍旧能够正确执行； (E)上述说法有不正确的。 答案：E 解释： 本题考核排序算法的研究 冒泡排序，内循环是两两相邻元素依次比较，其中如果发生交换，即元素大小次序不满足要求，变量haschange为true，若haschange为false，则说明经过一次遍历之后，没有发生过相邻元素交换，即当前序列满足排序的要求，说明任务已完成，算法可结束，如果将设计haschange的语句全部去掉，算法依旧能够执行，只是在已排序的记录上执行。 综上，选择（E）。 具体内容请参考内排序算法以及第八章课件。 6、外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答下列问题。 (1)关于“排序-归并”算法，下列说法不正确的是_____。 (A)“排序-归并”算法是一个两阶段完成排序的算法，第一个阶段称为子集合排序，第二个阶段称为归并排序； (B)“排序-归并”算法是在这样环境下应用的算法：待排序数据元素数目大于或远大于内存中可装入数据元素数目； (C)“排序-归并”算法可以对任意大规模的数据集合进行排序； (D)“排序-归并”算法是通过多次读写磁盘完成大规模数据集合的排序工作的； (E)上述说法有不正确的。 答案：E 解释： 本题考核对“排序-归并”算法的理解。 (A)(B)(C) (D)的叙述都是正确的，所以选择(E)。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (2)参见图示，内存块数为B memory=6，每块可装载R block=5个元素，如果经过一个轮次的归并操作便能完成排序，则关于待排序元素集合的大小，下列说法正确的是_____。 (A)待排序元素数目应>= (B memory-2) * B memory * R block； (B)待排序元素数目应<= (B memory-2) * B memory * R block； (C)待排序元素数目应<= B memory * R block； (D)待排序元素数目应>= B memory * R block； (E)上述说法都不正确。 答案：B 解释： 本题考核对排序-归并算法的理解。 首先，子集合排序时，将B problem块数据划分为N个子集合, 要求每个子集合的块数不超过内存可用块数（B problem）；其次，归并过程中，除了每个子集合中的一块要放到内存中，还要剩余2块，一块用于装载输出数据块，另一块用于存放待比较元素数据块，即子集合数不应该超过(B memory-2) ；所以待排序元素数目应<= (B memory-2) * B memory * R block，(B)正确。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (3)参见图示。如果：内存块数为B memory=6，每块可装载R block=5个元素，待排序元素集合所占用磁盘块数B problem=24，则关于此集合的排序问题，下列说法正确的是_____。 (A)首先将待排序元素集合划分为2个子集合，每个子集合为12块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再一个轮次对这2个已排序子集合进行归并操作，完成最终排序； (B)首先将待排序元素集合划分为4个子集合，每个子集合为6块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这4个已排序子集合进行归并操作，完成最终排序； (C)首先将待排序元素集合划分为6个子集合，每个子集合为4块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这6个已排序子集合进行一个轮次的归并操作，完成最终排序； (D)前述(A)(B)(C)都正确。 答案：B 解释： 本题考核排序-归并算法的子集合划分问题。 首先，子集合排序时，将B problem块数据划分为N个子集合, 要求每个子集合的块数小于内存可用块数，即：B problem/N ≤B memory，(A)不符合这个要求；其次，归并过程中，除了每个子集合中的一块要放到内存中，还要剩余2块，一块用于装载输出数据块，另一块用于 存放待比较元素数据块，(C)中把每个子集合中的元素放入内存中就没有剩余的内存了，所以错误，所以(B)正确。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (4)参见图示。如果：内存块数为B memory=6，每块可装载R block=5个元素，待排序元素集合所占用磁盘块数B problem=24，进行升序排序，此集合已被划分为4个子集合并对每个子集合元素已进行升序排序并写回磁盘，则关于归并问题，下列说法不正确的是_____。 (A)内存共有6块，其使用分配如下：4块内存中的每一块分别用于装载4个子集合中的一块；剩余2块，一块用于装载输出数据块，另一块用于存放待比较元素数据块，该块中的元素分别来自于4个子集合中。 (B)待比较元素数据块中的最小者，被送到输出数据块中；同时，再从其对应的子集合数据块中依次补充进一个元素； (C)当某子集合在内存的数据被处理完时，则再从磁盘上将该子集合的下一块读入到内存中，直到该子集合的所有块都已经被处理完为止； (D)当输出数据块被装满时，则将输出数据块依次写回到磁盘上； (E)上述说法有不正确的。 答案：E 解释： 本题考核排序-归并算法的归并过程。 (A)(B)(C) (D)的叙述都是正确的，所以选择(E)。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (5)参见图示。如果：内存块数为B memory=6，每块可装载R block=5个元素，待排序元素集合所占用磁盘块数B problem=24，采用排序-归并算法进行升序排序，下列说法正确的是_____。 (A)算法以磁盘块读写次数衡量的时间复杂性为1B problem； (B)算法以磁盘块读写次数衡量的时间复杂性为2B problem； (C)算法以磁盘块读写次数衡量的时间复杂性为4B problem； (D)算法以磁盘块读写次数衡量的时间复杂性为8B problem。 答案：C 解释： 本题考核排序-归并算法的时间复杂性。 4个子集合4次内排序---2个B problem；1次4路归并最终完成---2个B problem，最终时间复杂性为4B problem。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (*6)参见图示。如果：内存块数为Bmemory=4，待排序元素集合所占用磁盘块数Bproblem=40，进行升序排序。如果：归并过程中，整体的数据集被从磁盘读入内存，再由内存写回磁盘，被称为一个轮次，则下列说法正确的是_____。 (A)该数据集可以经过1个轮次的2路归并完成最终排序； (B)该数据集可以经过2个轮次的2路归并完成最终排序； (C)该数据集可以经过3个轮次的2路归并完成最终排序； (D)该数据集可以经过多于3个轮次的2路归并完成最终排序； 答案：D 解释： 本题考核排序-归并算法的归并过程。 10个子集合：5次2路归并形成5个集合--1个轮次；2次2路归并形成2个集合+1个集合—1个轮次；1次2路形成1个集合+1个集合--1个轮次；1次2路归并最终完成—1个轮次；所以该数据集可以经过多于3个轮次的2路归并完成最终排序，(D)正确。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (*7)参见图示。如果：内存块数为B memory=4，待排序元素集合所占用磁盘块数B problem=40，进行升序排序。如果：从磁盘装入内存，再从内存写回磁盘，被称为内存利用了一次，则下列说法正确的是_____。 (A)该数据集基于“排序-归并”策略完成最终排序，需要利用内存19次； (B)该数据集基于“排序-归并”策略完成最终排序，需要利用内存9次； (C)该数据集基于“排序-归并”策略完成最终排序，需要利用内存10次； (D)该数据集基于“排序-归并”策略完成最终排序，需要利用内存5次； 答案：A 解释： 本题考核排序-归并算法对内存的利用。 10个子集合进行10次内排序—内存利用10次；5次2路归并形成5个集合—内存利用5次；2次2路归并形成2个集合+1个集合—内存利用2次；1次2路形成1个集合+1个集合—内存利用1次；1次2路归并最终完成—内存利用1次；所以总的内存利用次数是19次。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (*8)参见图示。如果：内存块数为B memory=4，待排序元素集合所占用磁盘块数B problem=40，采用排序-归并算法进行升序排序，下列说法正确的是_____。 (A)算法以磁盘块读写次数衡量的时间复杂性为4B problem； (B)算法以磁盘块读写次数衡量的时间复杂性为8B problem； (C)算法以磁盘块读写次数衡量的时间复杂性为10B problem； (D)算法以磁盘块读写次数衡量的时间复杂性为19B problem。 答案：C 解释： 本题考核排序-归并算法的时间复杂性。 10个子集合10次内排序---2个B problem；5次2路归并形成5个集合---2个B problem；2次2路归并形成2个集合+1个集合---2个B problem；1次2路形成1个集合+1个集合---2个B problem；1次2路归并最终完成---2个B problem，最终时间复杂性为10B problem。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (*9)参见图示。如果：内存块数为B memory=8，待排序元素集合所占用磁盘块数B problem=80，首先，80个磁盘块的待排序元素集合被分成10个子集合，分别进行子集合排序；然后再进行归并处理完成最终排序。关于归并操作，几个子集合同时装入内存进行归并就被称为几路归并，则下列说法不正确的是_____。 (A)对10个已排序子集合可以先进行2个5路归并形成2个子集合，然后再进行1个2路归并便可完成最终的排序； (B)对10个已排序子集合可以先进行3个3路归并形成3个子集合，外加剩余子集合共4个子集合，然后再进行1个4路归并便可完成最终的排序； (C)对10个已排序子集合可以先进行1个5路归并形成1个子集合，外加剩余5个子集合共6个子集合，再进行1个6路归并便可完成最终的排序； (D)前述(A)(B)(C)归并策略都可以，但性能有所不同，最好的是(A)策略。 答案：D 解释： 本题考核对归并策略性能的理解。 (A)(B)(C)的归并策略都可以，但是最好的是(C)策略，因为(C)仅有5个子集合进行了2个轮次的归并，5个子集合进行了一个轮次的归并；(A)所有10个子集合都进行了2个轮次的归并；所以(D)错误。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (*10)已知内存块数为B memory，待排序元素集合所占用磁盘块数B problem，设计一个“排序-归并”算法的基本思路，下列描述不正确的是_____。 (A)首先划分子集合，每个子集合最大可为B memory块，可以划分为B problem/B memory个子集合。这样划分的理由：一是子集合可以全部装载入内存执行内排序，二是最大限度地利用内存产生尽可能少数目的子集合； (B)将B memory块内存留出两块，一块作为输出数据块，一块用于待比较元素数据块。其余B memory-2块用于装载尽可能多数目的子集合，即尽可能采用更多路的归并。这样做的理由：尽可能最大限度地利用内存，以便减少归并的次数； (C)如果子集合参与归并一次被称为一个轮次，则整个数据集的轮次是指该数据集中参与归并次数最多的子集合的轮次。归并算法应考虑以尽可能少轮次的归并为目标来衡量各种不同归并策略的好坏。也可以定义一个参数“子集合轮次累积和”，即所有子集合参与归并轮次的总和，来衡量性能好坏，即“子集合轮次累积和”越小，算法性能越好； (D)假设B memory=6，B problem=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次将10个子集合分成3组(3个、3个和4个)并分别采用3路归并和4路归并将其归并成3个子集合；第二次对这3个集合再采用3路归并完成最终的排序。这样做的算法是最优的。 (E)假设B memory=6，B problem=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次采用4路归并分别对8个子集合、4个一组归并成2个子集合；第二次对这2个集合与剩余的2个子集合一起采用4路归并完成最终的排序。这样做的算法是最优的； 答案：D 解释： 本题考核“排序-归并”算法的设计。 (A)(B)(C)的说法都是正确的，(E)相比(D)而言最优，因为E仅有8个子集合进行了2个轮次的归并，2个子集合进行了一个轮次的归并，而D所有10个子集合都进行了2个轮次的归并。从“子集合轮次累积和”角度(E)比(D)优，所以(D)错误。 具体内容请参考第八章课件之“基本排序算法--外排序算法”。 (11)关于内排序和外排序算法设计的关键点，下列说法不正确的是_____。 (A)外排序算法体现了受限资源环境下的算法构造，这里内存是一种受限资源； (B)外排序算法强调尽可能少地读写磁盘，尽可能充分地利用内存来完成算法构造； (C)外排序算法体现了与内排序算法设计不一样的关注点，前者更关注磁盘读写，后者更关注CPU执行操作的步数； (D)外排序算法因内存环境的变化可以采用不同的策略，而不同策略算法的性能可能有所不同，这体现了问题求解算法的多样性，体现了算法需要“优化”； (E)上述说法有不正确的。 答案：E 解释： 本题考核内排序和外排序的区别。 内排序是指待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据，使用数组或其他数据结构便可进行统一的排序处理的排序问题；外排序是指待排序的数据保存在磁盘上，不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；(A)(B) (C)(D)的叙述都是正确的，所以(E)错误。 具体内容请参考第八章课件。 7、PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答下列问题。 图I. (1)关于PageRank计算网页重要度的基本思想，下列说法正确的是_____。 (A)反向链接数越多的网页越重要----被链接次数越多越重要； (B)反向链接加权和越高的网页越重要----被重要网页链接次数越多越重要； (C)正向链接数越多的网页，其链接的权值越低----正向链接数越多的网页越不重要； (D)上述全部。 答案：D 解释： 本题考查PageRank的基本思想--通俗语义。 一个网页的重要度等于其所有反向链接的加权和，所以反向链接加权和越高的网页越重要，反向链接数越多的网页越重要；一个正向链接的权值等于网页的重要度除以其正向链接数，所以正向链接数越多的网页，其链接的权值越低，所以(A)(B)(C)都正确，选(D)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (2-1)按照PageRank的思想，一个网页的重要度被定义为_____。 (A)其所拥有的所有反向链接的数目； (B)其所拥有的所有正向链接的数目； (C)其所拥有的所有链接的数目； (D)上述都不正确。 答案：D 解释： 本题考查PageRank对网页重要度的定义。 一个网页的重要度等于其所有反向链接的加权和，所以(A)(B)(C)都不正确，选(D)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (2-2)按照PageRank的思想，一个网页的重要度被定义为_____。 (A)其所拥有的所有反向链接的数目； (B)其所拥有的所有反向链接的加权和； (C)其所拥有的所有正向链接的数目； (D)其所拥有的所有正向链接的加权和；。 答案：B 解释： 本题考查PageRank对网页重要度的定义。 一个网页的重要度等于其所有反向链接的加权和，所以(B)正确。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (3)按照PageRank的思想，一个网页链接的权值被定义为_____。 (A)网页重要度除以该网页所拥有的正向链接数； (B)网页重要度除以该网页所拥有的反向链接数； (C)网页重要度除以该网页所拥有的所有链接数； (D)上述都不正确；。 答案：A 解释： 本题考查PageRank对链接权值的定义。 一个网页链接的权值等于网页的重要度除以其正向链接数，所以(A)正确。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (4)PageRank将网页的链接关系，抽象为一个n n的矩阵A：网页被从1到n进行编号；如果网页i有一个指向网页j的链接，则矩阵的a ij元素(即第i行第j列元素)值为1，否则矩阵a ij元素值为0。然后将A做一个转置处理(即矩阵的行列互换)，形成转置矩阵A T，为什么要转置，原因是_____。 (A)有利于体现反向链接的重要性； (B)有利于更好地区分反向链接与正向链接； (C)有利于计算权值矩阵(可被称为转移概率矩阵M)：将A T的一列中的各行除以该列中1的个数，即可形成权值矩阵M； (D)有利于由A T计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和。 答案：D 解释： 本题考查PageRank对网页链接关系的抽象--邻接矩阵及其转置的理解。 将A转置的原因是有利于由A T计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和，选(D)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (5)PageRank算法中出现了一个“转移概率矩阵”，参见下图，其意义是_____。 (A)转移概率矩阵是基于网页链接关系矩阵A T计算得到的，按列来看是，网页j有多少个正向链接，其权值为多少分之一，反映了链接权值的计算方法； (B)转移概率矩阵是基于网页链接关系矩阵A T计算得到的，按行来看是，网页i有多少 个反向链接及其权值，可反映网页i的重要度计算方法即：，由其他网页的重要度及其权值计算该网页i的重要度； (C)网页i的重要度R i可以迭代地计算得到，设第m次得到的R i记为R i(m)，称为网页重要度R i的一个状态，则状态转移概率为R i由一个状态转变为另一个状态的概率； (D)状态转移概率可广泛用于计算客观事物呈现状态序列S(0),...., S(m-1),S(m),...，而S(m)的计算仅由S(m-1)的值来确定的情况； (E)上述说法都正确。 答案：E 解释： 本题考查PageRank对转移概率矩阵的理解。 (A)(B)(C) (D)的叙述都正确，所以选(E)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (6)前述说过PageRank网页i重要度R i可以通过迭代地计算得到，即由m-1状态下各个网页的重要度R(m-1)，依转移概率矩阵计算m状态下网页重要度R(m)，参见下图。 关于网页重要度的计算过程，下列说法正确的是_____。 (A)在得到了转移概率矩阵M后，任意给出网页重要度的一组值，记为R(0)，是一向量，参见下图，继续进行(B)； (B)不断地计算R(m)=M?R(m-1)，m从0开始，为迭代次数。当R(m) = R(m-1)时，迭代计算终止，此时的向量R即为所求的各个网页的重要度； (C)选项(A)(B)是将状态序列R(0)，...，R(m-1)，R(m)，...不断迭代产生后趋于稳定的，或者说收敛的R(m)，作为最终的R，即是已知M情况下，求方程R = MR的解； (D)上述说法都正确。 答案：D 解释： 本题考查PageRank对迭代法计算的理解。 网页重要度的计算过程正如(A)(B)所示，(C)是对(A)(B)的一个总结，都是正确的，所以选(D)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (7)前述说过PageRank，通过不断地计算R(m)=M?R(m-1)来计算网页重要度，即由第(m-1)次的网页重要度来计算第(m)次的网页重要度，那么网页重要度的初始值R(0)应如何获得呢? 下列说法正确的是_____。 (A)随机产生各网页重要度的一组值，该组值对最终计算结果没有影响； (B)由专家给出各网页重要度的一组值，该组值的质量好坏直接影响计算结果； (C)设定各网页重要度都是1； (D)随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响。 概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 算法的实现： 1.void print(int a[], int n ,int i){ 2. cout< 13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。 小于的话，移动有序表后插入 14.int j= i-1; 15.int x = a[i]; //复制为哨兵，即存储待排序元素 16. a[i] = a[i-1]; //先后移一个元素 17.while(x < a[j]){ //查找在有序表的插入位置 18. a[j+1] = a[j]; 19. j--; //元素后移 20. } 21. a[j+1] = x; //插入到正确位置 22. } 23. print(a,n,i); //打印每趟排序的结果 24. } 25. 26.} 27. 28.int main(){ 29.int a[8] = {3,1,5,7,2,4,9,6}; 30. InsertSort(a,8); 31. print(a,8,8); 32.} 效率： 时间复杂度：O（n^2）. 其他的插入排序有二分插入排序，2-路插入排序。 2. 插入排序—希尔排序（Shell`s Sort） 希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序 基本思想： 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序” 时，再对全体记录进行依次直接插入排序。 五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词：冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1]，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2，3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想 冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至ｎ-1个记录和第ｎ个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过ｎ-1次比较,不需要移动关键字,即时间复杂度为Ｏ(ｎ)(即正序);在最坏情况下是初始序列为逆序,则需要进行ｎ-1次排序,需进行ｎ(ｎ-1)/2次比较,因此在最坏情况下时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是ｎ个记录的文件的直接排序可经过ｎ-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(ｎ-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为ｎ(ｎ-1)/2,时间 陕西科技大学实验报告 班级学号姓名实验组别 实验日期室温报告日期成绩 报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：查找与排序算法的实现和应用 实验目的： 1. 掌握顺序表中查找的实现及监视哨的作用。 2. 掌握折半查找所需的条件、折半查找的过程和实现方法。 3. 掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。 4. 掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方 法。 5. 掌握直接插入排序、希尔排序、快速排序算法的实现。 实验环境（硬/软件要求）：Windows 2000,Visual C++ 6.0 实验内容： 通过具体算法程序，进一步加深对各种查找算法的掌握，以及对实际应用中问题解决方 法的掌握。各查找算法的输入序列为：26 5 37 1 61 11 59 15 48 19输出 要求：查找关键字37,给出查找结果。对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。 各排序算法输入的无序序列为：26 5 37 1 61 11 59 15 48 19。 实验要求： 一、查找法 1. 顺序查找 首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序 表中进行查找。 2. 折半查找 任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后再改有序表上 使用折半查找算法进对给定值key 的查找。 3. 二叉树查找 任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一 定k的查找过程。 4. 哈希表查找 任意输入一组数值作为个元素的键值，哈希函数为Hash （key ）=key%11, 用线性探测再散列法解决冲突问题。 二、排序算法 编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。 实验原理： 1. 顺序查找： 在一个已知无（或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以 《软件工程》社会实践 分布式系统中排序算法以及应用案例设计报告 学号： 2014107326 姓名：侯明兰 一.算法需求分析 1. 分布式排序算法的排序过程为：在p台已经赋予序号的计算机C1，C2，……，Cp上，对一组给定的数据分布X={X1，X2，……，Xp}进行全局排序，得到一个新的数据分布Y={Y1，Y2，……，Yp}，使得每个Yi(1≤i≤p)有序，并且Yi的每个元素不大于Yj的任何元素，i ≤j。分布式排序必须完成的最小工作是： 1.1 数据传输：把一些效据从它们所在的机器送到它们应放的机器； 1.2 局部排序； 1.3 预处理，以便能正确地把数据重新分布。 因此，根据预处理分类，一个分布式系统中的排序算法有四类操作： 1.3.1 局部排序； 1..3.2 合并； 1.3.3 预处理； 1.3.4 数据交换。 2.算法的分类：根据算法的分析可以分为：单节点排序（序(Single Node Sort，SNS）、多节点归并排序（(Multiple Node Merge Sort，MNMS）和多节点分区排序（(Multiple Partition Sort，MPS）。 2.1 单节点排序（SNS）：假设数据存储在多个节点中，但是负责计算的节点之间没有并行计算的能力，只有当前被连接的节点能够提供计算并对对客户端提供服务．在这样的场景下对进行数据排序，流程的主要是，各节点将数据读入内存，并通过网络传输至排序的节点，在该节点上进行排序。 2.2 多节点归并排序：当存储数据的节点同时也拥有计算能力的时候，可以采用算法是：各节点先对存储在本地的数据进行排序，待所有的存储节点都对本地的数据排好序之后，再传送至某一个处理节点进行归并排序。 第8章怎样研究算法:排序算法示例 1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。 (A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多； (B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多； (C)对无序数据集合，两个算法X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢； (D)上述说法有不正确的； 答案：C 解释： 本题考核排序算法的研究 在大规模数据集合中查找，有序数据集合有利算法进行和判断，要比无序数据集合查找的快，对于（C）选项，Y算法尽管需要排序后再处理，但排序处理后的数据查找更加快捷，因此可能Y算法比X算法更快。 具体内容请参考排序算法以及第八章课件。 2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 【算法A1】 Start of algorithm A1 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。 End of algorithm A1 【算法A2】 Start of algorithm A2 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。 Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。 Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。 End of algorithm A2 【算法A3】 Start of algorithm A3 Step 1. 假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n； Step 2. 计算中间记录位置I = (Start+Finish)/2，读取第I条记录。 Step 3. 判断第I条记录的成绩与给定查找分数： (3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2； (3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2； (3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。 End of algorithm A3 针对上述三个算法，回答下列问题： (1)关于算法A1, A2, A3的快慢问题，下列说法正确的是_____。 (A)算法A1快于算法A2，算法A2快于算法A3； (B)算法A2快于算法A1，算法A2快于算法A3； (C)算法A3快于算法A2，算法A2快于算法A1； (D)算法A1快于算法A3，算法A3快于算法A2； (E)上述都不正确。 答案：C 解释： 本题考核排序算法的研究 首先，数据是有序排列的，从大到小。 算法A1依次搜索，穷举。 算法A2与A1一样，穷举，不同的是它利用数据是从大到小排序的特点，因此，如果当前数据比如果小于目标数，那么说明只有的也一定小于，则目标不在序列中。因此，A2比A1快。 算法A3利用数据有序特点，采用二分查找，每次将目标数与中间值比较，缩小搜索范围，因此A3比A2快。 综上，答案选（C）。 具体内容请参考排序算法以及第八章课件。 第8章怎样研究算法排序算法示例练习题答案解析． 第8章怎样研究算法:排序算法示例 1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。(A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多； (B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多； (C)对无序数据集合，两个算法 X和Y：X 采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢；(D)上述说法有不正确的； 答案：C 解释： 本题考核排序算法的研究有序数据集合有 利在大规模数据集合中查找，算法进行和判断，要比无序数据集合查找的快， 算法尽管需要排序后再处理，选项，Y对于（C）Y但排序处理后的数据查找更加快捷，因此可能 X算法更快。算法比具体内容请参考排序算法以及第八章课件。、下列三个算法是关于“大规模数据集合中查2“学生”针对一个找有无某些元素”问题的算法：数据表，如下示意，找出“成绩”为某一分数的所有学生。学生 学 12030095 07 1203001李94 03 宁 1203001李88 01 鹏 85 徐120300106 月． 1203001王79 02 刚 1203001江77 09 12030073 10 12030069 0412030066 0544 12030008 A1】【算法Start of algorithm A1 条记录开始，直到其最Step 从数据表的第 《高级语言程序设计》 课程设计报告 题目： 排序算法 专业： 班级： 姓名： 指导教师： 成绩： 计算机与信息工程系 2015年3月26日 2014-2015学年 第2学期 目录 引言 (1) 需求分析 (1) 第一章程序内容及要求 (1) 1.1 冒泡排序 (1) 1.2 选择排序 (2) 1.3 插入排序 (3) 第二章概要设计 (4) 2.1冒泡排序 (4) 2.2选择排序 (5) 2.3插入排序 (6) 第三章程序的比较及其应用 (7) 3.1时间复杂度 (7) 3.2空间复杂度 (7) 3.3稳定程度 (7) 3.4应用及其改进 (8) 第四章程序设计结果 (8) 附录 (9) 参考文献 (12) 引言 伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。 经常查找资料的朋友都会知道，面对海量的资料，如果其查找资料没有进行排序，那么其查找资料将会是一家非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。 理论上排序算法有很多种，不过本课程设计只涉及到三种算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。 本课程设计通过对这三种算法的运行情况进行对比，选择最优秀的算法出来。希望通过我的努力能解决一些问题，带来一些方便。 需求分析 本课程题目是排序算法的实现，由于各方面的原因，本科程设计一共需要设计三种排序算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。三种排序算法各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。 由于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可能会报错。 本课程软件运行的的操作系统为Windows7 64位操作系统。所使用的软件为Microsoft Visual C++6.0以及Turbo C2.0 第一章程序内容及要求 1.1 冒泡排序 冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。 排序算法总结及习题 一、概述 排序是最基础和常用的算法之一，一般情况下，排序不开比较、数据交换，怎样降低算法的时间及空间复杂性是算法设计的目标，尽管经典算法已有不少，但研究一直不断，2001年还有综合性能很好的新算法出现。 为了对n个元素的线性表进行排序，至少必须扫描一遍以获取n各元素，因此排序问题的计算复杂性下界为： Ω(n) 如果对输入的数据不做任何要求，则仅能通过比较来确定输入序列 则任意分布数据，算法复杂性下界：Ω(nlogn) 二、常用基本算法及思想 名次排序、冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。 1.名次排序 （1）计算名次 void Rank(T a[], int n, int r[]) { //计算a [0:n-1]中n个元素的排名 for (int i = 0; i < n; i++) r[i] = 0; //初始化 //逐对比较所有的元素 for (int i = 1; i < n; i++) for ( int j = 0; j < i; j++) if (a [j] <= a[ i]) r[i]++; else r[j ]++; } （2）按名次排序 void Rearrange (T a[], int n, int r[]) { //按序重排数组a中的元素，使用附加数组u T *u = new T[n+1]; //在u中移动到正确的位置 for (int i = 0; i < n; i++) 常用算法的应用 1．递推算法（常用级数、数列求和、二分法、梯形积分法、穷举法等）； 2．排序算法（选择法、冒泡法）； 3．查找算法（顺序查找、折半查找）； 4．有序数列的插入、删除操作； 5．初等数论问题求解的有关算法（最大数、最小数、最大公约数、最小公倍数、素数等）；6．矩阵的处理（生成、交换及基本运算）； 7．递归算法（阶乘、最大公约数等）； 8．字符串处理（插入、删除、连接和比较等） 1.相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值. 比如阶乘函数：f(n)=n*f(n-1) 在f(3)的运算过程中,递归的数据流动过程如下: f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6} 而递推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础 的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意. 2.所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为： 计算的复杂度（最差、平均、和最好表现），依据串列（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。 记忆体使用量（以及其他电脑资源的使用） 稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。 一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。 当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有： (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的 八大排序算法 概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 算法的实现： [cpp]view plain copy print? 1.void print(int a[], int n ,int i){ 2. cout< 8. 9. 10.void InsertSort(int a[], int n) 11.{ 12.for(int i= 1; i C语言教学中关于排序算法的应用与分析 庄前进 摘要：算法是计算机语言教学中的重要因素，是分析问题的钥匙、程序设计的思想，离开算法就谈不上程序设计。本文阐述了排序算法在复杂问题中的应用、解决思路及相应的C语言程序。 引言 排序算法虽然在C语言教学中经常用到，但是当学生遇到有难度的问题时却难以解决，无从下手。为了帮助学生提高问题分析能力以及巩固知识，下面通过两个复杂问题的分析，让学生掌握科学的学习方法和思维，写出正确的程序。 1、排序算法 常用的排序算法有四种，分别是顺序比较法、冒泡法、插入法及选择法，各有各的特点，如果没有特别说明，用顺序比较法较为简单。 2、排序算法的应用 学习程序如果仅仅是局限于排序就没有意义了，有时要涉及有难度和深度的问题。下面通过两道考题帮助我们加深对排序的了解。 2．1有20个在10—99（含10和99）之间互不相同的整数11，21，22，32，23，43，34，44，56，65，77，57，82，27，95，48，68，64，90，81，按个位数作升序排序，个位数相同时再按十位数作降序排列，将排序结果输出。 分析：程序应由下面几个部分组成：定义变量和数组，数组元素的赋值，数组元素的处理—排序，数组元素的输出。在排序程序段，应将数组元素分解为个位数及十位数，这是本题重要算法之一。 程序清单 #define N 20 main() { int i,j,x,y,m,n,k; int a[N]={11,21,22,32,23,43,34,44,56,65,77,57,82,27,95,48,68,64,90,81}; for(i=0;i<=N-2;i++) for(j=i+1;j<=N-1;j++) { x=a[i]% 10;m=a[i]/10; y=a[j]% 10;m=a[j]/10; if(x>y) {k=a[i];a[i]=a[j];a[j]=k;} if(x==y) {k=a[i];a[i]=a[j];a[j]=k;} } printf("\n the sorted numbers are:\n"); for(i=0;i<=N-1;i++) printf("%4d",a[i]); } 2．2下列程序列用数据96，123，78，14，37实现对MxN矩阵a的赋值，要求将给定的数据依次赋给数组b，然后用冒泡法按列自上而下进行升序排列。 例：5 X 6 矩阵的赋值结果排序结果 96 123 78 14 37 96 14 14 14 14 14 123 78 14 37 96 123 37 37 37 37 37 78 14 37 96 123 78 78 78 78 78 78 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 1. 插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 算法的实现： 效率： 时间复杂度：O（n^2）. 其他的插入排序有二分插入排序，2-路插入排序。 2. 插入排序—希尔排序（Shell`s Sort） 希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序 基本思想： 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 操作方法： 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 2.按增量序列个数k，对序列进行k 趟排序； 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列， 分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 希尔排序的示例： 需 求 分 析 报 告 课程设计题目：排序算法实现与演示系统专业：计算机科学与技术 班级： 姓名： 一．问题的提出 1.1编写目的 排序在人们的日常生活和学习、科研、生产等各个方面有着重要的应用。因此掌握常用的排序算法是很必要的。此次设计拟开发一个排序算法演示系统，以提高对排序算法的掌握程度。 本系统实现各种内部排序：直接插入排序、冒泡排序、直接选择排序、希尔排序、快速排序、堆排序、归并排序演。用户可以选择排序算法以演示输入数据在该排序算法下的排序过程。 1.2项目背景 课程设计题目：排序算法实现与演示系统 本课题的指导老师： 本课题的任务开发者： 该设计系统与其他系统的关系：相辅相成，紧密相关 1.3定义 文档中所用到的专业术语： 1.4参考资料 [1] 李云清，杨庆红.数据结构（C语言版）.北京：人民邮电出版社，2004. [2]严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版.1997. [3] 苏光奎,李春葆.数据结构导学.北京:清华大学出版.2002. [4] 周海英，马巧梅，靳雁霞.数据结构与算法设计.北京：国防工业出版社，2007. [5] 张海藩. 软件工程导论. 北京：清华大学出版社.2003. 随着计算机的普及，数据结构的应用与开发也深入我们的生活学习当中，其中排序算法也影响极深，通过这次排序算法的实现，希望更多人可以学会并运用排序算法。 二．任务概述 2.1目标 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2.2运行环境 Microsoft Visual C++ 2008 2.3用户的特点 排序算法实现与演示系统使用者：具有一定的计算机操作能力和知识。 系统调用人员：具有很高的专业知识水平，理解排序算法实现与演示系统的运行机制，可以对开放代码进行阅读和分析，以完成其系统独特的需求。 2.4条件与限制 课程设计代码编写测试时间短、技术力量弱，设备具有约束性。 三．数据描述 9种经典排序算法的可视化 最近在某网站上看到一个视频，是关于排序算法的可视化的，看着挺有意思的，也特别喜感。 不知道作者是怎么做的，但是突然很想自己实现一遍，而且用python实现特别快，花了一天的时间，完成了这个项目。主要包括希尔排序（Shell Sort）、选择排序（Selection Sort）、快速排序（Quick Sort）、归并排序（Merge Sort）等九种排序。 附上源码链接： https://github/ZQPei/Sorting_Visualization （觉得不错，记得帮忙点个star哦） 下面具体讲解以下实现的思路，大概需要解决的问题如下： 如何表示数组 如何得到随机采样数组，数组有无重复数据 如何实现排序算法 如何把数组可视化出来 一、如何表示数组 Python提供了list类型，很方便可以表示C++++中的数组。标准安装的Python中用列表(list)保存一组值，可以用来当作数组使用，不过由于列表的元素可以是任何对象，因此列表中所保存的是对象的指针。这样为了保存一个简单的[1,2,3]，需要有3个指针和三个整数对象。对于数值运算来说这种结构显然比较浪费内存和CPU计算时间，再次就不详细论述。 二、如何得到随机采样数组，数组有无重复数据 假设我希望数组长度是100，而且我希望数组的大小也是在[0,100)内，那么如何得到100个随机的整数呢？可以用random库。 示例代码： import randomdata = list(range(100))data = random.choices(data, k=100)print(data)[52, 33, 45, 33, 48, 25, 68, 28, 78, 23, 78, 35, 24, 44, 69, 88, 66, 29, 82, 77, 84, 12, 19, 10, 27, 24, 57, 42, 71, 75, 25, 1, 77, 94, 44, 81, 86, 62, 25, 69, 97, 86, 56, 47, 31, 51, 40, 21, 41, 21, 17, 56, 88, 41, 92, 这是用C语言写好的5种最常用的排序算法： 1：冒泡排序2：交换排序3：选择排序4：插入排序5：快速排序 这5种算法都经过VC6.0测试，可以正确运行 其中带有一个洗牌函数，主要是为了打乱数组数据，方便测试排序函数。这5种算法都参考了其它书籍，在效率上很不错。 #include #include } A[j] = temp; } } template 2019年第3期 信息通信2019 (总第 195 期）INFORMATION&COMMUNICATIONS(Sum.N o 195) 浅析基于c语言的常用排序算法比较 王锦坤 (中国地质大学，湖北武汉430070) 摘要:作为计算机程序设计的重要操作，排序算法的优劣直接影响程序运行效率，因此文章开展了基于C语言的常用排 序算法比较，明确了排序算法的基本选择思路，并结合实例深入探讨了基于C语言的排序算法应用，希望能够为相关业 内人士带来一定启发。 关键词:C语言;选择排序;插入排序;起泡排序 中图分类号:TP301.6 文献标识码:A文章编号：1673-1131(2019)03-0083-03 在数据处理领域，排序算法属于较为常用的一种非数值 算法，该算法在计算机信息处理、数据分析、数据库操作等领 域能够发挥重要作用。基于C语言的排序算法一般分为7种，即归并排序、基数排序、堆排序、快速排序、选择排序、起泡排 序、插入排序，本文研究主要围绕选择排序、插入排序、起泡排直至所有数据选择完毕属于选择排序的基本方法，用语言描 述便是首先找到最小或最大项，并将其与其他项分开，以此完 成排序。但在基于C语言的选择排序算法应用中，该算法不 会考虑原序列的初始排序情况，哪怕原有数据已经完成从小 到大或从大到小排列，应用选择排序算法的程序也必须执行 序三种常见排序算法展开。 1基于C语言的常用排序算法比较 本节主要介绍了三种基于C语言的常用排序算法，分别 为选择排序算法、插入排序算法、起泡排序算法，并结合三种 算法的不足，提出了改进型算法且进行了简单对比。 1.1选择排序算法 次比较，这种情况下算法的应用复杂度为o(n2),而如果原序列元素较为庞大，选择排序算法的应用势必会因系统资源的较多占用造成不必要浪费。 为弥补选择排序算法的不足，树形选择排序算法应运而 生，这类基于C语言的选择排序算法能够将数据元素两两比 对，大者上升，上升元素再次进行两两比对，由此不断开展循 持续从待排序数据元素选择最小(最大)元素构成新序列， 表1隐藏前后的相似度计算结果 相似度 F.wav 歌曲1的P.w av0.99956 歌曲2的P.w av0.99973 歌曲3的P.w av0.99990 歌曲4的P.w av0.99943 歌曲5的P.w av0.99902 歌曲6的P w av0.99935 歌曲7的P.w av0.99909 歌曲8的P.w av0.99978 歌曲9的P.w av0.99940 歌曲10的P.w av0.99972 为了测试软件的隐藏和解除隐藏功能的可靠性，分别采 用30个不同的歌曲、诗朗诵、黄梅戏和京剧来隐藏不同的声 音。隐藏和解除隐藏的正确率的测试结果见表2。 表2载体不同、隐蔽话音不同时隐藏和解除隐藏正确率載体类型蔽话在为與卢的成功串隐薮话音为女声的成功串 歌曲丨〇首100%100% 英文朗读丨0首100%100% 10首黄梅戏和京剧100*/.100% 3结语 虽然我们鼓励面对面的交流，对于性格外向的同学而言，向别人道歉也许不是一件难事。但对性格内向(或偏内向)或 惧怕对方不接受道歉、担心丢面子的同学而言,如果能够消除 他们在道歉时的心理障碍，将有助于恢复同学友谊，及时化解 矛盾，构建更加和谐的校园环境。 目前国内大学和重点中学对心理疏导也非常重视，组建了专业教师队伍，而帮助化解同学间的矛盾也是学校心理疏 导的一项重要内容。 本文的研究构建了话音隐藏技术的一个新的应用，研发 了一个有助于缓解同学道歉时由于性格内向、羞涩或担心对 方不接受道歉所产生的心理障碍的应用软件，为有类似问题 困扰的同学提供了一个可供选择的方式，有助于构建和谐友 爱的同学关系和文明校园的建设。 参考文献： [1]林森浩_百度百科，[EB/OL].(2015-12-15)[2018-12-10].https:/ /https://www.doczj.com/doc/23259201.html,/item/%E6%9E%97%E6%A3%AE%E6% B5%A9/1090736lfi=aladdin. [2]马加爵 _百度百科,[EB/O L].(2004-6-18)[2018-12-10]. https://https://www.doczj.com/doc/23259201.html,/item/%E9%A9%AC%E5%8A%A0% E7°/〇88%B5/154174fr=aladdin. [3]柏森,胡中豫，等，通信信息隐匿技术[M].国防工业出版社， 2005. [4]李旭杰，杨成胡,赵鸿燕，话音通信中的数据自适应隐藏算 法[J],电路与系统学报,2007,12(2):52-55. [5]唐步天，郭立,刘振华.利用M F C C的语音信息隐藏方法[J]. 中国科学院研究生院学报,2008,25(3):386-394. [6]黄永峰，李松斌，网络隐蔽通信及其检测技术[M].清华大 学出版社,2016. [7]刘浩，韩晶.MATLAB R2014a完全自学一本通[M].电子工 业出版社,2015年. 作者简介:高雅云(2002-),女，四川成都人，主要研究方向:信 息技术。 838大排序算法
五种排序算法的分析与比较
实验8查找与排序算法的实现和应用
分布式系统中排序算法及应用案例
第8章怎样研究算法排序算法示例练习题答案解析
第8章怎样研究算法排序算法示例练习题答案解析
c语言程序设计(排序算法)
排序算法总结及习题
常用算法的应用
八大排序算法
C语言教学中关于排序算法的应用与分析
c++排序算法
排序算法的实现与演示需求分析报告
9种经典排序算法的可视化
常用的排序算法
内排序算法时间计算
浅析基于C语言的常用排序算法比较
相关主题
文本预览