极客算法

算法 - 常见排序Sorting

2020-12-14

快排

O(N *logN)

              k
 [1,2,3,4,5,  6,7,8,9,10]
 k.left <= last  k.right > last

快排主要是, 选择一个比较值(比如说last), 找到分割点k,保证k左边<=last, k右边>last

def quick_sort(arrs):
    def __partiion(arrs, start, end):
        last = arrs[end - 1]
        k = start

        for i in range(k, end - 1):
            if arrs[i] <= last:
                arrs[k], arrs[i] = arrs[i], arrs[k]
                k += 1
        arrs[k], arrs[end - 1] = arrs[end - 1], arrs[k]

        return k

    def __quick_sort(arrs, start, end):

        if end - start <= 1:
            return

        k = __partiion(arrs, start, end)
        __quick_sort(arrs, start, k)
        __quick_sort(arrs, k, end)

    __quick_sort(arrs, 0, len(arrs))

归并排序

O(N * logN)

分治思想, 将问题一步步切割,分到1个的时候就不用排序了,然后把各个结果都合并起来

def merge_sort(arrs):

    def __merge(arrs, start, mid, end):
        L = arrs[start: mid] # left sub problem, this is a copy
        R = arrs[mid: end] # right sub problem, this is a copy
        # merge two already sorted into one
        i = 0
        j = 0
        for k in range(start, end):
            if i >= len(L) or (j < len(R) and L[i] > R[j]):
                arrs[k] = R[j]
                j = j + 1
            else:
                arrs[k] = L[i]
                i = i + 1

    def __divied(arrs, start, end):
        if end - start <= 1:
            return

        mid = start + (end - start) // 2
        __divied(arrs, start, mid) # divide
        __divied(arrs, mid, end) # divide
        __merge(arrs, start, mid, end) # combine

    __divied(arrs, 0, len(arrs))

插入排序

O(N^2)

[3, 4] + [2, 5, 7, 9] # 当插入2时

[x, 3, 4] # 4比2大, 3比2大, 都右移一位,让出x位置
 ^
 2

对于小规模数据,还是挺快的

def insertion_sort(arrs):
    for i in range(1, len(arrs)): #from 2nd to the end
        target = arrs[i]

        # right shift until appropriate position found
        j = i
        while j > 0 and target < arrs[j - 1]:
            arrs[j] = arrs[j - 1]
            j -= 1

        arrs[j] = target

冒泡排序

O(N^2)

[3, 4, 2, 5, 7, 9]
 i
# 最小的2, 一步步交换, 放置到最左边i=0的位置

[2, 3, 4, 5, 7, 9]
    i
# 移动i,继续上述操作

最小元素像气泡一样, 一步步浮到左边

def bubble_sort(arrs):
    for i in range(len(arrs)):
        for j in reversed(range(i, len(arrs))):
            if arrs[j] < arrs[j - 1]:
                arrs[j], arrs[j - 1] = arrs[j - 1], arrs[j]

选择排序

O(N^2)

[3, 4, 2, 5, 7, 9]
 i  
 ------ min ------
# 找到右边最小的元素,然后和i交换

[2, 3, 4, 5, 7, 9]
    i  
    ---- min ----
# 移动i,继续上述操作
def selection_sort(arrs):
    for i in range(0, len(arrs)):
        min_index = i

        # find the smallest element from (i+1)th to the last
        for j in range(i + 1, len(arrs)):
            if arrs[j] < arrs[min_index]:
                min_index = j

        if min_index != i:
            arrs[i], arrs[min_index] = arrs[min_index], arrs[i]

堆排序

O(N * logN)

利用大堆的性质,每次拿出来root最大的,放在后面

           0     
        /     \    
      1         2  
    /   \      /     
   3     4    5       
# 以 0 为跟节点的堆, left = 2i + 1, right = 2i + 2

有点像选择排序,每次拿到最大的,放入到对应的位置

def heap_sort(arrs):
    def __max_heepify(arrs, size, i):
        l = 2 * i + 1
        r = 2 * i + 2
        largest = i

        # find the largest in the little "triangle", and swap them.
        # since swap may break the heap in child heap, so do it reacursively
        if l < size and arrs[l] > arrs[largest]:
            largest = l
        if r < size and arrs[r] > arrs[largest]:
            largest = r

        if largest != i:
            arrs[i], arrs[largest] = arrs[largest], arrs[i]
            __max_heepify(arrs, size, largest)

    # building a heap using array
    def __build_heap(arrs):
        for i in reversed(range(0, len(arrs)//2)):
            __max_heepify(arrs, len(arrs),  i)

    __build_heap(arrs)
    for i in reversed(range(1, len(arrs))):
        arrs[i], arrs[0] = arrs[0], arrs[i]
        __max_heepify(arrs, i, 0)

–End–

代码原地址: https://github.com/geemaple/leetcode/tree/master/learning


评论

内容:
其他: