算法思想
直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的纪录(这里我们记为key)的大小逐个插入到一个已经排好序的有序序列中,直到所有的纪录插入完为止,得到一个新的有序序列。
实现
1 | def InsertionSort(arr): |
备注:算法实现参照《算法导论》中的内容,注意书中伪码的边界值处理和具体实现的区别。
arr:待排序数组。
key:待比较元素,arr[i]。
arr[0…i-1]:已经排好序的数组。
j:已经排好序的数组的索引。
时间复杂度:O(n^2)
直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的纪录(这里我们记为key)的大小逐个插入到一个已经排好序的有序序列中,直到所有的纪录插入完为止,得到一个新的有序序列。
1 | def InsertionSort(arr): |
备注:算法实现参照《算法导论》中的内容,注意书中伪码的边界值处理和具体实现的区别。
arr:待排序数组。
key:待比较元素,arr[i]。
arr[0…i-1]:已经排好序的数组。
j:已经排好序的数组的索引。
时间复杂度:O(n^2)