免费智能真题库 > 历年试卷 > 程序员 > 2015年上半年 程序员 上午试卷 综合知识
  第43题      
  知识点:   冒泡排序   排序算法   排序
  关键词:   冒泡排序   排序        章/节:   常用算法       

 
序列(43)可能是第一趟冒泡排序后的结果。
 
 
  A.  40 10 20 30 70 50 60
 
  B.  20 30 10 40 70 50 60
 
  C.  30 10 40 20 70 60 50
 
  D.  20 30 10 40 60 50 70
 
 
 

 
  第35题    2017年上半年  
   54%
采用()算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。
  第43题    2010年下半年  
   51%
排序和快速排序方法中,能在第一趟排序结束后就得到最大(或最小)元素的排序方法是(43)。
  第43题    2013年下半年  
   29%
在第一趟排序之后,一定能把数据序列中最大或最小元素放在其最终位置上的排序方法是(43)。
   知识点讲解    
   · 冒泡排序    · 排序算法    · 排序
 
       冒泡排序
        若设R[1…n]为待排序的n个记录,且假设为从上至下纵向排列,则要求将n个给定记录由小到大排序的冒泡排序(Bubble Sort)的基本思路如下。
        (1)对当前还未排好序的、指定范围内的全部结点,自上而下对相邻的两个结点依次进行比较和调整,让关键字较大的结点往下沉,关键字较小的结点往上冒。即若R[j].key>R[j+1].keg,则将R[j].key与R[j+1].key交换。
        (2)初始化时,排序范围是R[1…n],以后的排序范围由前一遍的扫描结果确定:当自上而下将当前排序范围内的结点执行一遍比较之后,若最后往下沉的结点是R[j],R[j]下沉到R[j+1]的位置,R[j+1]以下的结点比较后会发现它们都不再需要交换。因此,下一趟的排列范围可以缩减为从R[1]到R[j]。
        (3)整个排列过程最多执行n-1趟。若某一趟的比较没有结点交换,所有相邻结点的排列顺序都与排序要求一致,则线性表为有序的。
        顺序线性存储结构下的冒泡排序算法如下:
        
        可见,对n个结点的线性表采用冒泡排序,外循环最多执行n-1趟,每一趟最多执行n-1次比较;第2趟最多执行n-2次比较;依次类推,第n-1趟最多执行1次比较。因此,整个排序过程最多执行n(n-1)/2次比较。由于关键字相等的结点不交换,所以冒泡排序算法是稳定的。
 
       排序算法
               简单排序
               简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
               1)直接插入排序
               直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
               2)冒泡排序
               首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即 r[1].key>r[2].key),则交换两个记录,接着比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序,使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时,所有记录都已有序排列。
               3)简单选择排序
               简单选择排序的基本思想是:在进行每趟排序时,从无序的记录中选择出关键字最小(或最大)的记录,将其插入到有序序列(初始时为空)的尾部。
               希尔排序
               希尔排序又称"缩小增量排序",是对直接插入排序方法的改进。希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
               快速排序
               快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,使得整个序列有序。
               堆排序
               1)堆的概念
               对于n个元素的关键字序列{k1,k2,…,kn},当且仅当所有关键字都满足下列关系时称其为堆:
               
               从序列元素间的关系来看,堆是一棵完全二叉树的层次序列。显然,堆顶元素为序列中n个元素的最小值(或最大值)。若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
               2)堆排序的基本思想(小根堆)
               对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字,然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
               归并排序
               归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序,它是将整个序列中的元素进行分组,相邻的两个元素为一组,然后分别为每个小组进行排序,随后将两个相邻的小组合成一个组,继续进行组内排序;直到所有元素被合并成一个组内,并使组内元素有序,此时排序结束。
               基数排序
               基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。基数排序把一个关键字Ki看成一个d元组,即
               
               其中称为最高有效位,@称为最低有效位。基数排序可以从最高有效位开始,也可以从最低有效位开始。
               基数排序的基本思想是:设立r个队列(r为基数),队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中的关键字再依次收集起来;接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高位有效。这样得到了一个从小到大有序的关键字序列。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
   题号导航      2015年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第43题    在手机中做本题