域名注册的网站有哪些怎么做网页
定义
插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后
挪位,为最新元素提供插入空间。
特性
1.时间复杂度
最好情况就是全部有序,此时只需遍历一次,最好的时间复杂度为O ( n ) O(n)O(n)
最坏情况全部反序,内层每次遍历已排序部分,最坏时间复杂度为O ( n 2 ) O(n^2)O(n2)
综上,因此直接插入排序的平均时间复杂度为O ( n 2 ) O(n^2)O(n2)
2.空间复杂度
辅助空间是常量
平均的空间复杂度为:O ( 1 ) O(1)O(1)
3.算法稳定性
相同元素的前后顺序是否改变
插入到比它大的数前面,所以直接插入排序是稳定的
举例说明原理
原理文字太枯燥了,以下用数组3,4,6,7,9,1,2,5为例
从小到大排序
1、首先选择第一个数,由于第一个数必然有序,丨前面为有序组、后面为无序。
3 | 6 7 9 1 2 5
2、取出无序部分的首个,在有序部分从后向前比较,插入到合适的位置
3 6 | 7 9 1 2 5
3、重复第2步直到无序部分全部插入有序,7和9也是一次比较就可以插入
3 6 7 | 9 1 2 5
3 6 7 9 | 1 2 5
4、1就需要多次比较,注意是多次比较,直接插入,不是比较一次插入一次(与冒泡不同)
3 6 7 9 口 | 2 5
temp = 1
可以看到先把1放到temp中,与前面比较,最后放到合适位置
1 3 6 7 9 | 2 5
5、后面就重复上面操作
1 2 3 5 6 7 9
以下为C语言代码并附上代码解析带图
一:C语言代码
#include <stdio.h>// 函数声明
void insertion_sort(int arr[], int len);int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度insertion_sort(arr, len); // 调用插入排序函数// 打印排序后的数组for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}return 0;
}
void insertion_sort(int arr[], int len) {for (int i = 1; i < len; i++){int temp = arr[i];int j = i;while (j > 0 && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}arr[j] = temp;}
}
二:代码解析
1、我们逐句分析,先看第一句,很简单从数组地址为1开始遍历
3 | 6 7 9 1 2 5
for (int i = 1; i < len; i++)
2、将数放进temp中,地址存进j中
int temp = arr[i];int j = i;
3 口 | 7 9 1 2 5
temp = 6
6所在地址1存进j中
3、前面还有数并且取出的数小于有序组最后一个
while (j > 0 && arr[j - 1] > temp)
3 7 9 口| 2 5
temp = 11前面有数并且9>1
4、前面比他大的数往后移;接着地址减小再进while
arr[j] = arr[j - 1];j--;
3 7 口 9| 1 2 5
temp = 1
5、最终放到合适地方
arr[j] = temp;
口 3 7 9 | 2 5
temp = 1放下以后:1 3 7 9 | 2 5
如下是用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的 Python 程序:
#待排序序列
list = [10, 14, 19, 27, 33, 35, 42, 44]
def insertion_sort():length = len(list)# 从第 2 个元素(下标为 1)开始遍历for i in range(1,length):# 记录要插入的目标元素insert_elem = list[i];position = i# 从 position 向前遍历,找到目标元素的插入位置while position > 0 and list[position -1] > insert_elem:#position 处的元素向后移动一个位置list[position] = list[position -1];position = position-1# 将目标元素插入到指定的位置if position != i:list[position] = insert_elem
insertion_sort()# 输出已排好序的序列
for i in list:print(i,end=" ")