插入排序算法(直接,折半,希尔)

插入排序

 

直接插入排序的算法思想是:

 以数组的第一个元素作为基础,从第二个元素开始下标index = 1,依次到N。

 然后顺序的从下标0到下标index-1,与当前待插入的元素下标index进行比较,查找到合适的插入位置,然后将当前元素放到此位置上。
两个循环:一是 从第二个元素开始,依次到N

      二是 比较寻找合适位置,移动数组,插入元素 

两个过程:一是查找插入位置

       二是将相应元素放到插入的位置上

时间复杂度为:O(n^2)

其实现算法如下:

一 按照过程进行:

bool sort_by_insert(int *src,int len)
{
int index = 1;
int i,j,temp;
while(index < len)
{
temp = src[index];

//寻找插入位置
for(i = 0; i < index ; i++)

{
if(src[i] > temp)
{
break;
}
}

//移动数组记录
for (j = index; j > i ; j--)

{
src[j] = src[j-1];
}
src[i] = temp;

index++;
}

return true;
}

二 合并两个过程

bool sort_by_insert_ex(int *src,int len)
{
int index = 1;
int i,temp;
while(index < len)
{
temp = src[index];
for(i = index; i>0; i--)
{
if(src[i-1] > temp)
{
src[i] = src[i-1];
}
else
{
break;
}
}
src[i] = temp;
index++;
}

return true;
}
三 插入排序改进
  插入排序算法主要 是两个过程:比较移动。想要提高速率,只能从这两方面上改进。
1 折半掺入排序(减少比较次数)
bool sort_by_half_insert(int *src,int len)
{
int index = 1;
int i,j,temp;
while(index < len)
{
temp = src[index];

//寻找插入位置
i = 0;

j = index;
while(i < j)
{
//折半进行比较
if(temp <= src[(i + j)/2])

{
j = (i + j)/2 - 1;
}
else
{
i = (i + j)/2 + 1;
}
}

//移动数组记录
for (j = index; j > i ; j--)

{
src[j] = src[j-1];
}
src[i] = temp;

index++;
}

return true;
}
 
四 希尔排序
基本思想:将待排序列,按照等间隔分成几个组,然后分别对每个组进行插入排序。

bool sort_by_shell(int *src,int len)
{
int start = 1;
int i,step,Temp;

//获取增量序列的最大值 以 h = 3*h + 1 方式
  for(step = 0; step <= len/9; step = step*3 + 1)
;
for(step ;step > 0; step /= 3)
{
//一趟希尔排序
for(start = step; start < len; start++)
{
Temp = src[start];
//分组排序
for(i = start - step; i>=0; i-= step)
{
if (src[i] > Temp)
{
src[i + step] = src[i];
}
else
{
break;
}

src[i] = Temp;
}
}
}

return 0;
}





原文地址:https://www.cnblogs.com/bastard/p/2251974.html