📦 c语言算法排序 - 免费下载

1．Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. (Implement exercise 2.3-7.)

#include<stdio.h>
#include<stdlib.h>
void merge(int arr[],int low,int mid,int high){
     int i,k;
     int *tmp=(int*)malloc((high-low+1)*sizeof(int));
     int left_low=low;
     int left_high=mid;
     int right_low=mid+1;
     int right_high=high;
     for(k=0;left_low<=left_high&&right_low<=right_high;k++)
     {
     if(arr[left_low]<=arr[right_low]){
                                       tmp[k]=arr[left_low++];
                                       }
     else{
          tmp[k]=arr[right_low++];
          }
} 
     
     if(left_low<=left_high){
                             for(i=left_low;i<=left_high;i++){
                                                              tmp[k++]=arr[i];
                                                              }
                             }
      if(right_low<=right_high){
                             for(i=right_low;i<=right_high;i++)
                                                               tmp[k++]=arr[i];
                                                       }
                             for(i=0;i<high-low+1;i++)
                                                      arr[low+i]=tmp[i];
     
}

void merge_sort(int a[],int p,int r){
     int q;
     if(p<r){
             q=(p+r)/2;
             merge_sort(a,p,q);
             merge_sort(a,q+1,r);
             merge(a,p,q,r);
             }
     }
int main(){
    int a[8]={3,5,8,6,4,1,1};
    int i,j;
    int x=10;
    merge_sort(a,0,6);
    printf("after Merging-Sort:\n");
    for(i=0;i<7;i++){
                     printf("%d",a[i]);
                     }
    printf("\n");
    i=0;j=6;
    do{
                 
                 if(a[i]+a[j]==x){
                                 printf("exist");
                                 break;
                                 }
                 if(a[i]+a[j]>x)
                                j--;
                 if(a[i]+a[j]<x)
                                i++;
                      }while(i<=j);
    if(i>j) 
            printf("not exist");
    system("pause");
    return 0;
    }

点击标签查看更多相关资源：