常用排序算法代码实现

本文使用python代码实现了常用的排序算法，并分析复杂度。有关动图以及算法详细介绍可以参考blog

插入排序法

• 基本介绍

  插入排序法依次选择元素，当选择第i位元素时，[0,i]为已排序序列，比较第i+1位元素大小并将其插入[0,i+1]序列中合适的位置。

• 算法复杂度

  插入排序法分为比较与插入（交换）2个过程。

  1. 最好情况：$O(n)$
  2. 最坏情况：$O(N^2)$
  3. 平均情况：$O(N^2)$
  4. 稳定

     def Insert(l):
         for i in range(1,len(l)):
             num=l[i]
             j=i
             while(j>=0):
                 if(l[j]<l[j-1]):
                     l[j],l[j-1]=l[j-1],l[j]
                     j-=1
                 else:
                     break
     
     l=[0,20,3,5,4,65]
     Insert(l)
     print(l)

冒泡排序法

• 基本介绍

  依次遍历元素，并将当前元素i与相邻元素i+1进行排序，遍历一遍后最大元素将位于队尾，下一次只需遍历至n-1位即可。

• 算法复杂度

  1. 最好情况：$O(n)$
  2. 最坏情况：$O(N^2)$
  3. 平均情况：$O(N^2)$
  4. 稳定

     def bubble(l):
         sort=1
         times=1
         while(sort):
             for i in range(len(l)-times):
                 sort=0
                 if(l[i]>l[i+1]):
                     l[i],l[i+1]=l[i+1],l[i]
                     sort=1
             times+=1
     
     l=[0,20,3,5,4,65,1,4,8,5,2]
     bubble(l)
     print(l)

选择排序

• 基本介绍

  依次遍历元素[begin,end]，每次选择最小元素放置于首位begin处，接下来继续遍历[begin+1,end]。

• 算法复杂度

  1. 最好情况：$O(n^2)$
  2. 最坏情况：$O(N^2)$
  3. 平均情况：$O(N^2)$
  4. 不稳定

     def select(l):
         for i in range(len(l)):
             if(min(l[i:])==l[i]):
                 pass
             else:
                 indexs=i+l[i:].index(min(l[i:]))
                 l[i],l[indexs]=l[indexs],l[i]
     
     l=[0,20,3,5,4,65,1,4,8,5,2]
     select(l)
     print(l)

归并排序

• 基本介绍

  合并2个已排序数组的复杂度为$O(N)$，归并排序法采用分治思想，将给定数组不断一分为二，最终得到N个长度为1的子数组，这些子数组可以看作已排序数组，接下来不断合并即可。

• 算法复杂度

  1. 最好情况：$O(n\log n)$
  2. 最坏情况：$O(n\log n)$
  3. 平均情况：$O(n\log n)$
  4. 辅助空间：$O(n)$
  5. 稳定

def merge(l):
    if(len(l)!=1):#list长度不为1时继续分治
        size=int(len(l)/2)
        l1=merge(l[0:size])
        l2=merge(l[size:])
        i=j=0
        res=[]
        while(i!=len(l1) and j!=len(l2)):#排序部分，将2个已经排好序的list合并
            if(l1[i]<l2[j]):
                res.append(l1[i])
                i+=1
            else:
                res.append(l2[j])
                j+=1
        #print(res)
        if(i!=len(l1)):
            res+=l1[i:]
        if(j!=len(l2)):
            res+=l2[j:]
        return res
    else:
        return l

l=[0,20,3,5,4,65,1,4,8,5,2]
a=merge(l)
print(a)

希尔排序

• 基本介绍

  又名缩小增量排序法，给定数组n与增量gap，将数组n分为len(n)//gap个子集，分别为n[i:len(n):gap] (0<=i<gap)，每次将一个子集排序，排完一次后缩小增量gap=gap//2，重复排序步骤，直到gap==0。

• 算法复杂度

  1. 最好情况：$O(n^{1.3})$
  2. 最坏情况：$O(n^2)$
  3. 平均情况：$O(n\log n)\thicksim O(n^2)$
  4. 辅助空间：$O(1)$
  5. 不稳定

     def shell(l,gap):
         gap=min(len(l)//2,gap)#初始化增量
         while(gap!=0):#循环使用插入排序法
             for i in range(0,gap):
                 for j in range(i+gap,len(l),gap):
                     while(j>=0):
                         if(l[j]<l[j-gap]):
                             l[j],l[j-gap]=l[j-gap],l[j]
                             j-=gap
                         else:
                             break
             gap=gap//2#缩小增量
     
     #使用python需要注意边界条件，对于C++，v[i]，当i<0时，越界就直接报错了，但对python，v[i]，i<0还是会能取一个值，排完序就乱了。
     l=[0,20,3,5,4,65,7,3,9,10,15,19,15,18,13,16,23]
     shell(l,5)
     print(l)
     #shell sort简介：https://blog.csdn.net/qq845579063/article/details/51447404

堆排序

• 基本介绍

  堆排序是利用堆这种数据结构而设计的一种排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

步骤：

1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

• 算法复杂度

  1. 最好情况：$O(n\log n)$
  2. 最坏情况：$O(n\log n)$
  3. 平均情况：$O(n\log n)$
  4. 辅助空间：$O(1)$
  5. 不稳定

#图解排序可以参考：https://www.cnblogs.com/chengxiao/p/6129630.html
def heap(l):#构建堆
    node=len(l)//2-1
    for i in range(node,-1,-1):#从第一个有叶节点的节点开始构造成一个大顶堆
        heaps(l,i)

def heaps(l,i):
    node=i #对第i个节点构排序，使节点大于叶节点值
    if(2*i+1>=len(l)):
        return
    leaf1=2*i+1
    leaf2=min(leaf1+1,len(l)-1)
    if(l[node]<l[leaf1] or l[node]<l[leaf2]):
        if(l[node]<l[leaf2] and l[node]>=l[leaf1]):
            l[node],l[leaf2]=l[leaf2],l[node]
        elif(l[node]>=l[leaf2] and l[node]<l[leaf1]):
            l[node],l[leaf1]=l[leaf1],l[node]
        else:
            if(l[leaf2]>=l[leaf1]):
                l[node],l[leaf2]=l[leaf2],l[node]
            else:
                l[node],l[leaf1]=l[leaf1],l[node]
    if(leaf1<=len(l)//2-1):#递归完成子节点的大顶堆
        heaps(l,leaf1)
    if(leaf2<=len(l)//2-1):#递归完成子节点的大顶堆
        heaps(l,leaf2)

def IsEnd(l):
    i=0
    while(i!=len(l)-1):
        if(l[i]-l[i+1]>0):
            return False
        i+=1
    return True

l=[4,6,8,5,9,10,0,2,5,1,6,8,5,4,1,2,3,5,4]
pos=0
heap(l)
while(not IsEnd(l)):
    l[0],l[-1-pos]=l[-1-pos],l[0]
    l1=l[0:-1-pos]
    heap(l1)
    l=l1+l[-1-pos:]
    pos+=1

print(l)

快排

• 基本介绍

  快排每次选中一个基元素，将小于此元素的放置在基元素左边，大于此元素的放置在基元素右边，然后对基元素左右两边的数组分别进行快排，直至数组排序完成。

• 算法复杂度

  1. 最好情况：$O(n\log n)$
  2. 最坏情况：$O(n^2)$
  3. 平均情况：$O(n\log n)$
  4. 辅助空间：$O(1)$
  5. 不稳定

def quick(l,b,e):#b:begin,e:end
    if(b<0 or e>len(l)-1 or b>=e):
        return
    i=b+1
    j=e
    while(i<j):
        while(l[j]>=l[b]):
            if(i>=j):
                break            
            j-=1
        while(l[i]<l[b]):
            if(i>=j):
                break            
            i+=1
        l[i],l[j]=l[j],l[i]
    if(l[i]<l[b]):
        l[b],l[i]=l[i],l[b]
        quick(l,b,i-1)
        quick(l,i+1,e)
    else:
        quick(l,b+1,e)
#http://developer.51cto.com/art/201403/430986.htm
l=[0,20,3,5,4,65,2,5,7,89,2,53,8]
quick(l,0,len(l)-1)
print(l)