# 04.快速排序

### 一、 什么是快速排序

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

### 二、 核心流程

1. 选取一个基准元素
2. 以该元素为基准，将比该元素大的放到右侧，小的放在左侧，从而一趟排序就可以确定基准元素的位置
3. 对左右两个分块重复上面的步骤（递归）
4. 直到所有元素都是有序的

### 三、 流程图

> 来自：[MOBIN](https://www.cnblogs.com/MOBIN/p/4681369.html)

![流程图](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-8fcd4fa92416de67bf48aed7fde53f0dfab90c87%2F%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.png?alt=media)

### 四、 方案一：辅助空间

```
func quickSort<T: Comparable>(_ arr: [T]) -> [T] {
    guard let base = arr.first, arr.count > 1 else {
        return arr
    }
    
    var left: [T] = []
    var right: [T] = []
    var result: [T] = []

    for index in 1..<arr.count {
        let value = arr[index]
        if value < base {
            left.append(value)
        }
        else {
            right.append(value)
        }
    }
    
    print("left = \(left)   right = \(right) ")
    
    result = quickSort(left)
    result.append(base)
    result.append(contentsOf: quickSort(right))
    
    return result
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/04.-kuai-su-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.