折半插入排序的c语言实现方式

1、写一个折半插入排序法的函数名，包含参数。

int TwoSort(int * ListData,int ListLength);

2、写一个循环，在循环中应用折半插入排序。数组中变换二次区间方法来实现折半插入法：

int TwoSort(int * ListData,int ListLength)

{

int i = 0;

int j = 0;

for(i=1;i<=length;i++)

{

int tmp = ListData[i];

int low = 0;

int hight = i-1；

while(low <= hight)

{

mid = (low+hight)/2;

if(tmp > ListData[mid])

low = mid+1;

else

hight = mid-1;

}

for(j=i-1;j>=low;j--)

ListData[j+1]=ListData[j];

r[low]=tmp;

}

return 0;

}

3、对编好的程序进行测试，得出测试结果:

#include <stdio.h>

int main()

{

int TestData[5] = {34,15,6,89,67};

int i = 0;

printf("排序之前的结果\n");

for(i = 0;i<5;i++)

printf("|%d|",TestData[i]);

int retData = TwoSort(TestData,5);

printf("排序之后的结果：\n");

for(i = 0;i<5;i++)

printf("|%d|",TestData[i]);

return 0;

}

1、可以减少比较的次数，折半插入要比直接插入排序要快一点，因为它改善了，算法中比较的次数，它的时间复杂度是:n*(log2(n));

这个算法要比直接插入排序要求，但是时间复杂度的笼统的算法是和直接一样的O(n*n);