hdu 2019:数列秩序!(データ構造、直接挿入ソート+折半挿入ソート)

数列整列!
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 2   Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
n(n<=100)個の整数があり、小さい順に並べられています.ここで別の整数xを与えます.この数をシーケンスに挿入し、新しいシーケンスを秩序正しくしてください.
Input
入力データには複数のテストインスタンスが含まれており、各グループのデータは2行で構成され、1行目はnとmであり、2行目は秩序化されたn個数の数列である.nとmは同時に0に入力データの終了を示し,本行は処理しない.
Output
各テストインスタンスについて、新しい要素を挿入した数列を出力します.
Sample Input

3 3

1 2 4

0 0

Sample Output

1 2 3 4

Author
lcy
Source
C言語プログラミング練習(三)
 
データ構造:ソート、水問題を挿入します.
ソート思想を挿入する水問題を訓練する.まずmが挿入すべき位置を見つけて、その位置から始まる数を順番に1桁押して、mをこの位置に挿入するという考え方です.ここでの検索は直接検索と半減で2種類検索できますが、後者は少し速いです.
出力フォーマットに注意してください.最後の数字の後ろにスペースはありません.
ACコード:
 
1)並べ替えの直接挿入

 1 #include <iostream>

 2 using namespace std;  3 int main()  4 {  5     int n,m;  6     int a[111];  7     while(cin>>n>>m){  8         if(n==0 && m==0) break;  9         for(int i=1;i<=n;i++)    //     

10             cin>>a[i]; 11         for(int i=1;i<=n;i++){ 12             if(m < a[i]){        //  m        

13                 for(int j=n;j>=i;j--){    //                  

14                     a[j+1] = a[j]; 15  } 16                 a[i] = m;    // m        

17                 break; 18  } 19  } 20         for(int i=1;i<=n+1;i++)    //    

21             if(i==n+1) 22                 cout<<a[i]<<endl; 23             else 

24                 cout<<a[i]<<' '; 25  } 26     return 0; 27 }

 
2)折半挿入ソート

 1 #include <iostream>

 2 using namespace std;  3 int main()  4 {  5     int n,m;  6     int a[111];  7     while(cin>>n>>m){  8         if(n==0 && m==0) break;  9         for(int i=1;i<=n;i++)    //     

10             cin>>a[i]; 11         

12         //     m 

13         int left=1,right=n,mid; 14         while(left<=right){ 15             mid = (left + right)/2; 16             if(a[mid]<=m){ 17                 left = mid+1; 18  } 19             else 

20                 right = mid-1; 21  } 22         //cout<<right+1<<endl;

23         

24         for(int j=n;j>=right+1;j--){    //                 

25             a[j+1] = a[j]; 26  } 27         a[right+1] = m;    // m        

28         

29         for(int i=1;i<=n+1;i++)    //    

30             if(i==n+1) 31                 cout<<a[i]<<endl; 32             else 

33                 cout<<a[i]<<' '; 34  } 35     return 0; 36 }

 
Freecode : www.cnblogs.com/yym2013