#!/usr/bin/env python

# -*- coding: utf-8 -*-

# 快速排序

# 时间复杂度 O(n lgn)-- O(n^2)

def quick_sort(array):

    if len(array) <= 1:

        return array

    left = quick_sort([i for i in array[1:] if i >= array[0]])

    right = quick_sort([i for i in array[1:] if i < array[0]])

    return left + array[0:1] + right

if __name__ == '__main__':

    aa = [4, 1, 4, 3, 5, 6, 2, 6, 0, 0]

    a = quick_sort(aa)

    print(a)

package main

import "fmt"

func quickSort(array []int) []int {

    if len(array) <= 1 {

        return array

    }else {

        left := make([]int, 0)

        right := make([]int, 0)

        for _, v := range array[1:] {

            if v < array[0] {

                left = append(left, v)

            } else {

                right = append(right, v)

            }

        }

        left = quickSort(left)

        right = quickSort(right)

        left = append(left, array[0: 1]...)

        left = append(left, right...)

        return left

    }

}

func main() {

    aa := []int{4, 1, 4, 3, 5, 6, 2, 6, 0, 8}

    a := quickSort(aa)

    fmt.Println(a)

}