首先複習一下 Insertion Sort。
Insertion Sort Insertion Sort的精神是當在排序一個數字陣列時，每當處理一個數字，就代表在這個數字之前的數都已經排序好了。因此只需要將這個數字跟前面排好的數字序列比較，並將目前處理的這個數字insert到之前排序好的序列中，就像一般在玩撲克牌時通常會使用的排序法。
以下是我練習將InsertionSort的Code用C++寫出：
void InsertionSort()
{
int key = 0;
for(int j=1;j<size;j++)
{
key = data[j];
int i = j-1;
while(i>=0 && data[i]>key)
{
data[i+1] = data[i];
i--;
}
data[i+1] = key;
}
}
UVA #10107(What is the median)這個題目給的Sample Input跟Sample Output如下：
Sample Input
1
3
4
60
70
50
2
Sample Output
1
2
3
3
4
27
4
本題的目標為每從Sample Input讀進一個數字到序列中，就找出當下的中位數(median)，如果總共有奇數個數字，則將取排序好的數列的中間兩個數字相加除以2，除以2後只取整數部分。
思考方式：
使用Insertion Sort的原因，是因為這題是每讀到一個數字就做排序，所以當讀進一個新數字時，之前的讀過的數字都已經排序好了，所以只須將新讀入的數字Insert到前面排序好的序列的適當位置，這很符合Insertion Sort的基本概念。
以下是我解決此題目的Code：(implement using C++)
//main.cpp
//The excution result is correct, and is accepted by UVA Online Judge.
//This is the code for UVA Online Judge #10107
//This code was created by Uncle on 2012/03/03
#include<iostream>
#include<sstream>
#include<fstream>
using namespace std;
int *data = NULL;
int size = 0;
int *Expand(int *arrReceive,int &s,int key)
{
int *newArr = new int [s+1];
for(int i=0;i<s;i++)
{
newArr[i] = arrReceive[i];
}
newArr[s] = key;
delete []arrReceive;
s++;
return newArr;
}
void InsertionSort()
{
int key = 0;
for(int j=1;j<size;j++)
{
key = data[j];
int i = j-1;
while(i>=0 && data[i]>key)
{
data[i+1] = data[i];
i--;
}
data[i+1] = key;
}
}
int main()
{
int key;
ifstream inputFile;
//inputFile.open("input.txt",ifstream::in);
while(cin >> key)
{
data = Expand(data,size,key);
InsertionSort();
if(size%2) //total size is odd
{
cout << data[size/2] << endl;
}
else
{
int tmp = data[(size/2)-1] + data[size/2];
tmp = tmp/2;
cout << tmp << endl;
}
}
//getchar();
return 0;
}
