插入排序

简介: 概念:插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

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

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。


*算法描述:

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

从第一个元素开始,该元素可以认为已经被排序;

取出下一个元素,在已经排序的元素序列中从后向前扫描;

如果该元素(已排序)大于新元素,将该元素移到下一位置;

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置后;

重复步骤2~5。

        if (arr == null || arr.length < 2) {
            return arr;
        }
        for (let i = 1; i < arr.length; i++) {
            for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        return arr;
    }
    var arr = [3, 4, 2, 1, 6, 7, 8, 4];
    console.log(arr); // [3, 4, 2, 1, 6, 7, 8, 4]
    insertionSort(arr);
    console.log(arr); // [1, 2, 3, 4, 4, 6, 7, 8]
相关文章
|
27天前
|
搜索推荐 算法 C语言
插入排序
插入排序是一种简单直观的排序算法,通过构建有序序列,将未排序的数据逐个插入到已排序序列中的适当位置。该算法采用in-place排序,只需常数级额外空间。示例代码展示了如何使用C语言实现插入排序,并对一个整数数组进行排序。
25 6
|
6月前
|
算法 搜索推荐 Java
插入排序就是这么容易
插入排序就是这么容易
33 0
|
7月前
|
搜索推荐 C++
C++插入排序的实现
C++插入排序的实现
|
7月前
|
存储 搜索推荐 算法
插入排序(一)——直接插入排序与希尔排序
插入排序(一)——直接插入排序与希尔排序
51 1
|
7月前
|
搜索推荐 算法 测试技术
排序算法:插入排序(直接插入排序、希尔排序)
排序算法:插入排序(直接插入排序、希尔排序)
76 0
|
搜索推荐
17 插入排序
17 插入排序
38 0
插入排序与希尔排序
插入排序与希尔排序
54 0
|
搜索推荐 测试技术 C++
【插入排序】直接插入排序 与 希尔排序
【插入排序】直接插入排序 与 希尔排序
|
算法
插入排序之直接插入排序
一、基本思想: 依次将每个记录(无序表)插入到一个已排好序的有序表中,得到一个新的,记录增加1的有序表;
插入排序
在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。   但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。