冒泡、选择、插入、希尔、归并、计数、快排

all

class ALG(object):
    def __init__(self,list):
        self.list=list
    #冒泡
    def bubble_sort(nums):
        n =len(nums)
        for i in range(n - 1):  
            for j in range(n-1 - i):
                if nums[j+1] < nums[j]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        return nums
    #选择
    def select_sort(alist):
        l= len(alist)
        for n in range(l-1):
            _min = n
            for m in range(n+1,l):
                if alist[m] < alist[_min]:
                    _min=m
            alist[n],alist[_min]=alist[_min],alist[n]
        return alist
    #插入
    def insert_sort(alist):
        l=len(alist)
        for m in range(1,l):
            for n in range(m,0,-1):
                if alist[n]<alist[n-1]:
                    alist[n],alist[n-1]=alist[n-1],alist[n]
        return alist
    #希尔
    def shell_sort(alist):
        l=len(alist)
        gap= l // 2
        while gap >0:
            for j in range(gap,l):
                i =j
                while i>0:
                    if alist[i] < alist[i-gap]:
                        alist[i],alist[i-gap]=alist[i-gap],alist[i]
                        i -= gap
                    else:
                        break
            gap //= 2
        return alist
    #快速
    def quick_sort(alist,start,end):
        if start >=end:
            return
        middle_v = alist[start]
        low= start
        high= end
        while low < high:
            while low < high and alist[high] >= middle_v:
                high -=1
            alist[low]=alist[high]

            while low < high and alist[low] < middle_v:
                low +=1
            alist[high]=alist[low]

        alist[low]=middle_v
        quicksort(alist,start,low-1)
        quicksort(alist,low+1,end)

#归并排序 
#      归并排序是采用分治策略进行排序的一种算法，其基本原理是将未排序的数组划分为两个子数组，分别对两个子数组尽心排序，然后将有序的子数组合并。归并排序分为两个过程：一是数组划分为两个子数组并分别进行排序，二是将两个已排序的子数组进行合并。
def merge_sort( li ):
    #递归调用一直到拆分成成单个元素的时候就返回这个元素，不再拆分
    if len(li) == 1:
        return li
    #取拆分的中间位置
    mid = len(li) // 2
    #拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]
    #对拆分过后的左右再拆分 一直到只有一个元素为止
    #最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort( left )
    rl =merge_sort( right )
    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    return merge(ll , rl)
    
def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
        #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result
	
#计数
#统计每个数比列表其他数  大于 的次数,   次数越多 : 说明, 这个数越大,   反之, 大于的次数越少, 说明, 这个数就越小
def count_sort(l):
    n = len(l)
    res = [None] * n
    for i in range(n):
        # p 表示 a[i] 大于列表其他数 的次数
        # q 表示 等于 a[i] 的次数
        p,q = 0,0
        for j in range(n):
            if l[i] > l[j]:
                p += 1
            elif l[i] == l[j]:
                q += 1
        for m in range(p, p+q):  # q表示 相等的次数,就表示, 从 P 开始索引后, 连续 q 次,都是同样的 数
            res[m] = l[i]
    return res

quicksort

def quicksort(array):
  if len(array) < 2:
   
    return array  # base case, arrays with 0 or 1 element are already "sorted"
  else:
    
    pivot = array[0]
    
    less = [i for i in array[1:] if i <= pivot]
   
    greater = [i for i in array[1:] if i > pivot]
    
    return quicksort(less) + [pivot] + quicksort(greater)



print(quicksort([10, 5, 2, 3]))