数据结构和算法-11-插入排序

继续学习简单排序算法中的第三种：插入排序，其实插入排序和选择排序很容易搞混淆。

1.插入排序概念和原理

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据， 在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序 元素进行逐步向后挪位，为最新元素提供插入空间。

2.插入排序图解

上面6个元素，6个步骤。重点来看看d这张图，1先和6交换，然后1和5交换，然后1和4交换，然后1和2交换，这几次交换都是在一个步骤中完成的。

3.插入排序代码实现

python代码实现

# coding:utf-8


def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for i in range(1, n):
        # i = [1, 2, 3, n-1]
        # j 代表内层循环的起始值
        j = i
        # 执行从右边的无序序列中取出第一个元素，即j位置的元素，然后
        # 将其插入到前面的正确位置中
        while j > 0:
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1]  = alist[j-1], alist[j]
                j -=1
            else:
                break

if __name__ == "__main__":
    alist = [17, 20, 93, 54, 77, 32, 45, 226]
    print(alist)
    insert_sort(alist)
    print(alist)

运行结果

[17, 20, 93, 54, 77, 32, 45, 226]
[17, 20, 32, 45, 54, 77, 93, 226]

java代码实现

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args){
        int[] arr = {93, 54, 20, 77, 32, 45};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int j = i;
            while(j > 0){
                if(arr[j] < arr[j-1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                    j -=1;
                }else {
                    break;
                }
            }
        }
    }
}

运行结果：

[93, 54, 20, 77, 32, 45]
[20, 32, 45, 54, 77, 93]