# coding:utf-8

def quick_sort_1(vet):
    '''python式'''
    if len(vet) <= 1:
        return vet

    key = vet[-1]
    middle = [i for i in vet if i==key]
    left = quick_sort_1([i for i in vet if i<key])
    right = quick_sort_1([i for i in vet if i>key])
    return left + middle + right

#-------------------------------------------------------------

def partition(vet, left_index, right_index):
    key = vet[left_index]
    while left_index < right_index:
        while left_index < right_index and vet[right_index] >= key:
            right_index -= 1
        if right_index != left_index:  # 上面减一之后可能会变成相同
            vet[right_index], vet[left_index] = vet[left_index], vet[right_index]
            left_index += 1
        while left_index < right_index and vet[left_index] < key:
            left_index += 1
        if right_index != left_index:
            vet[right_index], vet[left_index] = vet[left_index], vet[right_index]
            right_index -= 1
    return left_index # 显然此时左右指针一致


def quick_sort_2(vet, left_index, right_index):
    '''指针式'''
    if left_index < right_index:
        key_index = partition(vet, left_index, right_index)
        quick_sort_2(vet, left_index, key_index-1)  # 原地排序，没有return
        quick_sort_2(vet, key_index+1, right_index)


if __name__ == '__main__':
    vet = [7,6,2,0,3,12,5,7,8,5,23,89,9,4,1,6,8]
    quick_sort_2(vet, 0, len(vet)-1)
    print vet

#coding:utf-8

def built_max_heap(vet):
    '''调整为最大堆'''
    n = len(vet)
    while True:
        old = vet[:]
        for node_index in range(n):
            left_index = 2*node_index+1
            right_index = 2*node_index+2
            if left_index > n-1:     #若该结点无左孩，当然右孩也没有，则跳出循环
                break
            if right_index > n-1:    #若该结点有左孩，无右孩
                if vet[left_index]>vet[node_index]:
                    vet[left_index], vet[node_index] = vet[node_index], vet[left_index]
            if right_index <= n-1:   #若该节点既有左孩又有右孩
                if vet[left_index] >= vet[right_index] and vet[left_index] >= vet[node_index]:
                    vet[left_index], vet[node_index] = vet[node_index], vet[left_index]
                if vet[right_index] > vet[left_index] and vet[right_index] > vet[node_index]:
                    vet[right_index], vet[node_index] = vet[node_index], vet[right_index]
        if vet == old:
            break
    return vet

def get_max_and_new_heap(vet):
    vet[0], vet[-1] = vet[-1], vet[0]
    max = vet.pop()
    return max,vet

def heap_sort(vet):
    sorted_vet = []
    while len(vet)>=1:
        vet = built_max_heap(vet)
        max, new_heap = get_max_and_new_heap(vet)
        vet = new_heap
        sorted_vet.append(max)
    return sorted_vet

if __name__=='__main__':
    vet = [4, 4, 2, 5, 3, 9, 0, 6, 28, 9, -5, 7, 8]
    print heap_sort(vet)

# coding:utf-8

def merge(vet1, vet2):
    merge_vet = []
    index1 = 0
    index2 = 0
    while index1<len(vet1) and index2<len(vet2): # 将较小的放进merge_vet
        if vet1[index1]<vet2[index2]:
            merge_vet.append(vet1[index1])
            index1 += 1
        else:
            merge_vet.append(vet2[index2])
            index2 += 1
    if index1 == len(vet1):  # 若有一向量已全部放入merge_vet, 将剩下的部分全部复制进去(剩下部分之前已排好)
        merge_vet.extend(vet2[index2:])
    else:
        merge_vet.extend(vet1[index1:])
    return merge_vet

def merge_sort(vet):
    n = len(vet)
    if n <= 1:
        return vet
    middle_index = n/2
    left = merge_sort(vet[:middle_index])
    right = merge_sort(vet[middle_index:])
    return merge(left, right)

if __name__ == '__main__':
    vet = [4, 4, 2, 5, 3, 9, 0, 6, 28, 9, -5, 7, 8]
    print merge_sort(vet)