func partition(inout list : [Int], low: Int, high : Int) -> Int {
    let pivot = list[high]
    var j = low
    var i = j - 1
    while j < high {
        if list[j] <= pivot{
            i += 1
            (list[i], list[j]) = (list[j], list[i])
        }
        j += 1
    }
    (list[i+1], list[high]) = (list[high], list[i+1])
    return i+1
}

func quikcSort(inout list : [Int] , low : Int , high : Int) {

    if low < high {
        let pIndex = partition(&list, low: low, high: high)
        quikcSort(&list, low: low, high: pIndex-1)
        quikcSort(&list, low: pIndex + 1, high: high)
    }
}

var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)

var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)

var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1) 

这是我的博客关于快速排序- Github样本快速排序

您可以在partitioning the list中查看Lomuto的分区算法。用Swift编写。

摘自Swift编程语言:

Swift的标准库提供了一个名为 类对已知类型的值数组进行排序 所提供的排序闭包的输出。一旦它完成 排序过程中，sort函数返回一个相同的新数组 类型和大小与旧的一样，其元素在正确的排序 秩序。

排序函数有两个声明。

允许你指定比较闭包的默认声明:

func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

第二个声明只接受一个参数(数组)，并且“硬编码以使用小于比较器”。

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

我在一个操场上测试了您代码的修改版本，添加了闭包，以便我可以更密切地监视函数，我发现当n设置为1000时，这个闭包被调用了大约11000次。

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

这不是一个有效的函数，我建议使用更好的排序函数实现。

编辑:

我看了一下维基百科的Quicksort页面，并为它写了一个Swift实现。以下是我在操场上使用的完整程序

import Foundation

func quickSort(inout array: Int[], begin: Int, end: Int) {
    if (begin < end) {
        let p = partition(&array, begin, end)
        quickSort(&array, begin, p - 1)
        quickSort(&array, p + 1, end)
    }
}

func partition(inout array: Int[], left: Int, right: Int) -> Int {
    let numElements = right - left + 1
    let pivotIndex = left + numElements / 2
    let pivotValue = array[pivotIndex]
    swap(&array[pivotIndex], &array[right])
    var storeIndex = left
    for i in left..right {
        let a = 1 // <- Used to see how many comparisons are made
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Move pivot to its final place
    return storeIndex
}

let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = Int(arc4random())
}

quickSort(&x, 0, x.count - 1) // <- Does the sorting

for i in 0..n {
    x[i] // <- Used by the playground to display the results
}

当n=1000时，我发现

quickSort()被调用了大约650次， 大约进行了6000次互换， 大约有10,000个比较

似乎内置的排序方法是(或接近)快速排序，并真的很慢…

Swift Array性能回顾:

我写了自己的比较Swift和C/Objective-C的基准测试。我的基准计算质数。它使用之前的素数数组来寻找每个新的候选素数中的素数因子，所以它非常快。然而，它做了大量的数组读取，而很少写入数组。

我最初是针对Swift 1.2做这个基准测试的。我决定更新项目，并在Swift 2.0上运行它。

该项目允许您选择使用普通swift数组和使用swift不安全内存缓冲区使用数组语义。

对于C/Objective-C，你可以选择使用nsarray或C malloc'ed数组。

对于最快、最小的代码优化([-0s])或最快、积极的优化([-0fast])，测试结果似乎非常相似。

在关闭代码优化后，Swift 2.0的性能仍然很糟糕，而C/Objective-C的性能只是稍微慢一些。

最重要的是，基于C malloc数组的计算是最快的

当使用最快、最小的代码优化时，Swift不安全缓冲区的时间比C malloc数组长1.19 - 1.20倍。在快速、积极的优化中，差异似乎略小(Swift比C多花1.18到1.16倍的时间。

如果使用常规Swift数组，与C语言的区别会稍微大一些。(Swift要长1.22 - 1.23)

常规的Swift数组比Swift 1.2/Xcode 6中要快得多。它们的性能非常接近Swift的基于不安全缓冲区的数组，使用不安全内存缓冲区似乎真的不值得再麻烦了，这是大的。

顺便说一句，Objective-C NSArray的性能很糟糕。如果你打算在两种语言中使用原生容器对象，Swift要快得多。

你可以在github的SwiftPerformanceBenchmark上查看我的项目

它有一个简单的UI，让收集统计数据非常容易。

有趣的是，现在在Swift中排序似乎比在C中稍微快一些，但这个质数算法在Swift中仍然更快。

其他人提到但没有充分指出的主要问题是-O3在Swift中什么都不做(从来没有)，所以当用它编译时，它实际上是非优化的(-Onone)。

选项名称随着时间的推移而更改，因此一些其他答案的构建选项标志已过时。正确的当前选项(Swift 2.2)是:

-Onone // Debug - slow
-O     // Optimised
-O -whole-module-optimization //Optimised across files

整个模块优化有一个较慢的编译，但可以优化跨文件在模块内，即在每个框架内和在实际的应用程序代码，但不能在它们之间。你应该在任何性能关键的情况下使用它)

You can also disable safety checks for even more speed but with all assertions and preconditions not just disabled but optimised on the basis that they are correct. If you ever hit an assertion this means that you are into undefined behaviour. Use with extreme caution and only if you determine that the speed boost is worthwhile for you (by testing). If you do find it valuable for some code I recommend separating that code into a separate framework and only disabling the safety checks for that module.

通过这个基准测试，Swift 1.0现在和C一样快，使用默认的发布优化级别[-O]。

---

下面是Swift测试版中的就地快速排序:

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {
    if (end - start < 2){
        return
    }
    var p = a[start + (end - start)/2]
    var l = start
    var r = end - 1
    while (l <= r){
        if (a[l] < p){
            l += 1
            continue
        }
        if (a[r] > p){
            r -= 1
            continue
        }
        var t = a[l]
        a[l] = a[r]
        a[r] = t
        l += 1
        r -= 1
    }
    quicksort_swift(&a, start, r + 1)
    quicksort_swift(&a, r + 1, end)
}

在C中也是一样:

void quicksort_c(int *a, int n) {
    if (n < 2)
        return;
    int p = a[n / 2];
    int *l = a;
    int *r = a + n - 1;
    while (l <= r) {
        if (*l < p) {
            l++;
            continue;
        }
        if (*r > p) {
            r--;
            continue;
        }
        int t = *l;
        *l++ = *r;
        *r-- = t;
    }
    quicksort_c(a, r - a + 1);
    quicksort_c(l, a + n - l);
}

这两个工作:

var a_swift:CInt[] = [0,5,2,8,1234,-1,2]
var a_c:CInt[] = [0,5,2,8,1234,-1,2]

quicksort_swift(&a_swift, 0, a_swift.count)
quicksort_c(&a_c, CInt(a_c.count))

// [-1, 0, 2, 2, 5, 8, 1234]
// [-1, 0, 2, 2, 5, 8, 1234]

两者都在编写的程序中调用。

var x_swift = CInt[](count: n, repeatedValue: 0)
var x_c = CInt[](count: n, repeatedValue: 0)
for var i = 0; i < n; ++i {
    x_swift[i] = CInt(random())
    x_c[i] = CInt(random())
}

let swift_start:UInt64 = mach_absolute_time();
quicksort_swift(&x_swift, 0, x_swift.count)
let swift_stop:UInt64 = mach_absolute_time();

let c_start:UInt64 = mach_absolute_time();
quicksort_c(&x_c, CInt(x_c.count))
let c_stop:UInt64 = mach_absolute_time();

这将绝对时间转换为秒:

static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;

mach_timebase_info_data_t timebase_info;

uint64_t abs_to_nanos(uint64_t abs) {
    if ( timebase_info.denom == 0 ) {
        (void)mach_timebase_info(&timebase_info);
    }
    return abs * timebase_info.numer  / timebase_info.denom;
}

double abs_to_seconds(uint64_t abs) {
    return abs_to_nanos(abs) / (double)NANOS_PER_SEC;
}

下面是编译器优化级别的总结:

[-Onone] no optimizations, the default for debug.
[-O]     perform optimizations, the default for release.
[-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.

对于n=10_000，使用[-Onone]，时间单位为秒:

Swift:            0.895296452
C:                0.001223848

下面是Swift对于n=10_000的内置sort():

Swift_builtin:    0.77865783

下面是n=10_000时的[-O]:

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

如你所见，Swift的性能提高了20倍。

根据mweathers的回答，设置[-Ofast]会产生真正的区别，导致n=10_000的时间:

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

对于n=1_000_000:

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

为了进行比较，当n=1_000_000时，使用[-Onone]:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

因此，在开发的这个阶段，没有优化的Swift几乎比C慢了1000倍。另一方面，当两个编译器都设置为[-Ofast] Swift时，实际上至少和C一样好，如果不是稍微好一点的话。

有人指出，[-Ofast]改变了语言的语义，使其具有潜在的不安全性。这是苹果在Xcode 5.0发布说明中所说的:

一个新的优化级别-Ofast，在LLVM中可用，支持积极的优化。ofast放宽了一些保守的限制，主要针对浮点运算，这对大多数代码都是安全的。它可以从编译器中获得显著的高性能。

他们几乎都主张这样做。我不能说这是否明智，但据我所知，如果你不做高精度浮点运算，并且你确信在你的程序中不可能有整数或数组溢出，那么在发布版中使用[-Ofast]似乎是足够合理的。如果你确实需要高性能和溢出检查/精确的算术，那么现在选择另一种语言。

Beta 3更新:

n=10_000 with [-O]:

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift总体上要快一些，而且Swift的内置排序似乎有了很大的变化。

最后更新:

[-Onone]:

Swift:   0.678056695
C:       0.000973914

[o]:

Swift:   0.001158492
C:       0.001192406

[-Ounchecked]:

Swift:   0.000827764
C:       0.001078914

func partition(inout list : [Int], low: Int, high : Int) -> Int {
    let pivot = list[high]
    var j = low
    var i = j - 1
    while j < high {
        if list[j] <= pivot{
            i += 1
            (list[i], list[j]) = (list[j], list[i])
        }
        j += 1
    }
    (list[i+1], list[high]) = (list[high], list[i+1])
    return i+1
}

func quikcSort(inout list : [Int] , low : Int , high : Int) {

    if low < high {
        let pIndex = partition(&list, low: low, high: high)
        quikcSort(&list, low: low, high: pIndex-1)
        quikcSort(&list, low: pIndex + 1, high: high)
    }
}

var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)

var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)

var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1) 

这是我的博客关于快速排序- Github样本快速排序

您可以在partitioning the list中查看Lomuto的分区算法。用Swift编写。