Python中怎样实现插入排序

Python中怎样实现插入排序，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

插入排序（Insertion Sort）的算法时间复杂度也是O(n^2)，但思路与冒泡排序以及选择排序截然不同

插入排序有点类似于日常生活中的"打扑克牌"

插入排序思路：维持好一个已排序好的子列表，其位置始终在列表的前部，然后逐步扩大这个子列表直到全表

简单来说：对于一个输入的无序表，分成两个部分，前部分是已排序子列表，后部分是待排序数据。每一趟插入排序都从后面的数据找一个插入到前面已排序的子列表中（要找到其合适位置），最后完成全部数据排序

步骤：

1. 第一趟插入排序：前面的子列表仅包含一个元素，待插入数据从第二个元素开始。将第二个元素插入到子列表的合适位置，完成两个元素的排列

2. 第二趟插入排序：将第三个元素插入到子列表合适位置，完成前三个数据项的排序

   ……

3. 第n-1趟插入排序：最后一个数据插入到子列表合适位置，完成所有元素排序

插入排序的数据比对主要在于寻找待插入元素的合适位置

• 最差情况：比对要与子列表所有元素发送--O(n^2)

• 最好情况：每一趟插入排序只需发生一次比对--O(n)

插入排序找到合适位置的具体思路：

将待插入元素取出（存储在一个变量中）空出这个位置（记录这个位置），将这个取出的元素与子列表从后向前的元素逐个比对，若待插入元素小，则将子列表元素向后移动一位……直到整个子列表比对完或者待插入元素大于当前子列表元素则停止循环。将待插入元素插入当前位置

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注行业资讯频道，感谢您对的支持。