客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
一、基本思想
插入排序算法是每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到所有元素插入完毕为止。
二、算法过程
1）将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面，这样的插入方式，排序是稳定的）。
三、算法图解
四、PHP代码实现
function insertSort($arr) {
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$temp = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
if ($temp < $arr[$j]) {
$arr[$j + 1] = $arr[$j];
$arr[$j] = $temp;
} else {
break;
}
}
}
return $arr;
}
五、效率分析
1、时间复杂度：O(n²)
最好的情况：待排序记录按关键字从小到大排列（正序），需要比较n-1次，不需要交换元素，时间复杂度为O(n);
最坏的情况：待排序记录按关键字从大到小排列（逆序），时间复杂度为O(n²)。
2、空间复杂度：O(1)，是稳定排序。
|
2022-11-06
2022-08-17
2022-07-18
2022-08-17
2022-07-29
librespeed/speedtest: Self-hosted Speedtest for HTML5 and more. Easy setup, exam
avehtari/BDA_m_demos: Bayesian Data Analysis demos for Matlab/Octave
女人怀孕后，为了有一个健康聪明的宝宝，经历各种体检、筛查。其实这些体检和筛查中的
jacobmoncur/QuiltViewLibrary: Android Quilt View Library
medfreeman/markdown-it-toc-and-anchor: markdown-it plugin to add a toc and ancho
1、需求：要在小程序中展示新手指引富文本，某位吃饱没事做的后端拉着我要弄一个pc端
sydney0zq/covid-19-detection: The implementation of A Weakly-supervised Framewor
The Simple Page Transition WordPress plugin through 1.4.1 does not sanitise and
离中国最远的国家是阿根廷。从太平洋直线计算，即往东线走，北京到阿根廷的布宜诺斯艾
sciunto-org/python-bibtexparser: Bibtex parser for Python 3
请发表评论