# 06.冒泡排序

### 一、 常规冒泡

```
func bubbleSortA(nums: [Int]) -> [Int] {
    var nums = nums
    let count = nums.count
    
    for i in 0..<count {
        print("<")
        for j in (i + 1)..<count {
            if nums[i] > nums[j] {
                nums.swapAt(i, j)
            }
            print(nums)
        }
        print(">\n")
    }
    
    return nums
}
```

### 二、 外层优化

当发现在某一趟排序中没有发生交换，则说明排序已经完成，所以可以在此趟排序后结束排序，在每趟排序前设置flag，当其未发生变化时，终止算法

```
func bubbleSortB(nums: [Int]) -> [Int] {
    print("bubbleSortB")
    
    var nums = nums
    let count = nums.count
    
    for i in 0..<count {
        var swapFlag = true
        print("<")
        for j in (i + 1)..<count {
            if nums[i] > nums[j] {
                nums.swapAt(i, j)
                swapFlag = false
            }
            print(nums)
        }
        print(">\n")
        if swapFlag {
            break
        }
    }
    
    return nums
}
```

### 三、 内层优化

在每趟排序中，右面的许多元素已经是有序的结果了，可算法还是进行后面数值的排序，因此进行第二次优化

```
func bubbleSortC(nums: [Int]) -> [Int] {
    print("bubbleSortC")
    
    var nums = nums
    var boundary = nums.count - 1
    var lastSwapIdx = 0
    
    for _ in 0..<nums.count {
        var swapFlag = true
        print("<")
        for j in 0..<boundary {
            if nums[j] > nums[j+1] {
                nums.swapAt(j, j+1)
                swapFlag = false
                lastSwapIdx = j
            }
            print(nums)
        }
        print(">\n")
        boundary = lastSwapIdx
        if swapFlag {
            break
        }
    }
    
    return nums
}
```

### 四、 对比

```
let numbers: [Int] = [3, 5, 1, 11, 2, 4, 12]

bubbleSortA(nums: numbers)
bubbleSortB(nums: numbers)
bubbleSortC(nums: numbers)
```

输出：

```
<
[3, 5, 1, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
>

<
[1, 3, 5, 11, 2, 4, 12]
[1, 3, 5, 11, 2, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
>

<
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
>

<
[1, 2, 3, 5, 11, 4, 12]
[1, 2, 3, 4, 11, 5, 12]
[1, 2, 3, 4, 11, 5, 12]
>

<
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>

<
[1, 2, 3, 4, 5, 11, 12]
>

<
>

bubbleSortB
<
[3, 5, 1, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
>

<
[1, 3, 5, 11, 2, 4, 12]
[1, 3, 5, 11, 2, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
>

<
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
>

<
[1, 2, 3, 5, 11, 4, 12]
[1, 2, 3, 4, 11, 5, 12]
[1, 2, 3, 4, 11, 5, 12]
>

<
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>

<
[1, 2, 3, 4, 5, 11, 12]
>

bubbleSortC
<
[3, 5, 1, 11, 2, 4, 12]
[3, 1, 5, 11, 2, 4, 12]
[3, 1, 5, 11, 2, 4, 12]
[3, 1, 5, 2, 11, 4, 12]
[3, 1, 5, 2, 4, 11, 12]
[3, 1, 5, 2, 4, 11, 12]
>

<
[1, 3, 5, 2, 4, 11, 12]
[1, 3, 5, 2, 4, 11, 12]
[1, 3, 2, 5, 4, 11, 12]
[1, 3, 2, 4, 5, 11, 12]
>

<
[1, 3, 2, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>

<
[1, 2, 3, 4, 5, 11, 12]
>
```


---

# 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/06.-mao-pao-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.