12_快速排序

def quicksort(array):
    size = len(array)
    if not array or size < 2:
        return array
    pivot_idx = 0
    pivot = array[pivot_idx]
    less_part = [array[i] for i in range(size) if array[i] <= pivot and pivot_idx != i]
    great_part = [array[i] for i in range(size) if array[i] > pivot and pivot_idx != i]
    print(less_part, pivot, great_part)
    return quicksort(less_part) + [pivot] + quicksort(great_part)

def test_quicksort():
    seq = [15, 49, 9, 10, 23, 4, 2, 5]
    aa = quicksort(seq)
    print('aa')
    print(aa)
    # assert quicksort(seq) == sorted(seq)

def partition(array, beg, end):
    print(array)
    pivot_index = beg
    pivot = array[pivot_index]
    left = pivot_index + 1
    right = end - 1
    while True:
        while left <= right and array[left] < pivot:
            left += 1
        while right >= left and array[right] >= pivot:
            right -= 1
        if left > right:
            break
        else:
            array[left], array[right] = array[right], array[left]

    array[pivot_index], array[right] = array[right], array[pivot_index]
    return right

# def quicksort_inplace(array, beg, end):
#     if beg < end:
#         pivot = partition(array, beg, end)
#         quicksort_inplace(array, beg, pivot)
#         quicksort_inplace(array, pivot+1, end)

def test_partition(seq11):
    # l = [4, 1, 2, 8, 1, 49, 9, 10, 23, 5]
    partition(seq11, 0, len(seq11))

if __name__ == '__main__':
    seq11 = list(range(10))
    random.shuffle(seq11)
    seq = [1, 49, 9, 10, 23, 4, 72, 45]
    #test_quicksort()
    startt = time.time()
    test_partition(seq)
    time.sleep(1)
    print(time.time() - startt)