數據結構與算法分析C語言描述-1.1

2019-11-08 02:22:28

字體：大中小

來源：轉載

供稿：網友

#include <stdio.h> #include <time.h>/*將前k個元素讀入數組并（以遞減的順序）對其排序。接著，將剩下的元素再逐個讀入如果它小于數組中的第k個元素則忽略否則就將其放到數組中正確的位置上，同時將數組中的一個元素擠出數組 */ #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))int key(int *a,int len,int k);int location(int *a,int len,int ins);void insert(int *a,int len,int insKey); int main(void){ int count; PRintf("請輸入元素的個數N:"); scanf("%d",&count); int k=count/2; int time1=clock(); int i; //輸入的所有元素保存在數組a int a[count]; //排序后的前k個元素保存在數組b int b[k]; int input; for(i=0;i<count;i++){ scanf("%d",&input); a[i]=input; } //將前k個元素賦值geib for(i=0;i<k;i++){ b[i]=a[i]; } for(i=0;i<k;i++){ printf("%d ",b[i]); } printf("/n"); //對b進行排序 BubbleSort(b,k); for(i=0;i<k;i++){ printf("%d ",b[i]); } printf("/n"); //插入操作 for(i=k;i<count;i++){ if(a[i]>b[k-1]) insert(b,k,a[i]); } int time2=clock(); printf("%d time:/%lf",b[k-1],(time2-time1)); return 0;} //降序后返回最小的值 int key(int *a,int len,int k){ int i,j,tmp; for(i=0;i<len-1;i++){ for(j=0;j<len-1-i;j++){ if(*(a+j)<*(a+j+1)){ SWAP(*(a+j),*(a+j+1),tmp); } } } return *(a+k-1);} //插入操作（要插入的數組，數組長度，插入的值） void insert(int *a,int len,int insKey){ int locat; locat=location(a,len,insKey); int tmp[len]; for(int i=0;i<len;i++){ tmp[i]=*(a+i); } for(int i=locat;i<len-1;i++){ *(a+i+1)=tmp[i]; } *(a+locat)=insKey; }//得到插入位置（插入數組，數組長度，插入的值）int location(int *a,int len,int ins){ int i=0; while(ins<*(a+i)&&i<len){ i++; } if(i<len){ return i; }else{ printf("未找到插入位置"); return -1; }}

上一篇：UVA - 10285 Longest Run on a Snowboard （線性DP）

下一篇：POJ 2299 Ultra-QuickSort （歸并排序、逆序數）