博主头像
mxd's Blog

"The quieter you become,the more you are able to hear."

插入排序算法

插入排序基本思想

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

insertionSort.gif
insertionSort.gif

示例代码

1.C++

for(int i=2;i<=n;i++)//从第二个数开始排序
{
    key=a[i];//待记录插入的数字
    j=i-1;//令j=已有序列的尾位置
    while(j>=1 and key<a[j])//从后往前遍历序列的已有序列,直到第一个比key小的位置
    {
        a[j+1]=a[j];
        j--;
    }
    a[j+1]=key;
}

2.PHP

function insertionSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        $current = $arr[$i];
        while($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex+1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex+1] = $current;
    }
    return $arr;
}

3.JavaScript

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}


插入排序算法
https://blog.mxdyeah.top/mxdyeah_blog_post/37.html
本文作者 mxdyeah
发布时间 2024-01-22
许可协议 CC BY-NC-SA 4.0
发表新评论