毛老师算法分析课作业快速排序法

算法描述：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

# -*- coding: utf-8 -*-
# @Time    : 18-9-18 上午11:00
# @Author  : Guo Zhengbing
# @Email   : cn_gzb@126.com
import random
def random_int_list(start, stop, length):
    start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
    length = int(abs(length)) if length else 0
    random_list = []
    for i in range(length):
        random_list.append(random.randint(start, stop))
    return random_list
a = random_int_list(1,1000,15)
        #快速法排序
def sub_sort(array,low,high):
    key = array[low]
    while low < high:
        while low < high and array[high] >= key:
            high -= 1
        while low < high and array[high] < key:
            array[low] = array[high]
            low += 1
            array[high] = array[low]
    array[low] = key
    return low

def quick_sort(array,low,high):
     if low < high:
        key_index = sub_sort(array,low,high)
        quick_sort(array,low,key_index)
        quick_sort(array,key_index+1,high)

if __name__ == '__main__':
    array = a
    print(array)
    quick_sort(array,0,len(array)-1)
    print(array)

结果：

befor: [1000, 681, 230, 182, 424, 855, 699, 957, 312, 901, 933, 360, 657, 109, 67, 755, 993, 871, 801, 561]
later: [67, 109, 182, 230, 312, 360, 424, 561, 657, 681, 699, 755, 801, 855, 871, 901, 933, 957, 993, 1000]