編輯:關於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)
在機器視覺實驗室呆了有一年半時間了,但由於自己“任性”。一直以來學習的內容都是自己來安排,我還是堅持認為沒有最好和最簡單的技術,只有自己喜歡的技術
Android Fragment的回退棧點開之後按一次回退鍵只返回一次MainActivity 類public class MainActivity exte
360來電顯示歸屬地怎麼設置? 1、如果你使用的是安卓手機,那麼下載安裝並打開安卓版360安全衛士,切換到隱私保護然後點擊右上角三點符號找到衛士設置;3
本文實例講述了Android編程之ListPreference用法。分享給大家供大家參考,具體如下:先展示一下效果圖,如下所示:項目代碼如下:package com.my