插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序的核心思想就是：在一个有序数组中找到一个新加入的值在有序数组中的位置。

Java版

实现方式一(时间复杂度O(n^2) )

内层循环从有序数组的头部开始遍历，找到当前新加入值在这个有序数组中的下标，然后进行移动，将新加入的值插入。

public int[] insertSort(int[] arr){
    if (null== arr || arr.length==0){
        return arr;
    }
    int len = arr.length;
    for(int i=1; i<len; i++){
        if (arr[i-1] < arr[i]) {
            // 新进入的数字比当前有序数组的最后一个数字大，那么需要查找新加入数字的位置
            for (int j=0; j<i; j++){
                // 在有序数组里面找到这个新加入数字的位置
                if (arr[j] < arr[i]){
                    // 找到新加入数字的位置为j；此时将数字插入数数组里面
                    int temp = arr[i];
                    //将找到的位置处的数都向后移动
//                        for (int k=i; k>j; k--){
//                            arr[k] = arr[k-1];
//                        }
                    // 这个系统的函数的意思是从源数组的下标为j的地方开始，拷贝i-j个数字到目标数组中，从目标数组的j+1下标开放置
                    System.arraycopy(arr, j, arr, j + 1, i - j);
                    arr[j] = temp;
                    break;
                }
            }
        }
    }
    return arr;
}

实现方式二(时间复杂度O(nlgN))

这种方式是在第一种方式的基础上优化了的内层循环在查找新进入的值的位置的算法，下面采用的是二分查找算法

public int[] insertSort(int[] arr){
    int len = arr.length;

    for (int i=1; i<len; i++){
        if (arr[i]>arr[i-1]){
            // 查找当前值在有序数组中的位置；下面采用二分查找算法（lgN）进行处理
            int left = 0;
            int right = i-1;
            int tmp = arr[i];

            while (left<=right){
                int mid = (left+right) >> 1;
                if (tmp > arr[mid]){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }
            // 将数组后移，腾出新加入数据的位置
            System.arraycopy(arr, left, arr, left+1, i-left);
            arr[left] = tmp;
        }
    }
    return arr;
}

实现方式三(时间复杂度O(n^2))

内层循环从有序数组的尾部开始遍历，当后一个比前一个大（从大到小排序）就交换顺序，直到前一个比后一个小。

public int[] insertSort(int[] arr){
    int len = arr.length;

    for (int i=1; i<len; i++){
        if (arr[i-1] < arr[i]) {
            // 使用从最后面开始比较；如果小于当前值就交换顺序
            for (int j=i; j>0; j--){
                // 这里做个优化：因为这个 0~~(i-1) 的数组是有序的；因此当这个值比前面小的时候那么就说明已经排序好了;
                if (arr[j] <= arr[j-1]){
                    break;
                }
                // 直接使用当前值从后面依次比较，如果当前值大于的话那么就进行值的交换
                if (arr[j] > arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }
    return arr;
}

Golang版本

实现方式一

func insertSort(arr [6]int) [6]int {
	size := len(arr)
	for i:=1; i<size; i++ {
		if arr[i] > arr[i-1] {
			for j:=0; j<i; j++ {
				if arr[j]<arr[i] {
					tmp := arr[i]
					for k:=i-1; k>=j; k-- {
						arr[k+1] = arr[k]
					}
					arr[j] = tmp
					break
				}
			}
		}
	}
	return arr
}

实现方式二

func insertSort(arr [6]int) [6]int {
	size := len(arr)
	for i:=1; i<size; i++ {
		if arr[i] > arr[i-1] {
			left, right, mid := 0, i-1, 0
			tmp := arr[i]

			// 通过二分查找
			for left<=right {
				mid = (left+right)>>1
				if arr[mid] < tmp {
					right = mid-1
				}else {
					left = mid+1
				}
			}

			for k:=i-1; k>=left; k-- {
				arr[k+1] = arr[k]
			}
			arr[left] = tmp
		}
	}
	return arr
}