龙空技术网

直接插入排序(straight insertion sort)

punkyu 489

前言:

眼前小伙伴们对“c语言直接插入排序”都比较讲究,各位老铁们都需要剖析一些“c语言直接插入排序”的相关内容。那么小编同时在网摘上搜集了一些有关“c语言直接插入排序””的相关内容,希望大家能喜欢,同学们快快来学习一下吧!

思路:

从第一个元素起,视为已排序队列选取下一个元素(新),比较已排序队列从后往前扫描如果新元素小于比较元素则将比较元素移到下一位直到新元素大于或等于比较元素则在其后位置插入(替换)持续b~d步骤直到排序队列有序

适用:

当已知输入元素大致上按照顺序排列,直接插入排序将大大减少比较次数和移动记录的次数。适用于少量数据(小于1000)的排序。

时间复杂度:O(n2)

空间复杂度:O(1)

稳定性:稳定

php代码例子:

// 比较容易理解的写法function insertSort(&$sort_arr) {    for($i=1;$i<count($sort_arr);$i++) {        if($sort_arr[$i] < $sort_arr[$i-1]) {            $tmp = $sort_arr[$i];            for($j=$i-1;$j>=0;$j--) {                if($sort_arr[$j] <= $tmp) {                    break;                }                $sort_arr[$j+1] = $sort_arr[$j];            }            $sort_arr[$j+1] = $tmp;         }       }   }// 简化写法function insertSorts(&$sort_arr) {    for($i=1;$i<count($sort_arr);$i++) {        $tmp = $sort_arr[$i];        for($j=$i-1;$j>=0 && $sort_arr[$j]>$tmp;$j--) {            $sort_arr[$j+1] = $sort_arr[$j];         }        $sort_arr[$j+1] = $tmp;    }}

标签: #c语言直接插入排序