排序算法

排序算法

1、冒泡排序：

def Paosort(A):#冒泡排序
    # 时间复杂度为o(n)正序 ---o(n*n) 倒序 ,优点：简单、稳定 但时间复杂度差
    for i in range(len(A)-1,-1,-1):
        flag=0
        for j in range(i):
            if A[j]>A[j+1]:
                A[j],A[j+1]=A[j+1],A[j]
                flag=1
        if flag==0: #作用为判断后续数据是否已有序，若有则退出
            break
    return A

2、插入排序

def Insertsort(A):#插入排序
    # 时间复杂度与冒泡相同
    for i in range(1,len(A)):
        temp=A[i] #摸一张牌,然后与现有的牌进行比较
        while(i>0 and temp<A[i-1]):
            A[i]=A[i-1] #交换次数较少
            i-=1
        A[i]=temp
    return A

3、希尔排序

def ShellSort(A, k):
    # 原始的希尔排序,改变k值（k=1时）可以转化为插入排序
    # 可以通过增加增量序列，来改善希尔序列的复杂度
    D = int(len(A) / k)
    while (D > 0):
        for i in range(D, len(A)):
            temp = A[i]
            j = i
            while (j >= D and temp < A[j - D]):
                A[j] = A[j - D]
                j -= D
            A[j] = temp
        D = int(D / 2)
    return A

4、堆排序

lass minHeap(object): #最小堆

    def __init__(self):
        self.items=[0]  #设定哨兵
        self.currentSize=0

    def insert(self,item): #插入

        self.items.append(item)
        self.currentSize+=1
        self.percut()
    def percut(self): #堆的自我调整
        i = self.currentSize
        while i // 2 > 0:
            if self.items[i] < self.items[i // 2]:
                self.items[i], self.items[i // 2] = self.items[i // 2], self.items[i]
            i = i // 2

    def listToHeap(self,nums):
        for num in nums:
            self.insert(num)

    def getMin(self):
        return self.items[1]

    def delMin(self):

        if self.currentSize==0:
            return False
        temp = self.items[1]
        if self.currentSize==1:
            self.items.pop()
            return temp
        self.items[1]=self.items.pop()
        self.currentSize = self.currentSize - 1
        i=1
        while(i*2<=self.currentSize):
            minnum=self.permin(i)
            if self.items[i]>self.items[minnum]:
                self.items[i],self.items[minnum]=self.items[minnum],self.items[i]
            i=i*2
        return temp
    def permin(self,i):
        if i*2+1>self.currentSize:
            return i*2
        elif self.items[i*2]<self.items[i*2+1]:
            return i*2
        else:
            return i*2+1
    def pintHeap(self):
        print(H.items[1:])

def HeapSort(A): # 时间复杂度 O(NlogN)
    H=minHeap()  # O(n) ,
    H.listToHeap(A) #建立最小堆
    for i in range(len(A)):
       A[i]= H.delMin()
    return A



### 采用最大堆进行排序 ###
def Heap_sort(A): #采用最大堆进行排序，使用较多

    for i in range(len(A)-1,-1,-1):
        buildHeap(A, i)
        A[i],A[0]=A[0],A[i]


def buildHeap(A,N):

    for i in range(N//2,-1,-1):
        perdown(A,i,N)
        
def perdown(A,i,k):
    
    ''' 从最后一个带叶节点的节点进行堆化
        i 代表为当前堆的顶点，N代表当前遍历堆的最大数
    '''
   
    def findmax(i):
        if i*2+2>=k:
            return i*2
        elif A[i*2+1]>A[i*2+2]:
            return i*2+1
        else:
            return i*2+2
    while(i*2+1<k):
        if A[i] < A[findmax(i)]:
            A[i], A[findmax(i)] = A[findmax(i)], A[i]
        i=i*2+1

5、归并排序

def Merge(A, B, C=[]):  # 合并两个有序的子列
    # 时间复杂度O（n）
    i=j=0
    while (i < len(A) and j < len(B)):
        if A[i] > B[j]:
            C.append(B[j])
            j += 1
        else:
            C.append(A[i])
            i += 1
    while(i<len(A)):
        C.append(A[i])
        i+=1
    while(j<len(B)):
        C.append(B[j])
        j+=1
    return C

##递归排序##

def Mergesort(A):  # N为数组长度
    if len(A) <= 1:
        return A
    center = len(A) // 2
    left = Mergesort(A[:center])
    right = Mergesort(A[center:])
    return Msort(left, right)


def Msort(left, right):
    i, j = 0, 0
    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
    result+=left[i:]
    result+=right[j:]
    return  result