algorithms

heapsort.py

# coding=utf-8

import sys
import math


def left(i):
    return 2 * (i + 1) - 1

def right(i):
    return 2 * (i + 1) + 1 - 1

def parent(i):
    return (i + 1) // 2 - 1

def index(A, i, n):
    if i >= n:
        return None
    else:
        return A[i]

def swap(A, i, j):
    A[i], A[j] = A[j], A[i]

def max(v, lv, rv):
    # 比较的时候，要么统一使用<，要么使用>=
    if lv is None and rv is None:
        return v, ''
    if lv is None:
        if rv >= v:
            return rv, 'r'
        else:
            return v, ''
    if rv is None:
        if lv >= v:
            return lv, 'l'
        else:
            return v, ''
    if rv >= lv and rv >= v:
        return rv, 'r'
    elif lv >= rv and lv >= v:
        return lv, 'l'
    else:
        return v, ''

def max_heapify(A, i, n=None):
    """
    A: the array
    i: index of node to heapify
    n: the lenght of A, default to len(A)
    """
    if n is None:
        n = len(A)
    if i >= n:
        return

    l = left(i)
    r = right(i)
    v = index(A, i, n)
    lv = index(A, l, n)
    rv = index(A, r, n)
    max_v, pos = max(v, lv, rv)
    if pos == 'l':
        swap(A, l, i)
        max_heapify(A, l, n)
    elif pos == 'r':
        swap(A, r, i)
        max_heapify(A, r, n)

def heapify(A):
    start = len(A) // 2 - 1  # 只需从中间开始，后半部分自动就整理好了
    for i in range(start, -1, -1):
        max_heapify(A, i)

def heapsort(A):
    heapify(A)
    end_index = len(A) - 1
    while end_index > 0:
        swap(A, 0, end_index)  # 取最大的放到最后，然后重新整理一下堆
        max_heapify(A, 0, end_index)  # 然后重新最大堆化
        end_index -= 1

def head_print(A):
    line_count = 0
    for i, v in enumerate(A):
        h = int(math.log(i + 1, 2))
        if h != line_count:
            line_count += 1
            sys.stdout.write('\n')
        sys.stdout.write(' {} '.format(v))
    sys.stdout.write('\n')
    sys.stdout.flush()


arr1 = [1, 2, 3, 4, 4, 4, 7, 8, 9, 10]
arr2 = [2, 3, 1, 6, -1]
arr3 = [1] * 10


heapsort(arr1)
head_print(arr1)
print(arr1)
heapsort(arr2)
head_print(arr2)
print(arr2)
heapsort(arr3)
head_print(arr3)
print(arr3)

qsort.py

# coding=utf-8


def partition(A, i, j):
    val = A[j]
    for k in range(i, j):
        # 比较器在这里
        if A[k] < val:
            A[i], A[k] = A[k], A[i]
            i += 1
    A[j], A[i] = A[i], A[j]
    return i

def qsort(A, i=0, j=None):
    if j is None:
        j = len(A) - 1
    if i < j:
        pivot = partition(A, i, j)
        qsort(A, i, pivot - 1)
        qsort(A, pivot + 1, j)


arr1 = [1, 2, 3, 4, 5, 6, 7]
arr2 = [0, 1, -1, 2, -10, 6, 5, 3]
qsort(arr1)
qsort(arr2)
print(arr1)
print(arr2)