时间:2021-05-19
首先看一下例子,将数据一个个的插入到一个列表中,插入后这个列表就排序好了
注意:这个列表是递增的,而且内存空间已分配好,只是没有填充真正的数据,如下代码:
复制代码 代码如下:
int InsertSort(MergeType *L, int data)
{
int j;
if (!L->len)
{
L->elem[++L->len] = data;
return 0;
}
for (j = L->len-1; j >= 0; --j)
{
if (data < L->elem[j])
{
L->elem[j+1] = L->elem[j];
}
else
{
L->elem[j+1] = data;
L->len++;
break;
}
}
return 0;
}
测试用例的代码如下:
复制代码 代码如下:
#define LISTLEN 10
MergeType pList;
MergeType pT;
pList.elem = (int*)malloc(sizeof(int)*LISTLEN);
ScanfList(&pList);
pList.len = LISTLEN;
pList.size = LISTLEN;
pT.elem= (int*)malloc(sizeof(int)*LISTLEN);
pT.len= 0;
pT.size= LISTLEN;
memset(pT.elem, 0, LISTLEN*sizeof(int));
for (int i = 0; i < LISTLEN; i++ )
{
InsertSort(&pT, pList.elem[i]);
}
PrintList(&pT);
free(pList.elem);
free(pT.elem);
pList.elem = NULL;
pT.elem = NULL;
其他函数以及代码请定义请参考:冒泡算法的改进
直接插入排序
核心思想:是将一个记录插入到已排序好的有序表中,从中得到一个新的、记录数增1的有序表,也就是说递增的次序排列每一个数据,将每一个数据插入到前面已经排序好的位置中。看下面的代码
复制代码 代码如下:
int InsertSort(MergeType* L)
{
int i, j = 0;
int nCompKey;
if (!L->elem || !L->len) return -1;
if (L->elem && (L->len==1)) return 0;
for ( i = 1; i < L->len; i++)
{
if (L->elem[i] < L->elem[i-1])
{
nCompKey = L->elem[i];
L->elem[i] = L->elem[i-1];
//move elements back
for (j = i-2; j >= 0 && nCompKey < L->elem[j]; --j)
{
L->elem[j+1] = L->elem[j];
}
L->elem[j+1] = nCompKey;
}
}
return 0;
}
这里从第二个数据开始,比较当前的数据是否小于前面的一个数,如果小于前面一个数据,就将当前数据插入到前面的队列中,在插入到前面数据中的过程,要移动数据
这里要注意时间的复杂度:
总的比较次数=1+2+……+(i+1-2+1)+……+(n-2+1)= n*(n-1)/2= O(n^2)
总的移动次数=2+3+……+(2+i-1)+ …… + n = (n+2)*(n-1)/2=O(n^2)
当然还要考虑空间复杂度:其实这里使用了一个变量的存储空间作为移动数据的临时空间
这里在移动的过程中,可以减少代码理解的复杂度,但会在每一个数据比较的过程中增加一次比较的次数,如下代码:
复制代码 代码如下:
...
if (L->elem[i] < L->elem[i-1])
{
nCompKey = L->elem[i];
for (j = i-1; j >= 0 && L->elem[j] > nCompKey; --j)
{
L->elem[j+1] = L->elem[j];
}
L->elem[j+1] = nCompKey;
}
...
在插入数据的过程中,其实前面的数据都已经排序好了,这时候一个个的进行查找,必定查找次数较多,如果采用折半查找算法可以减少次数,如下
复制代码 代码如下:
int BInsertSort(MergeType *L)
{
int i, j;
int low, high, mid;
int nCompKey;
for (i = 1; i <= L->len - 1; i++ )
{
nCompKey = L->elem[i];
low = 0;
high = i - 1;
/*当low=high时,此时不能判断插入的位置是在low=high的
*前面还是后面,会进入下面的判断*/
while(low <= high)
{
mid = (low + high)/2;
if ( nCompKey > L->elem[mid] )
{
low = mid + 1;
}
else
{
high = mid -1;
}
}
/*移动nCompKey之前的所有数据,这里使用high+1是因为high<low
*的时候,按理数据应该放在high的位置,但是此时high的位置可
*能已经有排列好的数据或者不存在的位置,所以移动为后一个位置*/
for (j = i-1; j >= high+1; j-- )
{
L->elem[j+1] = L->elem[j];
}
L->elem[high+1] = nCompKey;
}
return 0;
}
具体什么原因,请看上面的注释,这里为什么用high+1,但是此时high与low的位置只相差一个位置,才会跳出while循环,请看下面的改进
复制代码 代码如下:
#if 0
for (j = i-1; j >= high+1; j-- )
{
L->elem[j+1] = L->elem[j];
}
L->elem[high+1] = nCompKey;
#else
for (j = i-1; j >= low; j-- )
{
L->elem[j+1] = L->elem[j];
}
L->elem[low] = nCompKey;
#endif
...
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
一、折半插入排序(二分插入排序)将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理A[i]时,A[0]……A[i-1
前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序)、交换排序(冒泡排序,快速排序)、选择排序(简单选择排序,堆排序)、2-路归
本文总结了一下常用的7种排序方法,并用php语言实现。1、直接插入排序/**直接插入排序,插入排序的思想是:当前插入位置之前的元素有序,*若插入当前位置的元素比
插入排序Python实现importrandoma=[random.randint(1,999)forxinrange(0,36)]#直接插入排序算法defin
直接插入排序importjava.util.HashMap;publicclassInsertSort{privatestaticintcontrastCoun