排序算法C语言实现——插入排序(优于冒泡)
为什么插入排序要优于冒泡? 插入排序在于向已排序序列中插入新元素,主要的动作是移动元素,涉及1次赋值,即data[j] = data[j-1]; 而冒泡排序在于相邻元素交换位置,涉及3条赋值,即iTmp = data[j+1];data[j+1] = data[j];data[j] = iTmp; 事实上插入的元素移动次数,与冒泡的元素交换次数是相同的,都等于待排序序列的逆序度。 而冒泡比插入多了2次元素赋值。所以插入要比冒泡快。 冒泡排序代码见:https://www.cnblogs.com/JoZSM/p/9768735.html 插入排序代码如下: /*插入*/ /* 原理: 每次从待排序序列中选取第1个元素,插入到已排序序列中。 */
/*O(n^2)
*/
void InsertSort(int* data, size_t len)
{
size_t i=0,j=0;
int iTemp=0; if(NULL == data)
{
/*throw("Invalid Parameter");*/
return;
} for(i=1; i<len; ++i)
{
iTemp = data[i];
for(j=i; j>0; --j)
{
if(data[j-1] > iTemp)
{
data[j] = data[j-1];
}
else
{
break;
}
}
data[j] = iTemp;
}
}
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄
/*O(n^2)
*/
void InsertSort(int* data, size_t len)
{
size_t i=0,j=0;
int iTemp=0; if(NULL == data)
{
/*throw("Invalid Parameter");*/
return;
} for(i=1; i<len; ++i)
{
iTemp = data[i];
for(j=i; j>0; --j)
{
if(data[j-1] > iTemp)
{
data[j] = data[j-1];
}
else
{
break;
}
}
data[j] = iTemp;
}
}
更多精彩