AI_第一部分 数据结构与算法（12.排序算法实战下）

def _quick_sort_between(a, low, high):
    if low < high:
        # get a random position as the pivot
        # 得到一个任意位置作为支点
        k = random.randint(low, high)
        a[low], a[k] = a[k], a[low]  # 将point 点换到最左边
        m = _partition(a, low, high)  # a[m] is in final position A[M]处于最终位置
        _quick_sort_between(a, low, m - 1)
        _quick_sort_between(a, m + 1, high)
def _partition(a, low, high):
    pivot, j = a[low], low
    print pivot
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:  # 从下标为1的开始找其值小于支撑点则下标自动加1
            j += 1
            a[j], a[i] = a[i], a[j]  # [没有理解]  为了让其[左边的保持有序]？swap  # 然后做一次交换(相当于更新了支撑点的下标)
            print a
    a[low], a[j] = a[j], a[low]  # 将支撑点放置在区分左右半区的点上
    return j

def _merge_sort_between(a, low, high):
    """
    归并排序
    :param a:需排序数组 
    :param low: 最小下标
    :param high: 最大下标
    :return: 
    """
    # The indices are inclusive for both low and high.
    # 指数包括低指数和高指数
    if low < high:
        mid = low + (high - low) // 2  # 求出把数组分成两半的中间节点下标
        _merge_sort_between(a, low, mid)  # 分解低于mid以下的
        _merge_sort_between(a, mid + 1, high)  # 分解高于mid的
        print(a, low, mid, high)
        _merge(a, low, mid, high)  # 合并
def _merge(a, low, mid, high):
    # a[low:mid], a[mid+1, high] are sorted.
    i, j = low, mid + 1
    tmp = []
    while i <= mid and j <= high:
        # i代表左边的半边 j 代表的是右边半边 (若有一边越界则退出，代表已经把一边的排序已经完成)
        if a[i] <= a[j]:  # 左边第一个与右边第一个比较(若左边小)
            tmp.append(a[i])  # 左边的数进入临时排序队列
            i += 1  # 左边下标向前移动一位
        else:  # 若有右边的比左边的小则
            tmp.append(a[j])  # 右边的下标向前移动一位
            j += 1  # 右边的下标向前移动一位
    # 若左边没有越界则开始下标等于左边的剩余下边起点，否则是等于右边下边剩余起点
    start = i if i <= mid else j
    # 结束结点则用中间节点或者最后一个节点来界定
    end = mid if i <= mid else high
    tmp.extend(a[start:end + 1])  # 将剩余的有序结点一次性加入有序结点中
    a[low:high + 1] = tmp  # 重新覆盖传入的无序的列表中