【数据结构】——排序算法的相关习题

目录

• 一、选择题
• • 题型一 （插入排序）
  • • 1、直接插入排序
    • 2、折半插入排序
    • 3、希尔排序
    • 题型二（交换排序）
    • • 1、冒泡排序
      • 2、快速排序
      • 题型三（选择排序）
      • • 1、简单选择排序
        • 2、堆排序
        • 题型四（归并排序）
        • 题型五（基数排序）
        • 二、应用题
        • • 题型一（插入排序）
          • 题型二（折半插入排序）
          • 题型三（希尔排序）
          • 题型四（冒泡排序）
          • 题型五（快速排序）
          • 题型六（简单选择排序）
          • 题型七（堆排序）
          • 题型八（归并排序）
          • 题型九（基���排序）

            一、选择题

            题型一 （插入排序）

            1、直接插入排序

            1、对n个元素进行直接插入排序，需要进行（）趟处理。

            A、n

            B、n+1

            C、n-1

            D、2n

            解析：（C）

            直接插入排序是将要排序的序列按照关键字的大小插入至已排好序的子序列中，一直进行直到整个序列有序，所以对n个元素进行直接插入排序，一共插入元素n-1次，需要进行n-1趟。

            2、对5个不同的数据元素进行直接插入排序，则最多需要进行的比较次数为（）。

            A、8

            B、10

            C、15

            D、25

            解析：（B）

            考虑最坏情况下为最多需要进行的比较次数，即序列元素呈逆序排列时最多，由于此时从前到后依次需要比较1次、2次、3次、……、n-1次，所以n(n-1)/2=(5×4)/2=10。

            3、对n个元素进行直接插入排序，最好情况下的时间复杂度为（），最坏情况下的时间复杂度为（）。

            A、O(n)，O(n2)

            B、O(n2)，O(n)

            C、O(n)，O(n)

            D、O(n2)，O(n2)

            解析：（A）

            最好情况下，即序列元素都有序，此时只需比较元素而不需移动元素，比较次数为n-1次，故最好时间复杂度为O(n)；而最坏情况下，即序列元素呈逆序排列时，此时比较次数和移动次数都到达最大值，均为n(n-1)/2，故最坏时间复杂度为O(n2)；考虑平均情况，总的比较次数和移动次数约为n2/4，故直接插入排序的时间复杂度为O(n2)。

            4、对n个元素进行直接插入排序，其空间复杂度为（）

            A、O(n)

            B、O(1)

            C、O(n2)

            D、O(log2n)

            解析：（B）

            直接插入排序代码如下：

            /*直接插入排序（由小到大）*/void InsertSort(int r[],int n) {int i,j,temp;for(i=1; itemp=r[i];//将要插入的元素暂存在temp中for(j=0,j=i-1;tempint i,j,temp,low,high,mid;for(i=1; i temp=r[i];//将要插入的元素暂存在temp中low=0;high=i-1;//low和high为折半查找的范围 while(lowmid=(low+high)/2;//mid取中间点 if(r[mid]temp)//查找左半子表 high=mid-1;else//查找右半子表 low=mid+1;}for(j=i-1; j=high+1; j--)//先后移动元素，空出位置留给插入元素 r[j+1]=r[j];r[j+1]=temp;//找到插入位置并插入}}

            p由于折半插入排序中只使用了辅助变量，故空间复杂度与直接插入排序相同，也为O(1)。/p h43、希尔排序/h4 blockquote p1、对初始数据序列(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)进行希尔排序。若第一趟排序结果为(1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)，第二趟排序结果为(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)，则两趟排序采用的增 量（间隔）依次是（）。/ppA、3，1/ppB、3，2/ppC、5，2/ppD、5，3/p /blockquote p解析：（D）/ppimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-2504230332335F.png" //ppimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-250423033234B1.png" //pp故两趟排序采用的增量依次为5和3。/p blockquote p2、希尔排序的组内排序采用的是（）。/ppA、直接插入排序/ppB、折半插入排序/ppC、快速排序/ppD、归并排序/p /blockquote p解析：（A）/pp希尔排序也称为缩小增量排序，它是通过选取一定的增量来排序的，其本质还是插入排序，通过增量将序列分为几个子序列，然后对每个子序列进行直接插入排序，当所有序列呈基本有序时，再进行一次直接插入排序即完成。/p blockquote p3、以下排序中，不稳定的排序算法是（）。/ppA、冒泡排序/ppB、直接插入排序/ppC、希尔排序/ppD、归并排序/p /blockquote p解析：（C）/pp由于分为不同子序列后，可能会出现改变其相对位置情况，所以希尔排序是不稳定的。/p h3题型二（交换排序）/h3 h41、冒泡排序/h4 blockquote p1、对n个元素进行冒泡排序，最好情况下的时间复杂度为（），最坏情况下的时间复杂度为（）/ppA、O(nsup2/sup)，O(n)/ppB、O(n)，O(nsup2/sup)/ppC、O(n)，O(n)/ppD、O(nsup2/sup)，O(nsup2/sup)/p /blockquote p解析：（B）/pp最好情况下，即待排序结果恰好是排序后的结果，此时比较次数为n-1，移动次数和交换次数都为0，故最好时间复杂度为O(n)；而最坏情况下，即排好的序列刚好与初始序列相反，呈逆序排列，则此时需要进行n-1趟排序，第i趟排序中要进行n-i次比较，即比较次数=交换次数=n(n-1)/2，由于每次交换都会移动3次元素从而来交换元素，即移动次数为3n(n-1)/2，故最坏时间复杂度为O(nsup2/sup)，而考虑平均情况下，故冒泡排序的时间复杂度为O(nsup2/sup)；/p blockquote p2、若用冒泡排序算法对序列{10、14、26、29、41、52}从大到小排序，则需要进行（）次比较。/ppA、3/ppB、10/ppC、15/ppD、25/p /blockquote p解析：（C）/pp元素52冒泡到最前面，比较5次；元素41冒泡到最前面，比较4次，……，所以一共比较次数为5+4+3+2+1=15次。/p blockquote p3、若用冒泡排序算法对序列{5，2，6，3，8}升序排序，且以从后向前进行比较，则第一趟冒泡排序的结果为（）。/ppA、{2，5，3，6，8}/ppB、{2，5，6，3，8}/ppC、{2，3，5，6，8}/ppD、{2，3，6，5，8}/p /blockquote p解析：（A）/pp首先，8>3，符合升序，不交换；

            35：

            j继续移动，由于元素8大于则继续向左，到元素3停下，3int i,temp;for(i=n/2;i=1;i--)//建立初始堆 Adjust(r,i,n);for(i=n;i>1;i--){//进行n-1次循环，完成堆排序 temp=r[1];//将堆中最后一个元素与堆顶元素交换，将其放入最终位置 r[1]=r[i];r[i]=temp;Adjust(r,1,i-1); //对剩下的无序序列进行调整 }}

            由于只需要常数个辅助单元，所以空间复杂度为O(1)。

            9、若只想的带1000个元素组成的序列中第10个最小元素之前的部分排序的序列，用（）方法最快。

            A、冒泡排序

            B、快速排序

            C、希尔排序

            D、堆排序

            解析：（D）

            通常在一大堆数据中取k个最大/最小元素时，一般采用堆排序，由于其只需要调整10次大/小根堆，其时间与形成的树的高度成正比。

            题型四（归并排序）

            1、下列排序算法中，占用辅助空间最多的是（）。

            A、快速排序

            B、归并排序

            C、堆排序

            D、冒泡排序

            解析：（B）

            归并排序的代码如下：

            /*归并*/void Merge(int r[],int low,int mid,int high) {int *r1=(int *)malloc((high-low+1)*sizeof(int));//辅助数组r1 for(int k=low; k//low指向为第一个有序表的第一个元素，j指向第二个有序表的第一个元素if(r1[i]if(lowint mid=(low+high)/2;//划分 MergeSort(r,low,mid);//对左有序子表递归 MergeSort(r,mid+1,high);//对右有序子表递归 Merge(r,low,mid,high);//归并}}46，74，53，14，26，38，86，65，27，34}；46，53，74，14，26，38，86，65，27，34}；14，46，53，74，26，38，86，65，27，34}；14，26，46，53，74，38，86，65，27，34}；14，26，38，46，53，74，86，65，27，34}；14，26，38，46，53，74，86，65，27，34}；14，26，38，46，53，65，74，86，27，34}；14，26，27，38，46，53，65，74，86，34}；14，26，27，34，38，46，53，65，74，86}，此时直接插入排序结束，最终结果为{14，26，27，34，38，46，53，65，74，86}。13，27，38，49，65，76，97，49*}。13，27，38，49*，49，65，76，97}。50，8，30，40，20，90，26，38，80，70}；26，8，30，40，20，80，50，38，90，70}；8，20，26，30，38，40，50，70，80，90}。40，38，46，56，79，84}；38，40，46，56，79，84}。-2，0，7，1，4，3}；-2，0，7，1，4，3}；-2，0，1，7，4，3}；-2，0，1，3，4，7}；-2，0，1，3，4，7}；-2，0，1，3，4，7}。15，19，21，29，32，33，38，40}。15，34，13，93，65，74，17，20}。13，15，34，93，17，20，65，74}。13，15，17，20，34，65，74，93}。521，532，513，703，983，476，147，577，147*，189}；703、513、521、532、147、147*、476、577、983、189}；147、147*、189、476、513、521、532、577、703、983}。