插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

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

1. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2. 动图演示

动图演示

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;
}

4. Python 代码实现

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

5. Go 代码实现

func insertionSort(arr []int) []int {
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        arr[preIndex+1] = current
    }
    return arr
}

冒泡排序

发布于:2年以前  |  2773次阅读  |  详细内容 »

选择排序

发布于:2年以前  |  1887次阅读  |  详细内容 »

归并排序

发布于:2年以前  |  1942次阅读  |  详细内容 »

快速排序

发布于:2年以前  |  2000次阅读  |  详细内容 »

插入排序

发布于:2年以前  |  2268次阅读  |  详细内容 »

十大经典排序算法

发布于:2年以前  |  2369次阅读  |  详细内容 »

基数排序

发布于:2年以前  |  2917次阅读  |  详细内容 »

希尔排序

发布于:2年以前  |  1676次阅读  |  详细内容 »

堆排序

发布于:2年以前  |  2360次阅读  |  详细内容 »

桶排序

发布于:2年以前  |  2386次阅读  |  详细内容 »

所属标签

最多阅读

基数排序 2年以前  |  2917次阅读
冒泡排序 2年以前  |  2773次阅读
计数排序 2年以前  |  2520次阅读
桶排序 2年以前  |  2386次阅读
十大经典排序算法 2年以前  |  2369次阅读
堆排序 2年以前  |  2360次阅读
插入排序 2年以前  |  2268次阅读
快速排序 2年以前  |  2000次阅读
归并排序 2年以前  |  1942次阅读
选择排序 2年以前  |  1887次阅读
希尔排序 2年以前  |  1676次阅读