目录

一、选择题

二、填空题

三、函数题 

6-1 折半插入排序

6-2 冒泡排序

6-3 快速排序

一、选择题

1、下列排序算法中，▁▁B▁▁ 是稳定的。

A.简单选择排序

B.冒泡排序

C.希尔排序

D.快速排序

稳定：冒泡排序、归并排序、基数排序

不稳定：选择排序、希尔排序、快速排序、堆排序

2、有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为

（ C ）

A.-1，4，8，9，20，7，15，7

B.-1，7，15，7，4，8，20，9

C.-1，4，7，8，20，15，7，9

D.A，B，C均不对

堆排序概念：完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值

 3、对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数最多为( D )。

A.n+1

B.n

C.n-1

D.n(n-1)/2

比较次数最多时元素是逆序的，需要n-1趟排序
第一趟，比较n-1次，确定第n个据元素
第二趟，比较n-2次，确定第n-1个数据元素
第三趟，比较n-3次，确定第n-2个数据元素
......
第n-1趟，比较1次，确定第1、2个数据元素
总的比较次数=(n-1)+(n-2)+......+1= n(n-1)/2 

4、对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是( B ) 

A.O(n)

B.O(n^2)

C.O(nlog2(n))

D.O(n^3)

快排：最优 O(nlogn) 最坏 O(n^2)

5、

6、对同一待排序序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是_D__。

A.排序的总趟数

B.元素的移动次数

C.使用辅助空间的数量

D.元素之间的比较次数

排序的总趟数取决于元素个数n，都是n-1趟。 元素的移动次数都取决于初始序列，两者相同。 使用辅助空间的数量也都是一样的。 折半插入不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。 所以，很明显比较的次数减少了。

7、按排序过程中依据的原则分类，快速排序属于( C )

A.插入类的排序方法

B.选择类的排序方法

C.交换类的排序方法

D.归并类的排序方法

8、数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( D )算法最节省时间。

A.冒泡排序

B.快速排序

C.简单选择排序

D.堆排序

大顶堆、小顶堆 

 二、填空题

给定一组整数，请写出经过一趟排序后的结果：

{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 }

1、直接插入排序

{ 25, 47, 87, 36, 90, 18, 65, 31, 79, 58 }

2、冒泡排序

最大元素沉底，最大元素之前两两交换排序

{ 25, 47, 36, 87, 18, 65, 31, 79, 58, 90 }

3、选择排序

选该序列里最小的值，与其交换位置

{ 18, 25, 87, 36, 90, 47, 65, 31, 79, 58 }

三、函数题 

6-1 折半插入排序

PTA | 程序设计类实验辅助教学平台

void BInsertSort(SqList &L)
{
    int i,j,low,high,mid;
    for(i=2;iL.r[0].key) high=mid-1;
            else low=mid+1;
        }
        for(j=i-1;j>=high+1;j--) L.r[j+1]=L.r[j];
        L.r[high+1]=L.r[0];
    }
}

6-2 冒泡排序

PTA | 程序设计类实验辅助教学平台

void BubbleSort(List L)
{
    for(int i=0;iLast;i++)
    {
        int flag=0;
        for(int j=0;jLast-i;j++)
            if(L->Data[j]>L->Data[j+1])
            {
                int t=L->Data[j];
                L->Data[j]=L->Data[j+1];
                L->Data[j+1]=t;
                flag=1;
            }
        if(!flag) break;
    }
}

6-3 快速排序

PTA | 程序设计类实验辅助教学平台

void quicksort(List L,int Left,int Right)
{
    if(Left>=Right) return;
    
    int x=L->Data[Left],i=Left-1,j=Right+1;
    
    while(iData[++i]Data[--j]>x);
        
        if(iData[i];
            L->Data[i]=L->Data[j];
            L->Data[j]=t;
        }
    }
    quicksort(L,Left,j);
    quicksort(L,j+1,Right);
}