插入排序的算法分析：（未完）
可参考的排序算法的博客： http://blog.csdn.net/cjf_iceking/article/details/7916194
这是剪贴的别人的插入排序的 函数代码。
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int j = 0;
while (j < i && pDataArray[j] <= pDataArray[i]) //寻找插入的位置
j++;
if (j < i) //i位置之前，有比pDataArray[i]大的数，则进行挪动和插入
{
int k = i;
int temp = pDataArray[i];
while (k > j) //挪动位置
{
pDataArray[k] = pDataArray[k-1];
k--;
}
pDataArray[k] = temp; //插入
}
}
}
int main()
{
int n;
int a[200];
int i;
cin>>n;
for(i=0; i<n; i++)
{
cin>>a[i];
}
InsertSort(a, n);
for(i=0; i<n; i++)
{
if(i==n-1)
cout<<a[i]<<endl;
else
cout<<a[i]<<" ";
}
return 0;
}
这是我自己的插入函数 模板代码， 待排序数组的数据元素从下标1开始存储，一直存储到下标n。
这个插入函数会将a[0] 设置成一个监测哨， 这样做的好处是：减少交换次数，减少了运行时间。
SDUT 排序
Time Limit: 1000ms Memory limit: 32678K 有疑问？点这里^_^
题目描述
给你N(N<=100)个数,请你按照从小到大的顺序输出。
输入
输入数据第一行是一个正整数N,第二行有N个整数。
输出
输出一行，从小到大输出这N个数，中间用空格隔开。
示例输入
5 1 4 3 2 5
示例输出
1 2 3 4 5
//插入排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void Insert_sort(int a[], int n)
{
int i, j;
for(i=2; i<=n; i++)
{
if( a[i]<a[i-1] )
{
a[0]=a[i];
for(j=i-1; a[0]<a[j]; j--)
{
a[j+1] = a[j];
}
a[j+1]=a[0];
}
}
}
int main()
{
int n;
int i, j;
int a[100];
while(scanf("%d", &n)!=EOF)
{
for(i=1; i<=n; i++)
{
scanf("%d", &a[i] );
}
Insert_sort(a, n);
for(j=1; j<=n; j++)
{
printf("%d%c", a[j], j==n?'
':' ' );
}
}
return 0;
}
HDU 2020 绝对值排序
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42143 Accepted Submission(s): 20476
Problem Description
输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。
Input
输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。
Output
对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。
Sample Input
3 3 -4 2
4 0 1 2 -3
0
Sample Output
-4 3 2
-3 2 1 0
算法： 使用结构体，x保留原数值，y保留该数的绝对值。 利用插入排序对结构体元素y进行排序，然后输出 排序后的的结构体的x元素。
//插入排序
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
struct N
{
int x;
int y;
}a[200];
void Insert_sort( int n)
{
int i, j;
for(i=2; i<=n; i++)
{
if( a[i].y>a[i-1].y )
{
a[0]=a[i];
for(j=i-1; a[0].y>a[j].y; j--)
{
a[j+1] = a[j];
}
a[j+1]=a[0];
}
}
}
int main()
{
int n, dd;
int i, j;
while(scanf("%d", &n)!=EOF)
{
for(i=1; i<=n; i++)
{
scanf("%d", &dd );
a[i].x = dd;
a[i].y = abs(dd);
}
Insert_sort(n);
for(j=1; j<=n; j++)
{
printf("%d%c", a[j].x, j==n?'
':' ' );
}
}
return 0;
}