分类

排序

希尔排序

• 代码实现

def sort(arr):
    h = 1
    size = len(arr)
    while h < size // 3:
        h = 3 * h + 1
    while h >= 1:
        for i in range(h, size):
            j = i
            while j >= h and arr[j] < arr[j-h]:
                tmp = arr[j-h]
                arr[j-h] = arr[j]
                arr[j] = tmp
                j -= h
        h = h // 3
    return arr

归并排序

• 代码实现

# coding=utf-8
###归并排序
class Merge:
    # 额外数组空间
    aux = []

    def sort(self, arr):
        count = len(arr)
        ##初始化数据大小
        self.aux = [0] * count
        self.sort0(arr, 0, count - 1)

    def sort0(self, arr, low, high):
        if low < high:
            mid = (low + high) // 2
            self.sort0(arr, low, mid)
            self.sort0(arr, mid + 1, high)
            self.merge(arr, low, mid, high)

    def merge(self, arr, low, mid, high):
        for i in range(low, high + 1):
            self.aux[i] = arr[i]
        i = low
        j = mid + 1
        #原地归并
        for k in range(low, high + 1):
            if i > mid:
                arr[k] = self.aux[j]
                j += 1
            elif j > high:
                arr[k] = self.aux[i]
                i += 1
            elif self.aux[j] >= self.aux[i]:
                arr[k] = self.aux[i]
                i += 1
            else:
                arr[k] = self.aux[j]
                j += 1

查找