67Python排序算法——插入排序

67 Python 排序算法 ——插入排序 一、插入排序简介 插入排序(Insertion Sort)，也被称为直接插入排序，是一种常见的排序算法。 插入排序是将元素列表中未排序的数据依次插入到有序序列中。从元素列表的第一个数据开始(将第一个数据视为已排序序列)，按顺序将后面未排序的数据依次插入到前面已排序的序列中。对每一个未排序数据进行插入，是将该数据依次与相邻的前一个数据进行比较，如果顺序错误则交换位置，直到不需要交换则该数据插入完成。 插入排序的原理类似于玩扑克牌时，手动抓牌和排序，每抓一张新牌都按顺序插入到已有的牌中。 动态演示 二、插入排序原理 插入排序的原理如下： 1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。 2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。 3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。 三、插入排序的步骤： 插入排序是一种简单直观的排序算法，具体步骤如下： 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或等于新元素的位置 将新元素插入到该位置后 重复步骤2-5，直到所有元素都被插入到了合适的位置 四、插入排序举例：对以下列表进行插入排序 l = [3, 2, 1, 5, 4] $$