Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> 關於Android編程 >> 插入排序

插入排序

編輯:關於Android編程

 1. 問題描述


輸入:n個數的序列<a1,a2,a3,...,an>。
輸出:原序列的一個重排<a1*,a2*,a3*,...,an*>;,使得a1*<=a2*<=a3*<=...<=an*。

2.問題分析


(1)從有序數列和無序數列{a2,a3,…,an}開始進行排序;
(2)處理第i個元素時(i=2,3,…,n),數列{a1,a2,…,ai-1}是已有序的,而數列{ai,ai+1,…,an}是無序的。用ai與ai-1,a i-2,…,a1進行比較,找出合適的位置將ai插入;
(3)重復第二步,共進行n-i次插入處理,數列全部有序。

 \
\
 


3. 算法實現

[cpp]
template <typename T> 
void InsertSort( CVector<T> &vec ) 

    for ( size_t i=1; i<vec.GetSize(); i++ ) 
    { 
        T temp = vec[i]; 
        int j = i-1; 
 
        while ( j >= 0 && vec[j] > temp ) 
        { 
            vec[j+1] = vec[j]; 
            j--; 
        } 
 
        vec[j+1] = temp; 
    } 

template <typename T>
void InsertSort( CVector<T> &vec )
{
    for ( size_t i=1; i<vec.GetSize(); i++ )
    {
        T temp = vec[i];
        int j = i-1;

        while ( j >= 0 && vec[j] > temp )
        {
            vec[j+1] = vec[j];
            j--;
        }

        vec[j+1] = temp;
    }
}測試:


[cpp]
#define  DATA_MAGNITUDE 1000  
 
double random(double start, double end) 

    return start+(end-start)*rand()/(RAND_MAX + 1.0); 

//-----------------------------------------------------------  
    srand( unsigned(time(0))); 
    for ( int i=0; i<DATA_MAGNITUDE; i++ ) 
    { 
        vec2.PushBack( random(1, DATA_MAGNITUDE) ); 
    } 
 
    int size = 20>DATA_MAGNITUDE? 20 : DATA_MAGNITUDE; 
    InsertSort<int>( vec2 ); 
    for ( size_t i =0; i < size; i++ ) 
    { 
        cout<<vec2[i]<<" "; 
    } 
    cout<<endl; 

#define  DATA_MAGNITUDE 1000

double random(double start, double end)
{
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}
//-----------------------------------------------------------
    srand( unsigned(time(0)));
    for ( int i=0; i<DATA_MAGNITUDE; i++ )
    {
        vec2.PushBack( random(1, DATA_MAGNITUDE) );
    }

 int size = 20>DATA_MAGNITUDE? 20 : DATA_MAGNITUDE;
    InsertSort<int>( vec2 );
    for ( size_t i =0; i < size; i++ )
    {
        cout<<vec2[i]<<" ";
    }
    cout<<endl;


4. 算法分析

 comp move
best n-1 0
worst n(n-1)/2 = o(n^2) n(n-1)/2 = o(n^2)
avg n(n-1)/4 = o(n^2) n(n-1)/4 = o(n^2)


 

  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved