基于python的七种经典排序算法.doc

基于python的七种经典排序算法一、排序的基本概念和分类所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序的稳定性：经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。内排序和外排序内排序：排序过程中，待排序的所有记录全部放在内存中外排序：排序过程中，使用到了外部存储。通常讨论的都是内排序。影响内排序算法性能的三个因素： 时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数 空间复杂度：主要是执行算法所需要的辅助空间，越少越好。 算法复杂性。主要是指代码的复杂性。根据排序过程中借助的主要操作，可把内排序分为： 插入排序 交换排序 选择排序 归并排序按照算法复杂度可分为两类： 简单算法：包括冒泡排序、简单选择排序和直接插入排序 改进算法：包括希尔排序、堆排序、归并排序和快速排序以下的七种排序算法只是所有排序算法中最经典的几种，不代表全部。二、 冒泡排序冒泡排序（Bubble sort）：时间复杂度O(n2)交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。其实现细节可以不同，比如下面3种：1. 最简单排序实现:bubble_sort_simple2. 冒泡排序:bubble_sort3. 改进的冒泡排序:bubble_sort_advance#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 冒泡排序算法class SQList: def _init_(self, lis=None): self.r = lis def swap(self, i, j): 定义一个交换元素的方法，方便后面调用。 temp = self.ri self.ri = self.rj self.rj = temp def bubble_sort_simple(self): 最简单的交换排序，时间复杂度O(n2) lis = self.r length = len(self.r) for i in range(length): for j in range(i+1, length): if lisi lisj: self.swap(i, j) def bubble_sort(self): 冒泡排序，时间复杂度O(n2) lis = self.r length = len(self.r) for i in range(length): j = length-2 while j = i: if lisj lisj+1: self.swap(j, j+1) j -= 1 def bubble_sort_advance(self): 冒泡排序改进算法，时间复杂度O(n2) 设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。 对于比较规整的元素集合，可提高一定的排序效率。 lis = self.r length = len(self.r) flag = True i = 0 while i = i: if lisj lisj + 1: self.swap(j, j + 1) flag = True j -= 1 i += 1 def _str_(self): ret = for i in self.r: ret += %s % i return retif _name_ = _main_: sqlist = SQList(4,1,7,3,8,5,9,2,6) # sqlist.bubble_sort_simple() # sqlist.bubble_sort() sqlist.bubble_sort_advance() print(sqlist)三、简单选择排序简单选择排序（simple selection sort）:时间复杂度O(n2)通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1=i lisj: minimum = j if i != minimum: self.swap(i, minimum) def _str_(self): ret = for i in self.r: ret += %s % i return retif _name_ = _main_: sqlist = SQList(4, 1, 7, 3, 8, 5, 9, 2, 6, 0) sqlist.select_sort() print(sqlist)四、直接插入排序直接插入排序（Straight Insertion Sort）:时间复杂度O(n2)基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 直接插入排序class SQList: def _init_(self, lis=None): self.r = lis def insert_sort(self): lis = self.r length = len(self.r) # 下标从1开始 for i in range(1, length): if lisi temp and j = 0: lisj+1 = lisj j -= 1 lisj+1 = temp def _str_(self): ret = for i in self.r: ret += %s % i return retif _name_ = _main_: sqlist = SQList(4, 1, 7, 3, 8, 5, 9, 2, 6, 0) sqlist.insert_sort() print(sqlist)该算法需要一个记录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为O(n)。然而，这基本是幻想。五、希尔排序希尔排序（Shell Sort）是插入排序的改进版本，其核心思想是将原数据集合分割成若干个子序列，然后再对子序列分别进行直接插入排序，使子序列基本有序，最后再对全体记录进行一次直接插入排序。这里最关键的是跳跃和分割的策略，也就是我们要怎么分割数据，间隔多大的问题。通常将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过：increment = int(increment/3)+1来确定“增量”的值。希尔排序的时间复杂度为：O(n(3/2)#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 希尔排序class SQList: def _init_(self, lis=None): self.r = lis def shell_sort(self): 希尔排序 lis = self.r length = len(lis) increment = len(lis) while increment 1: increment = int(increment/3)+1 for i in range(increment+1, length): if lisi = 0 and temp = 0: self.heap_adjust(i, length-1) i -= 1 # 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。 j = length-1 while j 0: # 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处 self.swap(0, j) # 将发生变化的序列重新构造成大顶堆 self.heap_adjust(0, j-1) j -= 1 def heap_adjust(self, s, m): 核心的大顶堆构造方法，维持序列的堆结构。 lis = self.r temp = liss i = 2*s while i = m: if i m and lisi = lisi: break liss = lisi s = i i *= 2 liss = temp def _str_(self): ret = for i in self.r: ret += %s % i return retif _name_ = _main_: sqlist = SQList(4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22) sqlist.heap_sort() print(sqlist)堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。其初始构建堆时间复杂度为O(n)。正式排序时，重建堆的时间复杂度为O(nlogn)。所以堆排序的总体时间复杂度为O(nlogn)。堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。七、归并排序归并排序（Merging Sort）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 归并排序class SQList: def _init_(self, lis=None): self.r = lis def swap(self, i, j): 定义一个交换元素的方法，方便后面调用。 temp = self.ri self.ri = self.rj self.rj = temp def merge_sort(self): self.msort(self.r, self.r, 0, len(self.r)-1) def msort(self, list_sr, list_tr, s, t): temp = None for i in range(0, len(list_sr) if s = t: list_trs = list_srs else: m = int(s+t)/2) self.msort(list_sr, temp, s, m) self.msort(list_sr, temp, m+1, t) self.merge(temp, list_tr, s, m, t) def merge(self, list_sr, list_tr, i, m, n): j = m+1 k = i while i = m and j = n: if list_sri list_srj: list_trk = list_sri i += 1 else: list_trk = list_srj j += 1 k += 1 if i = m: for l in range(0, m-i+1): list_trk+l = list_sri+l if j = n: for l in range(0, n-j+1): list_trk+l = list_srj+l def _str_(self): ret = for i in self.r: ret += %s % i return retif _name_ = _main_: sqlist = SQList(4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23) sqlist.merge_sort() print(sqlist) 归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。八、快速排序快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n)。快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。#!/usr/bin/env python# -*- :utf-8 -*-# Author: Liu Jiang# Python 3.5# 快速排序class SQList: def _init_(self, lis=None): self.r = lis def swap(self, i, j): 定义一个交换元素的方法，方便后面调用。 temp = self.ri self.ri = self.rj self.rj = temp def quick_sort(self): 调用入口 self.qsort(0, len(self.r)-1) def qsort(self, low, high): 递归调用 if low high: pivot = self.partition(low, high) self.qsort(low, pivot-1) self.qsort(pivot+1, high) def partition(self, low, high): 快速排序的核心代码。 其实就是将选取的pivot_key不断交换，将比它小的换到左边，将比它大的换到右边。 它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。 但在函数调用的过程中，pivot_key的值始终不变。 :param low:左边界下标 :param high:右边界下标 :return:分完左右区后pivot_key所在位置的下标 lis = self.r pivot_key = lislow while low high: while low = pivot_key: high -= 1 self.swap(low, high) while low high and lislow lishigh: self.swap(low, high)if lism lishigh: (high, m)if lism lislow: self.swap(m, low)如果觉得这样还不够好，还可以将整个序列先划分为3部分，每一部分求出个pivot_key，再对3个pivot_key再做一次上面的比较得出最终的pivot_key。这时的pivot_key应该很大概率是一个比较靠谱的值。2. 减少不必要的交换原来的代码中pivot_key这个记录总是再不断的交换中，其实这是没必要的，完全可以将它暂存在某个临时变量中，如下所示：def partition(self, low, high): lis = self.r m = low + int(high-low)/2) if lislow lishigh: self.swap(low, high) if lism lishigh: self.swap(high, m) if lism lislow: self.swap(m, low) pivot_key = lislow # temp暂存pivot_key的值 temp = pivot_key while low high: while low = pivot_key: high -= 1 # 直接替换，而不交换了 lislow = lishigh while low high and lislow = pivot_key: low += 1 lishigh = lislow lislow = temp return low3. 优化小数组时的排序快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：def qsort(self, low, high): 根据序列长短，选择使用快速排序还是简单插入排序 # 7是一个经验值，可根据实际情况自行决定该数值。 MAX_LENGTH = 7 if hig