数据结构&算法实践—插入排序_程序人生

数据结构&算法实践—插入排序

admin

2023-07-31 00:37:11

0次

排序>>选择排序>>选择排序

List:

12	0.概念+示例分析1.插入排序实现

start

基本概念：

维基百科http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

插入排序，简单来说就是每次拿一个新的数，将其插入到有序序列中.

示例：

1	[8, 4, 3, 1, 6, 9, 2, 7]

index- 1 #从第二个数开始

1	move 1 , change-> [4, 8, 3, 1, 6, 9, 2, 7] #移动一次，插入

index- 2

1	move 2 , change-> [3, 4, 8, 1, 6, 9, 2, 7] #移动两次，插入

index- 3

1	move 3 , change-> [1, 3, 4, 8, 6, 9, 2, 7]

index- 4

1	move 1 , change-> [1, 3, 4,6, 8, 9, 2, 7]

index- 5

1	move 0 , nochange -> [1, 3, 4, 6, 8, 9, 2, 7]

index- 6

1	move 5 , change-> [1,2, 3, 4, 6, 8, 9, 7]

index- 7

123	move 2 , change-> [1, 2, 3, 4, 6,7, 8, 9] [1, 2, 3, 4, 6, 7, 8, 9]

start

插入排序python实现

12345678910111213141516

#!/usr/bin/python# -*- coding:utf-8 -*-#插入排序#@author: wklken@yeah.net def insert_sort(l): print l for i in range(1,len(l)): #从第二个元素开始 value = l[i] while i >= 1 and l[i–1] > value: l[i] = l[i–1] i -= 1 l[i] = value return ll = [8, 4, 3, 1, 6, 9, 2, 7]print insert_sort(l)

改进及优化：

1.加入监控，已排序完成直接退出

2.使用二分插入排序，即，处理某个节点往前插入的时候，使用二分查找插入

上一篇：用Python实现K-近邻算法

下一篇：用Python和Pygame写游戏-从入门到精通（实战一：涂鸦画板1）

数据结构&算法实践—插入排序

相关内容

热门资讯