快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

func QuickSort<T: Comparable>(dest:[T])->[T]{
    guard dest.count > 1 else {
        return dest
    }
    let middle = dest[dest.count/2]
    
    let bigger = dest.filter { (t:T) -> Bool in
        return t > middle
    }
    let equal = dest.filter { (t:T) -> Bool in
        return t == middle
    }
    let less = dest.filter { (t:T) -> Bool in
        return t < middle
    }
    let finally = QuickSort(dest: less) + equal + QuickSort(dest: bigger)
    return finally
}

测试用例

var test1 = [1,2,-1,34,3434,3434,3,2,4,3,243,23,34,3434,32,-2,0,0,343443,54,25]
print(QuickSort(dest: test1))

结果

快速排序结果