插入排序算法的原理很简单，首先将数组的第一个数data[0]看成是有序的，然后从第二个元素开始和它前面的元素进行比较，如果从前面的某一个数大，就交换。由于前面的元素是有序的，所以就使有序元素的个数逐渐增大，直到等于n。插入排序的时间复杂度为
O(n^2)
。
算法的c实现如下：
算法的c实现如下：
#include
<
stdio.h
>
void output_array( int data[], int n)
{
int i;
for (i = 0 ; i < n; i ++ )
printf( " %d " , data[i]);
printf( " \n " );
}
void swap( int * a, int * b)
{
int x;
x = * a;
* a = * b;
* b = x;
}
// 算法实现
void insertion( int data[], int b, int e)
{
int i, j;
for (i = b + 1 ; i <= e; i ++ )
{
for (j = i; j > 0 && data[j] > data[j - 1 ]; j -- )
{
swap( & data[j], & data[j - 1 ]);
}
}
}
int main()
{
int data[] = { 5 , 3 , 1 , 665 , 77 , 66 , 44 , 11 , 10 , 9 , 8 , 6 };
output_array(data, 12 );
insertion(data, 0 , 11 );
output_array(data, 12 );
return 0 ;
}
void output_array( int data[], int n)
{
int i;
for (i = 0 ; i < n; i ++ )
printf( " %d " , data[i]);
printf( " \n " );
}
void swap( int * a, int * b)
{
int x;
x = * a;
* a = * b;
* b = x;
}
// 算法实现
void insertion( int data[], int b, int e)
{
int i, j;
for (i = b + 1 ; i <= e; i ++ )
{
for (j = i; j > 0 && data[j] > data[j - 1 ]; j -- )
{
swap( & data[j], & data[j - 1 ]);
}
}
}
int main()
{
int data[] = { 5 , 3 , 1 , 665 , 77 , 66 , 44 , 11 , 10 , 9 , 8 , 6 };
output_array(data, 12 );
insertion(data, 0 , 11 );
output_array(data, 12 );
return 0 ;
}
本文转自 androidguy 51CTO博客，原文链接：http://blog.51cto.com/androidguy/216634，如需转载请自行联系原作者
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)