排序算法基本思想及实现

一、插入排序

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个子序列 ,相邻的序列进行两两合并,在合并的过程中,较小的元素放置左边,较大的元素放置右边

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

作者:默玖 原文地址:https://www.cnblogs.com/shixiaogu/p/16716138.html

%s 个评论

要回复文章请先登录注册