快速排序

quick_sort.py

# !/usr/bin/python3
# coding=utf-8

# Time: O(n*logn)
# Space: O(n)

def qsort(arr):
    # 基线条件
    if len(arr) < 2:
        return arr
    else:
        # 基准值
        pivot = arr[0]
        less = []
        greater = []
        pivot_list = []
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                greater.append(i)
            else:
                pivot_list.append(i)
        return qsort(less) + pivot_list + qsort(greater)


if __name__ == "__main__":
  arr = [3,5,1,6,8,4,9]
  sorted_arr = qsort(arr)
  print(sorted_arr)