1.3 插入排序

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

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

1. 算法步骤

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

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

2. 动图演示

代码实现

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;

}

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

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

}

Java

实例

public class InsertSort implements IArraySort {



    @Override

    public int[] sort(int[] sourceArray) throws Exception {

        // 对 arr 进行拷贝，不改变参数内容

        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);



        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的

        for (int i = 1; i < arr.length; i++) {



            // 记录要插入的数据

            int tmp = arr[i];



            // 从已经排序的序列最右边的开始比较，找到比其小的数

            int j = i;

            while (j > 0 && tmp < arr[j - 1]) {

                arr[j] = arr[j - 1];

                j--;

            }



            // 存在比其小的数，插入

            if (j != i) {

                arr[j] = tmp;

            }



        }

        return arr;

    }

}

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;

}

C

实例

void insertion_sort(int arr[], int len){

        int i,j,key;

        for (i=1;i<len;i++){

                key = arr[i];

                j=i-1;

                while((j>=0) && (arr[j]>key)) {

                        arr[j+1] = arr[j];

                        j--;

                }

                arr[j+1] = key;

        }

}

C++

实例

void insertion_sort(int arr[],int len){

        for(int i=1;i<len;i++){

                int key=arr[i];

                int j=i-1;

                while((j>=0) && (key<arr[j])){

                        arr[j+1]=arr[j];

                        j--;

                }

                arr[j+1]=key;

        }

}

C#

实例

public static void InsertSort(int[] array)

{

    for(int i = 1;i < array.length;i++)

    {

        int temp = array[i];

        for(int j = i - 1;j >= 0;j--)

        {

            if(array[j] > temp)

            {

                array[j + 1] = array[j];

                array[j] = temp;

            }

            else

                break;

        }

    }

}

Swift

实例

for i in 1..<arr.endIndex {

    let temp = arr[i]

    for j in (0..<i).reversed() {

        if arr[j] > temp {

            arr.swapAt(j, j+1)

        }

    }

}

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md

参考地址：https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F