免费智能真题库 > 历年试卷 > 程序员 > 2017年下半年 程序员 下午试卷 案例
  第2题      
  知识点:   选择排序   简单选择排序   排序

 
【说明】
对n个元素进行简单选择排序的基本方法是:第一趟从第1个元素开始,在n个元素中选出最小者,将其交换至第一个位置,第二趟从第2个元素开始,在剩下的n-1个元素中选出最小者,将其交换至第二个位置,依此类推,第i趟从n=i+1个元素中选出最小元素,将其交换至第i个位置,通过n-1趟选择最终得到非递减排序的有序序列。
 
问题:2.1   【代码】
#include <stdio.h>
void selectSort(int data[ ],int n)
//对 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列
{
     int i,j,k;
     int temp;
     for(i=0;i<n-1;i++){
          for(k=i,j=i+1;(1);(2)) //k表示data[i]~data[n-1]中最小元素的下标
                 if(data[j]<data[k]) (3) 
     if(k!=i) {
        //将本趟找出的最小元素与data[i]交换
         temp=data[i]; (4) ;data[k]=temp;
      }
   }
}

int main()
{
     int arr[ ]={79,85,93,65,44,70,100,57};
     int i,m;
     m=sizeof(arr)/sizeof(int); //计算数组元素的个数,用m表示
    (5); //调用selectSort对数组arr进行非递减排序
     for((6);i <m;i++) //按非递减顺序输出所有的数组元素 
          printf(“%d\t”,arr[i]);
     printf(“\n”);
     return 0;
}
 
 
 

   知识点讲解    
   · 选择排序    · 简单选择排序    · 排序
 
       选择排序
        若设R[1...n]为待排序的n个记录,R[1...i-1]已按照主关键字由小到大排序,且任意x∈R[1...i-1],y∈R[i...n]满足x.key≤y.key,则选择排序的主要思路如下。
        (1)反复从R[i...n]中选出关键字最小的结点R[k]。
        (2)若i≠k,则将R[i]与R[k]交换,使得R[1...i]有序且保持原来的性质。
        (3)i增1,直到i为n。
        为方便描述,被查找的顺序表C类型定义如下:
        
        顺序存储线性表的选择排序算法如下:
        
        可见,选择排序不管原先序列是否有序,其排序需要比较的次数均为n(n-1)/2;同时,由于相等的两个元素,位置相对在前的可能被交换到后面,故该选择排序是不稳定的。
 
       简单选择排序
        n个记录进行简单选择排序的基本方法是:通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤in)个记录进行交换,当i等于n时所有记录有序排列。
        【算法】简单选择排序算法。
        
        简单选择排序法在最好情况下(待排序列已按关键码有序)不需要移动元素,因此n个元素排序时的总移动次数为0次。在最坏情况下(元素已经逆序排列),每趟排序移动记录的次数都为3次(两个数组元素交换值),共进行n-1趟排序,总移动次数为3(n-1)。无论在哪种情况下,元素的总比较次数为
        由此,简单选择排序是一种不稳定的排序方法,其时间复杂度为On2)。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换,空间复杂度为O(1)。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
   题号导航      2017年下半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第2题    在手机中做本题