插入排序 insert sort

插入排序

1. 时间复杂度（平均、最坏）O(n^2), 最好时间复杂度O(n)
2. 空间复杂度为O(1)
3. 稳定性：稳定

算法解析：
插入排序类似于打扑克，取出未排序的一张牌插入到已排序的牌中，取出的一张牌是在已排序好的牌中从后向前查找，直到查找到比当前牌小的那个位置，然后插入进去

动画演示：

insertionSort

C代码：

int * insertSort1(int arr[],int count) {
    int current,preIndex;
    for (int i = 1; i<count; i++) {
        current = arr[i];
        preIndex = i - 1;
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

OC代码

- (NSArray *)insertSort:(NSMutableArray *)arr {
    NSNumber *current = nil;
    int preIndex;
    for (int i = 1; i<arr.count; i++) {
        current = arr[i];
        preIndex = i - 1;
        while (preIndex >= 0 && [arr[preIndex] intValue] > [current intValue]) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr.copy;
}

Swift代码

func insertSort(_ arr:Array<Int>) -> Array<Int> {
    var current = 0
    var preIndex = 0
    var tmpArr = arr
    for (index,item) in tmpArr.enumerated() {
        current = item
        preIndex = index - 1
        while(preIndex >= 0 && tmpArr[preIndex] > current) {
            tmpArr[preIndex+1] = tmpArr[preIndex]
            preIndex -= 1;
        }
        tmpArr[preIndex+1] = current
    }
    return tmpArr
}

以下语言实现来源于网络，未验证

js实现

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