七种排序算法的python3实现
本文介绍七种排序算法以及Python3的实现，分别是冒泡排序，选择排序，插入排序，希尔排序，归并排序，堆排序以及快速排序。
1、冒泡排序
通过两次迭代，从第一个数开始进行比较，每次将最大的数移动到最右边，就好像气泡从左边移动到右边一样，因此获名“冒泡”。
冒泡排序的过程如下：
1、比较相邻的两个元素，如果左边大于右边，则进行交换，否则继续迭代
2、对每一个相邻元素都做步骤1操作，直至一轮迭代结束，最后一个元素就是最大的数
3、针对以上未排序的部分，重复1-2步骤，每次需要排序的数列的长度逐渐减小直到变为1
冒泡排序对n个元素，需要O（n²)的比较次数，最坏情况时，交换次数也是这么多，因此冒泡排序是一种效率比较低的排序算法。
# -*- coding:utf-8 -*-
class BubbleSort:
def __init__(self,m=[]):
self.m=m
def get_sort(self):
return self.m
def bubble_sort(self):
#两次for循环，最多进行(n-1)+(n-2)+....+(2-1)次比较以及交换
for i in range(len(self.m)):
for j in range(len(self.m)-i-1):
if self.m[j]>self.m[j+1]:
self.m[j],self.m[j+1]=self.m[j+1],self.m[j]
l=[3,5,1,99,2]
l_sort=BubbleSort(l)
l_sort.bubble_sort()
print(l_sort.get_sort())
2、选择排序
通过两次迭代，每次通过一次内层迭代，找到当次循环的最大值，并将其序号index记录，并与当次循环最右边位置的值进行交换。这样最多经过n-1次交换，就将所有值都排好了。
与冒泡相比，二者的比较次数是相同的，但是选择排序的交换次数大大减少。因为对于内层迭代而言都是只记录而不交换，只有在外层才进行交换。
选择排序的交换操作介于0和 (n-1)次之间。选择排序的比较操作为n(n-1)/2次。
选择排序的过程如下：
1、比较相邻的两个元素，如果左边大于右边，则记录将左边的值赋值给index，否则继续迭代
2、在内层迭代中重复步骤1，直到找到最大值的index
3、将index位置的值与数列的最后一个元素进行交换
4、重复1-3的步骤，直至数列的长度为1
#-*-coding:utf-8-*-
class SelectSort:
def __init__(self,m):
self.m=m
def get_sort(self):
return self.m
def select_sort(self):
for i in range(len(self.m)):
max_index=0
for j in range(len(self.m)-i):
if self.m[j]>self.m[max_index]:
max_index=j#每次将最大的值的编号值传给index，但不进行交换。比较的次数与冒泡相当，当时交换的次数只有n次
self.m[len(self.m)-i-1],self.m[max_index]=self.m[max_index],self.m[len(self.m)-i-1]
l=[3,5,1,99,2]
l_sort=SelectSort(l)
l_sort.select_sort()
print(l_sort.get_sort())
3、插入排序
向已经排好序的数列插入一个数，而得到一个新的有序数列。
我们得到第一个有序数列的方式，是我们将第一个元素认为是一个数列，那么他必然是有序的。我们只对相邻的元素做比较，逐个推进式比较。在从后向前扫描过程中，需要反复把已经排序的的元素逐步向后移，为新元素提供插入空间。
插入排序的过程如下：
1、从第一个元素开始，该元素认为已经被排序
2、取出下一个元素，在已经排序的的元素序列中从后向前扫描
3、如果该元素大于需要被排序的元素，则将该元素与需要被排序的元素交换而移动到下一位
4、重复第3步，直到在已经排序的列表中找到小于需要被排序的元素
5、将该新元素插入到该位置之后
6、重复2-5的步骤
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需n-1次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有（1/2）n(n-1)次。插入排序的赋值操作是比较操作的次数减去n-1次，（因为n-1次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为O（n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。
#-*-coding:utf-8-*-
class InsertSort:
def __init__(self,m):
self.m=m
def get_sort(self):
return self.m
def insert_sort(self):
for i in range(1,len(self.m)):#默认第一个元素已经是排好序的元素，因此从第二个元素开始
while i>=1:
if self.m[i]<self.m[i-1]:
self.m[i],self.m[i-1]=self.m[i-1],self.m[i]
# 每次插入的时候都会遍历前面已经排好序的部分，逐个插入，直到满足while的条件
i-=1
l=[5,1,7,3,2,1,22,8,4,9,99,66,3]
l_sort=InsertSort(l)
l_sort.insert_sort()
print(l_sort.get_sort())
在进行向前迭代的时候当然也可以使用for，而不使用while，代码如下：
def inset_sort(list):
for i in range(1,len(list)):
for j in range(i,0,-1):
if list[j]<list[j-1]:
list[j],list[j-1]=list[j-1],list[j]
return list
l=[5,1,7,3,2,1,22,8,4,9,99,66,3]
print(inset_sort(l))
4、希尔排序
希尔排序也称递减增量排序算法，是插入排序的优化版本或者说是冒泡排序的优化版本，因为当gap为1的时候，实际上就变成了插入排序，在插入排序中，我们对每次比较的步长gap都是1。步长是希尔排序的核心思想，只要最终步长为1任何步长序列都是可以的，已知的最好步长序列是由Sedgewick提出的 1，5，19，41，109，…
希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
希尔排序的过程如下：
1、从第一个元素开始，该元素认为已经被排序
2、设置步长值gap
3、取出下一个元素，在已经排序的元素序列中从后向前扫描
4、如果该元素大于需要被排序的元素，则将该元素与被需要排序的元素交换而移动到下一位
5、重复第4步，直到在已经排序的列表中找到小于需要被排序的元素
6、将该新元素插入到该位置之后
7、重复2-6的步骤，直到最后一次比较，也就是第二个元素与第一个元素比较
8、将gap值减半，递归3-7步骤，最后一次比较的时候gap=1，当gap<1时，结束递归
#-*-coding:utf-8-*-
class ShellSort:
def __init__(self,m):
self.m=m
def get_sort(self):
return self.m
def shell_sort(self):
gap=len(self.m)//2#以数列的一半为初始的gap值
while gap>=1:#保证gap的值始终大于1
for i in range(0,len(self.m)-gap,gap):#每次增量为gap，而我们在插入时候，，每次的增量为1
while i >=0:#为了保证每次可以跟前面已经排序的整个数列进行比较，我们再加一个迭代的条件
if self.m[i]>self.m[i+gap]:
self.m[i],self.m[i+gap] = self.m[i+gap],self.m[i]
i -= gap
gap = gap//2
l=[4,1,4,7,3,2,66,6,9,4,12,35,6899,2]
l_sort=ShellSort(l)
l_sort.shell_sort()
print(l_sort.get_sort())
5、归并排序
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并排序是对已经排序好的数据进行排序，但是与shell的方式是不同的，归并是实际分割了数列，产生了新的存储空间，而shell只是概念上分割，并没有产生新的存储空间。
归并算法是将数列进行逐级对半分割，一直分割到最小粒度也就是两边都是一个元素或者一半是一个元素，一半是两个元素。前面shell排序也说到，如果是只有一个元素，当然一个元素肯定是排好序的，然后将两半的元素进行比较和交换，然后递归。
归并排序的过程如下：
1、将数列对半分割成left和right两个新的数列，而后递归分割，一直到left长度为1或者 right的长度为1
2、将left和right两边的数列元素从第一个开始比较，将比较小的值赋值给一个空的数组result
3、当一次比较完成后，将left或者right中剩余的值赋值给result
4、将result的值返回给上一层递归函数
5、重复以上2-4的步骤
归并算法的效率是O（n log n)
#-*-coding:utf-8-*-
class MergeSort:
def __init__(self,m):
self.m=m
def get_sort(self):
return self.merge_sort(self.m)
#使用递归的方式，将数列拆分，直到最小的粒度是1
def merge_sort(self,s):
if len(s)==1:
return s
else:
#将list每次截取一半出来，分别放在左右两个list中，直至最小粒度为1
mid=len(s)//2
left=self.merge_sort(s[:mid])
right=self.merge_sort(s[mid:])
return self.merge_list(left,right)
#排序
def merge_list(self,left,right):
i,j=0,0
result=[]
#每次将left数列和right数列从第一个元素开始比较，将最小的数放在result
while i<len(left) and j<len(right):
if left[i]>right[j]:
result.append(right[j])
j+=1
else:
result.append(left[i])
i+=1
#每次while循环结束以后，因为有可能出现虽然left中已经没有数，但是right中还有很多，当然也可能是反过来；
# 下面就是把剩下的值加入到result中，剩下的值必然是这次比较中最大的，因此都放在最右边。
result = result + left[i:]
result = result + right[j:]
return result
m=[4,1,3,99,5,22,8,5,2,1,3]
s_sort=MergeSort(m)
print(s_sort.get_sort())
6、堆排序
堆排序将一个数列构造成一个完全二叉树，再将完全二叉树构造成大顶堆或者小顶堆的形式。
这个时候我们的堆的根节点就是最大值所在位置，然后将该值与最后一个元素进行调换，调换之后再将堆重新构造成大顶堆，如此进行迭代就完成堆排序。
堆排序过程如下：
1、定义大顶堆构造函数build_heap，迭代调用max_heap函数，由下向上构造大顶堆。
这步并不难，方法也很多。但是如果我们想为后来第三步做铺垫，这步最好是有一个独立的构造顶堆的函数max_heap
2、将大顶堆的根节点与完全二叉树的最后一个元素交换
3、将交换过后的二叉树进行重构大顶堆。
4、重复2-3步骤，直到最后一对元素（index分别是0和1）比较和交换
基于以上，我们也能发现，我们需要不断利用max_heap进行大顶堆的构造。实际上我们在每次执行max_heap函数时，都是调整了一个二叉树单分支的节点，**这个调整是从上向下的，我们需要把最大值放在最上面，因此我们借助递归来完成。**当该二叉树分支被调整后，**为了依然保证这个分支的值依然也都满足大顶堆的性质，我们需要向下进行递归来进行修正。**也就是说，**我们的数据流有两个方向，初始时，我们通过调用max_heap从下至上遍历每个节点来形成一个大顶堆，第二个方向是当一个节点的值被改变，我们再从该节点开始，从上至下进行递归修正，来保持大顶堆的形态。**简而言之，我们的算法是迭代中包括着递归，每次形态被改变后，都会进行递归修正。
堆排序的平均时间复杂度是O（n log n)
#-*-coding:utf-8-*-
class HeapSort:
def __init__(self,m):
self.m=m
def get_sort(self):
return self.m
def build_heap(self):
"""构建一个大顶堆或者小顶堆，这里以大顶堆为例"""
"""根据完全二叉树的性质，根的index为0。最后一个叶的根节点为len//2-1，也就是总长的1/2减去1"""
for i in range((len(self.m) // 2) - 1, -1, -1):#从最后一个叶的根节点开始从下往上构建大顶堆
self.max_heap(len(self.m), i)
def max_heap(self,heap_size,index):
"""这里是一个独立的，创建一个大顶堆的函数，而不涉及循环。"""
"""本函数最精巧的地方在于当一个顶堆被改变之后，下面会递归对这个顶堆之下的部分进行重新判断，进而形成一个新的大顶堆的二叉树"""
"""max_heap函数在两个地方被调用，一个是在构建大顶堆时候，从build_heap这个入口调用；还有就是在顶堆被调整后，从heao_sort这个入口调用重新形成完整大顶堆"""
left_child = 2 * index + 1
right_child = left_child + 1
if left_child < heap_size and self.m[left_child] > self.m[index]:
largest = left_child
else:
largest = index
if right_child < heap_size and self.m[right_child] > self.m[largest]:
largest = right_child
if largest != index:
self.m[largest], self.m[index] = self.m[index], self.m[largest]
# 以上的代码保证largest肯定是index，所以有了下面这个递归，保证每次如果二叉树的根节点被改变，则会向下去重新比较这个分支中所有的值，而形成新的大顶堆
self.max_heap(heap_size, largest)
def heap_sort(self):
"""堆排序主入口"""
# 首先将列表调整为大顶堆
self.build_heap()
heap_size = len(self.m)
# 调整堆中的第一个元素（也就是最大值）和最后一个元素交换，然后再将剩余的堆进行重新调整为大顶堆
for i in range(len(self.m) - 1, 0, -1):
self.m[i], self.m[0] = self.m[0], self.m[i]
heap_size -= 1#最后一个元素在比较完之后，就是被排好序的，下面往上去接着比较和交换。
self.max_heap( heap_size, 0)
l=[4,1,5,9,22,1,3,2,8]
l_sort=HeapSort(l)
l_sort.heap_sort()
print(l_sort.get_sort())
7、快速排序（quick_sort）
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。
快速排序是固定选择数列中第一个值（当然你选择别的位置的值也可以）作为key，将比key小的值放在左边，比key大的值放在右边。而后进行迭代，一直到最小的部分，最后形成一个有序的数列。对于迭代而言，数组本身是不变化的，因为虽然我们再进行多层迭代，但是我们作用的依然是一个数组，也就是说只是指针的改变，没有新建存储空间。
快排的过程如下：
1、选择数列中的第一个值，赋值给key,并将数列中第一个值的下标赋值给left，最后一个值的下标赋值给right
2、定义i和j两个参数，二者的值与left和right的值相同。
3、以i的值为编号参数，遍历数列的值，当对应的值小于等于key，则i的值一直增加；当i位置的值大于key，则将该值与当前j位置的值进行替换，j–
4、以j的值为编号参数，遍历数列的值，当对应的值大于等于key，则j的值一直减小；当j位置的值小于key，则将该值与当前i位置的值进行替换，i++
5、以上迭代结束后，i的值已经与j的值相同，这时候将key赋值给i位置的值，就完成了一轮迭代。
6、分别在当前i位置往左移动一位，往右移动一位，形成两个新的数列，分别进行递归。
我们可以发现，每一轮迭代完成之后，虽然数列可能还是乱序的，但是key的位置就是他应该在的位置。
快速排序O（n log n)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
#-*-coding:utf-8-*-
class QuickSort:
"""快排是选择数组的第一个值的作为中间值key，将一个数列中比其小的值放在左边，比其大的值放在右边"""
"""完成一次之后快排之后，再对两边的值进行逐次递归，然后得到一个有序的数列"""
def __init__(self,m):
self.m=m
def get_sort(self,left,right):
return self.quick_sort(left,right)
def quick_sort(self,left,right):
#这里涉及到递归，为了保证left和right的值都合法，因此在被递归的函数的开始就进行条件限制
#如果是出现不合法的条件，那么直接return，就进入到上一级递归。
if left<0 or right<0 or right<=left:
return self.m
key=self.m[left]
i,j=left,right
#在快排中多次用到了相同的限定条件，比如i<j，这是由于每次迭代虽然有包含和被包含的关系，但是在具体的迭代中，如果出现违法条件，最外层的条件是没发限定的。
while 0<=i<j:
#从右向左逐渐比较右边比key小的值，发现该值就把他赋值给i所在位置的值，因为可以确定i位置的值小于了key，所以i++,跳过目前位置
while self.m[j]>=key and i<j:
j-=1
if self.m[j]<key:
self.m[i]=self.m[j]
i+=1
#从左向右逐渐比较左边比key大的值，发现该值就把他赋值给j所在位置的值，因为可以确定j位置的值大于了key，所以j--,跳过目前位置
while self.m[i]<=key and i<j:
i+=1
if self.m[i]>key:
self.m[j]=self.m[i]
j-=1
#逐渐迭代直到最小组合
self.m[i]=key
self.quick_sort(left,i-1)
self.quick_sort(i+1,right)
return self.m
#L=[4,1,4,7,44,32,9,10]
L=[67,23,89,35,28,90,10,24]
left,right=0,len(L)-1
#L=[67,23,89,35,28,90,10,24]
L_sort=QuickSort(L)
print(L_sort.get_sort(left,right))
算法效率
借用网上的图来列举这七种排序算法的效率。
参考
*-冒泡排序算法
*-选择排序算法
*-插入排序算法
*-希尔排序算法
*-归并排序算法
*-堆排序算法
*-快速排序算法
排序算法详解
经典排序算法总结