直接插入排序

using namespace std;
int num[100] = { 0 };

void insertSort(int n){
int i = 2,j;
int tmp;
for (i = 2; i < n; ++i){
if (num[i] < num[i - 1]){
tmp = num[i];
num[i] = num[i - 1];
for (j = i - 2; tmp < num[j]; --j){
num[j + 1] = num[j];
}
num[j + 1] = tmp;
}
}
}
int main(){
int n;
int i;
while (cin >> n){
for (i = 0; i < n; i++){
cin >> num[i];
}
insertSort(n);
for (i = 0; i < n; i++){
cout << num[i] << " ";
}
cout << endl;
}
return 0;
}
为了提高效率可以在插入的时候可以使用折半查找的方式。
void BinsertSort(int n){
int i = 2,j;
int tmp;
for (i = 1; i < n; ++i){
if (num[i] < num[i - 1]){
tmp = num[i];
int low = 0,high=i-1;
int m;
while (low <= high){
m = (low + high) / 2;
if (tmp < num[m]){
high = m - 1;
}
else{
low = m + 1;
}//else
}//while
for (j = i - 1; j >= high + 1; --j){
num[j + 1] = num[j];
}
num[j + 1] = tmp;
}
}
}