标签：sort 思想 元素 lst 算法 放置 序列 排序

一、插入排序

1、直接插入排序

　　　　基本思想：类似抓扑克牌，待排序元素在已排序的序列中从后往前遍历，遇到小于他的元素向后移一位，直至遇到小于或等于他的元素，在其后插入即可

2、希尔排序(是对直接插入排序的一种改进)

二、交换排序

　　1、冒泡排序

　　　　基本思想：相邻的两个元素进行两两比较，如果出现逆序，则小的元素向前移动

　　　　代码实现：

　　　　　　

 1 def bubble_sort(lst):
 2     """冒泡排序"""
 3     n = len(lst)
 4     for i in range(n):
 5         for j in range(1, n-i):
 6             if not lst[j-1] > lst[j]:
 7                 # print("{}小于{},无需替换".format(lst[j-1], lst[j]))
 8                 continue
 9             lst[j-1], lst[j] = lst[j], lst[j-1]
10 
11     return lst

　　2、快速排序(是对冒泡排序的一种改进)

　　　　基本思想：找到一个基准元素，比其小的元素放置左边，反之不小于他的元素放置右边，由此分成左右两个区间，对左右两个区间进行递归，重复以上操作，最终形成有序序列

　　　　代码实现：

1 def quick_sort(lst):
2     """快速排序"""
3     n = len(lst)
4     if n <= 1:
5         return lst
6     baseline = lst[0]
7     left = [lst[i] for i in range(1, len(lst)) if lst[i] < baseline]
8     right = [lst[i] for i in range(1, len(lst)) if lst[i] >= baseline]
9     return quick_sort(left) + [baseline] + quick_sort(right)

 

三、选择排序

　　1、直接选择排序

　　　　基本思想：从待排序记录中找到最小或最大的元素，放置起始位置，然后再从剩下的序列中找到最值，放置在已排序的序列末尾，直至待排序记录为空

　　　　代码实现：

1 def select_sort(lst):
2     """直接选择排序"""
3     for i in range(len(lst)):
4         res = min(lst)
5         yield res
6         lst.remove(res)

　　2、堆排序

　　　　基本思想：堆是python中一种基本的数据结构，heapq[0]永远是序列中最小的元素

　　　　代码实现：

1 def select_sort(lst):
2     """堆排序"""
3     heapq.heapify(lst)
4     for i in range(len(lst)):
5         yield heapq.heappop(lst)

四、归并排序

　　1、二路归并排序

　　　　基本思想：先拆再合：带有N个元素的待排序序列分成N个子序列 ，相邻的序列进行两两合并，在合并的过程中，较小的元素放置左边，较大的元素放置右边

以上总结仅代表个人理解，可能存在不足，还请批评指正

标签：sort,思想,元素,lst,算法,放置,序列,排序
From： https://www.cnblogs.com/shixiaogu/p/16716138.html