插入排序

启发：像接扑克牌，每次拿一张插到合适的位置

image.png

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

过程看似和冒泡、选择很像。
冒泡是每次冒大小顺序不对就交换，一趟就把最小/最大的放在正确的位置了。
选择每趟找最小/大放在前面，一趟交换一次。

插入排序时每次拿到一个数把他插到相应的位置，有个插入操作，所以就多一个后面元素要往后移动一个位置的操作。

image.png

算法步骤

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

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

Python

class Solution:
    def MySort(self , arr ):
        # write code here
        for i in range(len(arr)):
            
            # 记录前面已有序元素的位置
            preIndex = i - 1
            # 获取当前要插入的元素
            current = arr[i]
            
            # 第一个元素默认有序，依次和前面的比较，先和最大，比他小就让大的往后移
            while preIndex >= 0 and arr[preIndex] > current:
                # 第一次循环时 arr[preIndex+1] 就是 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;
    }
}

二分排序（优化插入排序）

二分查找是在有序的数列里查找某一个元素
而插入排序的时候，前面排好的部分都是有序的，所以可以在插入的时候使用二分搜素的思想找到相应位置进行插入。

二分搜索Java

    public static int binarySearch(int[] arrayA, int key) {
        int low = 0;
        int high = arrayA.length - 1;
        int mid = 0;

        while (low <= high) {
            mid = (low + high) / 2;

            if (key < arrayA[mid]) {
                high = mid - 1;
            } else if (key > arrayA[mid]) {
                low = mid + 1;
            } else
                break;
        }

        return mid;
    }

二分排序Java

    public static int[] binarySort(int[] array) {

        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int low = 0;
            int high = i - 1;
            int mid = -1;

            while (low <= high) {
                mid = (low + high) / 2;

                if (temp < array[mid]) {
                    high = mid - 1;
                } else { // temp >= array[mid])
                    low = mid + 1;
                }
            }

            // 将low下标以后的元素全部向后移一位
            for (int j = i - 1; j >= low; j--) {
                array[j + 1] = array[j];
            }

            if (low != i)// 若待插入元素的插入位置不等于当前位置，则插入
                array[low] = temp;
        }

        return array;
    }

Python

def insertion_sort2(arr):
    '''
    二分法插入排序原理：
    外层循环控制循环次数，第二层确定待插入的位置与范围，最后一层循环向后挪动元素的位置，插入待插入的元素。
    count 和 print(arr)为了便于观察过程，可省略。
    '''
    for i in range(1, len(arr)):
        tem = arr[i]
        left = 0
        right = i-1
        count = 0
        
        #待插入的值与已排序区域的中间值比较，不断缩小区域范围，直到left和right相遇。
        while left <= right:
            count += 1
            mid = (left+right)//2
            if arr[i] < arr[mid]:
                right = mid-1 
            else:
                left = mid+1
                
        #当left和right相遇的时候，待插入的位置其实就是left的位置，此时要将left到有序序列的最后一个元素都向后移动一个位置，才能插入元素。
        #这里一定要用left-1,否则当left的位置就是有序序列的最后一个位置时，j取不到值，后面的元素会被这个位置的元素值覆盖。
        for j in range(i-1, left-1 ,-1):
            arr[j+1] = arr[j]
            
        #插入元素
        if left != i:
            arr[left] = tem
            print(arr)
    print('共循环%i次' % count)
    return arr
}