程序员必须掌握的数据结构 1

无论是任何程序员，不论是算法，还是其他，都需要掌握一定的数据结构。本文以最优雅的方式，基于Python，完成算法，不要问，背下来就好。代码量更少，更好背。

源码 ： github.com/SpikeKing/d…

第1篇 查找和排序：二分查找、冒泡排序、选择排序、插入排序、希尔排序、归并 排序 、快速排序。

1. 二分查找

二分查找，时间复杂度O(logn)，排序一次，查找多次，排序成本可以忽略；只查找一次，则顺序查找比较好。非递归13行，递归11行。

def binary_search(alist, item):
    """
    二分查找，非递归
    1. 2个参数，待查找alist和查找项item
    2. 声明3个变量，first，last，found(返回值)
    3. while条件，first小于等于last，found是false
    4. mid是first和last的中值(整除)；
    5. 三个if条件，相等alist[mid]=item，小于中值换last，大于中值换first；
    6. 返回found，13行
    :param alist: 待查找alist
    :param item: 待查找项item
    :return: 是否找到
    """
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        mid = (first + last) // 2
        if alist[mid] == item:
            return True
        else:
            if item < alist[mid]:
                last = mid - 1
            else:
                first = mid + 1
    return found


def binary_search_re(alist, item):
    """
    二分查找，递归
    1. if终止条件，长度为0，返回False；
    2. 中点是长度除2，中值判断；
    3. 小于递归前半部分，大于递归后半部分，返回递归函数；
    4. 11行
    :param alist: 待查找alist
    :param item: 待查找项item
    :return: 是否找到
    """
    if len(alist) == 0:
        return False
    else:
        mid = len(alist) // 2
        if alist[mid] == item:
            return True
        else:
            if item < alist[mid]:
                return binary_search_re(alist[:mid], item)
            else:
                return binary_search_re(alist[mid + 1:], item)


def test_of_binary_search():
    test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
    print(binary_search(test_list, 3))
    print(binary_search(test_list, 13))
    print(binary_search_re(test_list, 3))
    print(binary_search_re(test_list, 13))


if __name__ == '__main__':
    test_of_binary_search()
复制代码

2. 冒泡排序

冒泡排序，时间复杂度O(n^2)，冒泡排序通常被认为是低效的排序方式。优势是：识别排序列表，和提前终止排序。冒泡排序4行，短冒泡排序9行。

def bubble_sort(alist):
    """
    冒泡排序
    1. 两次遍历，第1次遍历长度，倒序逐渐减1，每遍历一次，排序一个；
    2. 第2次，正常遍历，少1个值，因为i和i+1；
    3. 当前位大于下一位，交换当前位和下一位；
    4. 4行
    :param alist: 待排序列表
    :return: None，内部排序
    """
    for p_num in range(len(alist) - 1, 0, -1):
        for i in range(p_num):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]


def short_bubble_sort(alist):
    """
    短冒泡排序，增加exchange，额外终止参数
    1. 初始为True，当为False时终止；
    2. 在第2次循环前，设置为False，交换一次就设置为True，一次未交换则触发终止；
    3. 9行，增加5行的exchange操作
    :param alist:
    :return:
    """
    exchange = True
    for p_num in range(len(alist) - 1, 0, -1):
        if not exchange:
            break
        exchange = False
        for i in range(p_num):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                exchange = True

                
def test_of_bubble_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # bubble_sort(alist)
    # print(alist)
    alist = [17, 20, 26, 93, 77, 31, 44, 55, 54]
    short_bubble_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_bubble_sort()
复制代码

3. 选择排序

选择排序，时间复杂度O(n^2)，比较次数与冒泡排序相同，交换次数小于冒泡排序。 选择排序6行。

def selection_sort(alist):
    """
    选择排序，即选择最大值再交换
    1. 依然是2次遍历，第1次反序，第2次正序，注意起始为1，末尾+1；
    2. max_loc存储最大值，默认第0位；
    3. 当loc的值大于max_loc的值时，max_loc重新赋值；
    4. 交换loc和max_loc
    5. 6行
    :param alist: 待排序alist
    :return: None
    """
    for p_num in range(len(alist) - 1, 0, -1):
        max_loc = 0
        for loc in range(1, p_num + 1):
            if alist[loc] > alist[max_loc]:
                max_loc = loc
        alist[p_num], alist[max_loc] = alist[max_loc], alist[p_num]


def tes_of_selection_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    selection_sort(alist)
    print(alist)


if __name__ == '__main__':
    tes_of_selection_sort()
复制代码

4. 插入排序

插入排序，时间复杂度O(n^2)，用移位代替交换，移位操作的时间大约是交换时间的1/3。插入排序7行。

def insert_sort(alist):
    """
    插入排序，
    1. 遍历列表，存储当前值cur_val，设置游标pos
    2. 游标大于0和游标的值大于当前值，则移位，同时游标减1；
    3. 将当前值赋予游标的终止位置；
    4. 7行
    :param alist: 待排序alist
    :return: None
    """
    for idx in range(1, len(alist)):
        cur_val = alist[idx]
        pos = idx  # 游标
        while pos > 0 and alist[pos - 1] > cur_val:
            alist[pos] = alist[pos - 1]
            pos -= 1
        alist[pos] = cur_val  # 最后游标的位置


def test_of_insert_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_insert_sort()
复制代码

5. 希尔排序

希尔排序，时间复杂度，介于O(n)~O(n^2)，也可以认为是O(n^3/2)，插入排序的改进，比较和移位较少，每次遍历都会生成一个"更有序"的子列表。12行，增量部分5行，插入部分7行。

def shell_sort(alist):
    """
    希尔排序
    1. 两部分，第1部分，计算增量gap和起始位置s_pos；
    2. 增量是累除2，s_pos是增量的遍历
    3. 增量插入排序，额外传入起始位置和增量；
    4. range的起始由起始位置+增量；
    5. 循环条件为大于等于增量，差值为增量
    6. 12行，增量部分5行，插入部分7行
    :param alist: 待排序alist
    :return: None
    """
    gap = len(alist) // 2
    while gap > 0:
        for s_pos in range(gap):
            gap_insert_sort(alist, s_pos, gap)
        gap = gap // 2


def gap_insert_sort(alist, s_pos, gap):
    """
    带增量的插入排序
    :param alist: 待排序alist
    :param s_pos: 起始位置
    :param gap: 增量
    :return: None
    """
    for idx in range(s_pos + gap, len(alist), gap):
        cur_val = alist[idx]
        pos = idx
        while pos >= gap and alist[pos - gap] > cur_val:
            alist[pos] = alist[pos - gap]
            pos -= gap
        alist[pos] = cur_val


def test_of_shell_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shell_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_shell_sort()
复制代码

6. 归并排序

归并排序，时间复杂度O(nlogn)。20行。

def merge_sort(alist):
    """
    归并排序
    1. 递归，结束条件，只有1个元素，return；
    2. mid中心，左右两部分，递归调用merge_sort；
    3. 遍历左右，添加较小的值；遍历其余部分；
    4. 20行
    :param alist:
    :return:
    """
    if len(alist) < 2:
        return
    mid = len(alist) // 2
    left_half = alist[:mid]
    right_half = alist[mid:]
    merge_sort(left_half)
    merge_sort(right_half)
    i, j, k = 0, 0, 0
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            alist[k] = left_half[i]
            i += 1
        else:
            alist[k] = right_half[j]
            j += 1
        k += 1
    while i < len(left_half):
        alist[k:] = left_half[i:]
    while j < len(right_half):
        alist[k:] = right_half[i:]


def test_of_merge_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    merge_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_merge_sort()
复制代码

7. 快速排序

快速排序，时间复杂度O(nlogn)。不需要额外空间14行，需要额外空间7行。

def quick_sort(alist, fst, lst):
    """
    快速排序
    1. 确定终止条件，起始等于终止；
    2. 起始fst和终止lst的位置，枢轴的值pivot；
    3. 遍历i和j，
    :param alist: 待排序列表
    :param fst: 起始idx
    :param lst: 终止idx
    :return: None
    """
    if fst >= lst:
        return
    i, j = fst, lst
    pivot = alist[fst]
    while i <= j:
        while alist[i] < pivot:
            i += 1
        while alist[j] > pivot:
            j -= 1
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
            i, j = i + 1, j - 1
    quick_sort(alist, fst, j)
    quick_sort(alist, i, lst)


def quick_sort_v2(alist):
    """
    快速排序
    :param alist:
    :return:
    """
    if len(alist) < 2:
        return alist
    pivot = alist[0]
    small = [i for i in alist if i < pivot]
    medium = [i for i in alist if i == pivot]
    large = [i for i in alist if i > pivot]
    return quick_sort_v2(small) + medium + quick_sort_v2(large)


def test_of_quick_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # quick_sort(alist, 0, len(alist) - 1)
    # print(alist)
    alist = quick_sort_v2(alist)
    print(alist)


if __name__ == '__main__':
    test_of_quick_sort()
复制代码

OK, that's all! Enjoy it!