python - 排序

希尔排序：

1、将列表以一定间隔gap进行划分，再对划分后的每一部分进行插入排序，使得每一部分构成一个有序的序列

2、再缩小gap，重复步骤1，直至gap = 1，进行最后一次插入排序，获得整体的有序序列

notes：list内部操作，无需另外请求地址

# coding:utf-8
# 希尔排序

def shell_sort(alist):
    '''希尔排序'''
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for j in range(gap, n):
            i = j
            while i > 0:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

快速排序：将列表通过选定的参考基准分为左/右两部分，左边的都比基准小，右边的都比基准大，再对左/右的列表进行快排（递归），直至有序排列

快速排序的过程很复杂，中间有多次递归，要注意每次递归时传入的参数是多

过程参考下图：

单次递归的结果是将列表以基准分为小于基准部分和大于基准部分

进行下一次递归时，则将基准左右的数据以新基准进行再次进行划分

代码如下：

# coding:utf-8
# 快速排序

def quick_sort(alist, first, last):
    '''快速排序'''
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        # high 左移
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]

    # 从循环退出时，low = high
    alist[low] = mid_value

    # 对low位置左边的列表进行快速排序
    quick_sort(alist, first, low-1)

    # 对low位置右边的列表进行快速排序
    quick_sort(alist, low+1, last)

归并排序：先分解，后排序

下图清晰明了，参考博文：图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园

快，但是需要额外的内存

代码如下：

# coding:utf-8
# 归并排序

def merge_sort(alist):
    '''归并排序'''
    n = len(alist)
    if n <= 1:
        return alist
    mid = n//2

    # left 采用归并排序后形成的有序新列表
    left_li = merge_sort(alist[:mid])

    # right 采用归并排序后形成的有序新列表
    right_li = merge_sort(alist[mid:])

    # 将两个子序列合为一个新的整体
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []

    while left_pointer < len(left_li) and  right_pointer < len(right_li):
        if left_li[left_pointer] <= right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

搜索-二分查找：

局限性：应用于有序列表中

简例：猜0-100中的某个数，这个数既代表位置，要代表数据

# coding:utf-8
# 二分查找的递归和非递归形式
def binary_search(alist, item):
    """二分查找,递归"""
    n = len(alist)
    if n > 0:
        mid = n//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid+1:], item)
    return False



def binary_search_2(alist, item):
    """二分查找， 非递归"""
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last)//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False