算法（10）：排序

  偶然间发现了自己以前写的十种排序算法的代码，现粘贴上来，方便自己日后查阅~ （里面还附赠了和 的实现方法）

• 目录：
  算法：附录
  算法（1）：递归
  算法（2）：链表
  算法（3）：数组
  算法（4）：字符串
  算法（5）：二叉树
  算法（6）：二叉查找树
  算法（7）：队列和堆栈（附赠BFS和DFS）
  算法（8）：动态规划
  算法（9）：哈希表
  算法（10）：排序
  算法（11）：回溯法
  算法（12）：位操作

小伙子我心肠好，再送俩非递归实现~

快速排序的非递归实现
归并排序的非递归实现

#python3
'''
插入排序：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，
算法适用于少量数据的排序；首先将第一个作为已经排好序的，然后每次从后的取出插入到前面并排序；
'''
def insert_sort(ilist):
    for i in range(len(ilist)):
        for j in range(i):
            if ilist[i] < ilist[j]:
                # ilist[i], ilist[j] = ilist[j], ilist[i]
                ilist.insert(j, ilist.pop(i))
                break
    return ilist


'''
希尔排序是第一个突破O(n^2)的排序算法；是简单插入排序的改进版；是把记录按下标的一定增量分组，
对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，
整个文件恰被分成一组，算法便终止
'''
def shell_sort(ilist):
    gap=len(ilist)
    while gap>1:
        gap=gap//2
        for i in range(gap,len(ilist)):
            for j in range(i%gap,i,gap):
                if ilist[i]<ilist[j]:
                    ilist[i],ilist[j]=ilist[j],ilist[i]
    return ilist


'''
冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
'''
def bubble_sort(ilist):
    flag=len(ilist)-1
    for i in range(len(ilist)):
        for j in range(flag):
            if ilist[j]>ilist[j+1]:
                flag=j
                ilist[j], ilist[j+1] = ilist[j+1], ilist[j]
    return ilist


'''
快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
'''
def quick_sort(ilist):
    if ilist==[]:
        return []

    qfirst=ilist[0]
    qsmall=quick_sort([s for s in ilist[1:] if s < qfirst])
    qlarge=quick_sort([l for l in ilist[1:] if l >=qfirst])

    return qsmall +[qfirst] +qlarge

'''
选择排序：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，
将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕
'''
def select_sort(ilist):
    for i in range(len(ilist)):
        a=i
        for j in range(i+1,len(ilist)):
            if ilist[j]<ilist[a]:
                a=j
        ilist[i],ilist[a]=ilist[a],ilist[i]
    return ilist


'''
归并排序：采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
'''
def merge_sort(ilist):
    def recursive(ilist):
        if len(ilist)==1:
            return ilist
        mid=len(ilist)//2
        left=recursive(ilist[:mid])
        right=recursive(ilist[mid:])
        return merge(left,right)

    def merge(left,right):
        ans=[]
        while len(left) and len(right):
            if left[0]<= right[0]:
                ans.append(left.pop(0))
            else:
                ans.append(right.pop(0))
        ans.extend(left)
        ans.extend(right)
        return ans

    return recursive(ilist)


'''
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，
先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于分别排序，分别收集，所以是稳定的。
'''
def radix_sort(ilist):
    bucket,digit=[[]],0
    while len(bucket[0])!=len(ilist):
        bucket=[[] for x in range(10)]
        for i in ilist:
            num=(i//10**digit)%10
            bucket[num].append(i)
        ilist=[a for b in bucket for a in b]
        digit+=1
    return ilist


'''
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
'''
def counting_sort(ilist):
    n = len(ilist)
    b = [0 for i in range(n)]
    c = [0 for i in range(max(ilist)+1)]
    for j in ilist:
        c[j] = c[j] + 1
    for i in range(1, len(c)):
        c[i] = c[i] + c[i-1]
    for j in ilist:
        b[c[j] - 1] = j
        c[j] = c[j] - 1
    return b


'''
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序
（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
该例子中，设置桶的数量为(max(ilist) - min(ilist)) + 1），跟计数排序很像
'''
def bucket_sort(ilist):
    buckets = [0] * ((max(ilist) - min(ilist)) + 1)  # 初始化桶元素为0
    for i in range(len(ilist)):
        buckets[ilist[i] - min(ilist)] += 1  # 遍历数组a，在桶的相应位置累加值
    b = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            b += [i + min(ilist)] * buckets[i]
    return b


'''
堆排序：它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，
需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶
lchild=parent*2+1 rchild=parent*2+2
'''
def heap_sort(ilist):
    def heap_adjust(parent):
        child=parent*2+1
        while child<len(heap):
            if child +1<len(heap):
                if heap[child +1]>heap[child]:
                    child=child+1
            if heap[parent]>=heap[child]:
                break
            heap[parent],heap[child]=heap[child],heap[parent]
            parent, child = child, 2 * child + 1

    heap, ilist = ilist.copy(), []
    for i in range(len(heap)//2,-1,-1):
        heap_adjust(i)
    while len(heap)!=0:
        heap[0],heap[-1]=heap[-1],heap[0]
        ilist.insert(0,heap.pop())
        heap_adjust(0)
    return ilist

#Ann = n!
def Ann(arr):
    def first(ans,arr):
        if len(arr)==0:
            return print(ans)
        arr_t=arr.copy()
        num=arr_t.pop(0)
        for i in range(len(ans)+1):
            temp=ans.copy()
            temp.insert(i,num)
            first(temp,arr_t)

    return first([],arr)

#Anm = n! / (n-m)!
#Cnm = n! / ( m! * (n-m)! )
def Cnm(lis,m,start=0):
    if m==0:
        for i in range(start-1):
            if lis[i]>lis[i+1]:   # 只取从小到大的那种排列方式，去掉这句就是Anm的实现
                break
        else:
            print(lis[:start])
            global count
            count += 1
        return 0

    for i in range(start,len(lis)):
        lis[start],lis[i]=lis[i],lis[start]
        Cnm(lis,m-1,start+1)
        lis[start], lis[i] = lis[i], lis[start]


if __name__=="__main__":
    # Ann(['a', 'b', 'c', 'd', 'e'])
    ilist=[4,5,6,7,3,2,6,9,8]
    print(bubble_sort(ilist))