如何用Python编写插入排序算法?
插入排序是一种简单直观的排序算法,它的思想是将待排序的数组分为有序部分和无序部分,每次从无序部分中选择一个元素插入到有序部分的正确位置。插入排序算法的实现通常通过多次比较和交换元素来实现,时间复杂度为O(n^2)。
下面我们就来看一下用Python语言如何编写插入排序算法,以及具体的代码示例。
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] # 当前待插入元素 j = i - 1 # 有序部分的最后一个元素索引 # 将比key大的元素都向后移动一位 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # 将key插入正确位置 return arr
以上是插入排序算法的具体实现代码。在主函数中,我们需要传入一个待排序的数组arr,并将排序后的结果返回。
在算法的主要循环中,我们从第二个元素开始,将其作为待插入元素key。然后,我们将key与有序部分的最后一个元素进行比较,将比key大的元素向后移动一位,直到找到key的正确位置。最后,我们将key插入到正确位置。
接下来,我们可以测试一下这个插入排序算法。
arr = [9, 5, 1, 6, 8, 2] sorted_arr = insertion_sort(arr) print(sorted_arr)
输出结果为:
[1, 2, 5, 6, 8, 9]
可以看到,通过插入排序算法,我们成功地将输入的数组按照升序排列。
总结起来,使用Python编写插入排序算法并不复杂。我们只需要理解插入排序的基本思想,然后根据思想实现相应的代码即可。当然,为了使代码更加健壮和通用,我们还可以对边界情况进行处理,例如空数组或只有一个元素的数组。
希望本文能对您理解和掌握插入排序算法有所帮助!
以上就是如何用Python编写插入排序算法?的详细内容,更多请关注php中文网其它相关文章!
已抢65719个
抢已抢31299个
抢已抢17270个
抢已抢8778个
抢已抢11342个
抢已抢23512个
抢