排序就是把一组对象按照指定的条件（升序或倒序）重新排列的过程。

01 - 思考

开始前不妨思考以下几个问题：

  • 想一想什么是排序呢？
  • 想一想怎么描述排序的效率？时间复杂度，空间复杂度

02 - 常见排序

本文中的代码使用的 Swift，默认排序是升序排序，其他的大同小异，这里不一一赘述了。

选择排序

排序方法：

  1. 遍历过程为从一个元素到倒数第二个元素。
  2. 在遍历中，要执行的操作是每次从当前元素之后的序列中，寻找最小元素，然后与当前元素交换，然后再处理下一个元素。
1
2
3
4
5
6
7
8
9
10
11
func selection(_ numbers: inout [Int]) {
    guard numbers.count > 1 else { return }
    
    for indexI in 0..<numbers.count-1 {
        var minIndex = indexI
        for indexJ in minIndex+1..<numbers.count {
            minIndex =  numbers[indexJ] < numbers[minIndex] ? indexJ : minIndex
        }
        numbers.swapAt(indexI, minIndex)
    }
}

冒泡排序

排序方法：

  1. 遍历过程为多趟逐次递减遍历，即第一次遍历到最后一个元素，第二次为倒数第二个元素，直到第一个元素为止。
  2. 在每次遍历中，要执行的操作是，依次比较当前元素和下一个元素的值，不满足条件则交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func bubble(_ numbers: inout [Int]) {
    guard numbers.count > 1 else {
        return
    }
    
    var total = numbers.count
    while total > 0 {
        
        var changed = false
        var index = 0
        while index < numbers.count-1 {
            if numbers[index] > numbers[index+1] {
                numbers.swapAt(index, index+1)
                changed = true
            }
            index += 1
        }
        if !changed {
            break
        }
        
        total -= 1
    }
}

插入排序

排序方法：

  1. 遍历过程为从第二个元素遍历到最后一个元素。
  2. 遍历中执行的操作是从当前元素之前的队列中，找到要插入的位置后，将当前元素插入到序列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func insert(_ numbers: inout [Int], gap: Int = 1) {
    guard numbers.count > 1 else { return }
    
    for g in 0..<gap {
        var i = g
        while i < numbers.count {
            var current = i
            while current-gap >= 0 && numbers[current-gap] > numbers[current] {
                numbers.swapAt(current, current-gap)
                current -= gap
            }
            
            i += gap
        }
    }
}

希尔排序

希尔排序是对插入排序的改进，是一种增量递减排序。

排序方法：

  1. 首先生成一个增量递减序列，一般是 n / 2。
  2. 遍历增量递减序列种，对于每一个增量 gap，要执行的操作是，对数组中依次相距 gap 的序列进行插入排序。增量序列遍历完得到的数组就是排序后数组。
1
2
3
4
5
6
7
8
9
func shell(_ numbers: inout [Int]) {
    guard numbers.count > 1 else { return }
    
    var gap = numbers.count / 2
    while gap != 0 {
        insert(&numbers, gap: gap)
        gap = gap / 2
    }
}

归并排序

排序方法：

  1. 对数组中的元素进行递归分割，直到每个序列只包含一个元素为止。
  2. 有序合并分割后的每个序列，合并后数组就是排序后的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func merge(_ numbers: [Int]) -> [Int] {
    return divide(nums)
}

/// 分割
func divide(_ numbers: [Int]) -> [Int] {
    guard numbers.count > 1 else { return numbers }
    
    let mid = (0+numbers.count-1)/2
    let leftNumbers = divide(Array(numbers[0...mid]))
    let rightNumbers = divide(Array(numbers[mid+1..<numbers.count]))
    return join(leftNumbers, rightNumbers)
}

/// 合并
func join(_ leftNumbers: [Int], _ rightNumbers: [Int]) -> [Int] {
    var result = [Int]()
    
    var leftIndex = 0
    var rightIndex = 0
    while leftIndex < leftNumbers.count && rightIndex < rightNumbers.count {
        if leftNumbers[leftIndex] <= rightNumbers[rightIndex] {
            result.append(leftNumbers[leftIndex])
            leftIndex += 1
        } else {
            result.append(rightNumbers[rightIndex])
            rightIndex += 1
        }
    }
    
    if leftIndex < leftNumbers.count {
        result.append(contentsOf: Array(leftNumbers[leftIndex..<leftNumbers.count]))
    }
    if rightIndex < rightNumbers.count {
        result.append(contentsOf: Array(rightNumbers[rightIndex..<rightNumbers.count]))
    }
    
    return result
}

快速排序

排序方法：

  1. 以序列中间元素为基准，将序列重组为小于中间元素，等于中间元素，大于中间元素的三个部分。
  2. 递归地对小于中间元素序列、大于中间元素序列执行操作1，直到子序列的个数等于1为止，此时得到的数组就是排序后的数组。
1
2
3
4
5
6
7
8
9
10
11
12
func quick(_ numbers: [Int]) -> [Int] {
    guard numbers.count > 1 else {
        return numbers
    }
    
    let pivot = numbers[numbers.count/2]
    let less = numbers.filter { $0 < pivot }
    let equal = numbers.filter { $0 == pivot }
    let greater = numbers.filter { $0 > pivot }
    
    return quick(less) + equal + quick(greater)
}

计数排序

排序方法：

  1. 生成一个下标最小为0，最大为数组中最大值，值为0的一个统计序列。
  2. 遍历数组中的元素，以元素的值为 index，增加统计序列的出现次数。
  3. 遍历统计序列，根据出现次数，生成排序后的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func count(_ numbers: [Int]) -> [Int]{
    guard numbers.count > 1 else {
        return numbers
    }
    
    // 计数
    let maxVal = numbers.max()!
    var counts = Array(repeating: 0, count: maxVal+1)
    for element in numbers {
        counts[element] += 1
    }
    
    // 重组
    var result = numbers
    var resultIndex = 0
    for (index, val) in counts.enumerated() {
        for _ in 0..<val {
            result[resultIndex] = index
            resultIndex += 1
        }
    }
    return result
}

基数排序

排序方法：

  1. 生成一个下标为0，最大值为9的暂存序列。
  2. 寻找数组中值最大的元素，统计其位数。
  3. 从最低位开始，循环的执行操作4，循环完成后得到的数组就是排序后的数组。
  4. 将数组中的元素，按照相应位上数值分到暂存系列中，分完再将暂存序列合并后的数组赋值给原数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func radix(_ numbers: [Int]) -> [Int] {
    guard numbers.count > 1 else {
        return numbers
    }
    
    let totalDigit = getTotalDigit(numbers.max()!)
    var tempts = Array(repeating: [Int](), count: 10)
    var result = numbers
    
    for digit in 0..<totalDigit {
        // 按照指定 digit 进行分类
        tempts = Array(repeating: [Int](), count: 10)
        for element in result {
            let index = getDigit(element, digit)
            tempts[index].append(element)
        }
        // 合并
        result = tempts.flatMap { $0 }
    }
    return result
}

/// 获取数值的总位数
func getTotalDigit(_ number: Int) -> Int {
    guard number > 0 else {
        return 1
    }
    
    var length = 0
    var target = 1
    while number >= target {
        length += 1
        target *= 10
    }
    return length
}

/// 获取数值相应位上的数字
func getDigit(_ number: Int, _ Index: Int) -> Int{
    let num1 = pow(10, Index+1)
    let num2 = pow(10, Index)
    return number % num1 / num2
}

/// 计算 x 的 y 次方
func pow(_ x: Int, _ y: Int) -> Int {
    var result = 1
    for _ in 0..<y {
        result *= x
    }
    return result
}

桶排序

排序方法：

  1. 生成一个元素类型是数组，总个数为 n 的的空序列，序列中的每个数组可以理解为一个桶。
  2. 找出数组最大值，最小值，将它们的差除以桶的总个数得到值就是每个桶的容量。
  3. 确定每个桶允许放入元素的数值范围后，遍历数组中的元素，将元素放入到每个桶中，使桶中的元素也是有序排列。
  4. 将包含桶的序列合并成一个新的数组就是排序后的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func bucket(_ numbers: [Int]) -> [Int] {
    guard numbers.count > 0 else { return numbers}
    
    let totalBucket = 10
    var buckets = Array(repeating: [Int](), count: totalBucket)
    let minVal = numbers.min()!
    let maxVal = numbers.max()!

    for element in numbers {
        let bucketIndex = getBucketIndex(element, minVal, maxVal, totalBucket)
        addElementToBucket(&buckets[bucketIndex], element)
    }
    
    return buckets.flatMap { $0 }
}

/// 获取要加入桶的 index
func getBucketIndex(_ element: Int, _ minVal: Int, _ maxVal: Int, _ totalBucket: Int) -> Int {
    var index = 0
    let capacity = Double(maxVal-minVal) / Double(totalBucket)
    var target = capacity
    while Double(element-minVal) > target {
        target += capacity
        index += 1
    }
    return index
}

/// 桶内新增元素并排序
func addElementToBucket(_ bucket: inout [Int], _ element: Int) {
    bucket.append(element)
    // sort
    var index = bucket.count - 1
    while index - 1 >= 0 && bucket[index-1] > bucket[index] {
        bucket.swapAt(index-1, index)
        index -= 1
    }
}

堆排序

排序方法：

  1. 将数组中的元素构建成最大堆结构后，第一个元素与最后一个元素交换。
  2. 对去掉最后一个元素的数组继续执行操作1，直到数组中元素的个数为0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 堆排序
func heap(_ numbers: inout [Int]) {
    var lastIndex = numbers.count - 1
    while lastIndex >= 0 {
        buildHeap(&numbers, lastIndex)
        numbers.swapAt(0, lastIndex)
        lastIndex -= 1
    }
}

// 构建最大堆
func buildHeap(_ numbers: inout [Int], _ lastIndex: Int) {
    var parent = (lastIndex - 1) / 2
    while parent >= 0 {
        heapify(&numbers, parent, lastIndex)
        parent -= 1
    }
}

// 对指定 index 元素进行 heapify, lastIndex 数组的最后一个元素的 index
func heapify(_ numbers: inout [Int], _ index: Int, _ lastIndex: Int) {
    guard index < lastIndex else {
        return
    }
    
    let left = index * 2 + 1
    let right = index * 2 + 2
    var max = index
    if left <= lastIndex && numbers[left] > numbers[max] {
        max = left
    }
    if right <= lastIndex && numbers[right] > numbers[max] {
        max = right
    }
    if max != index {
        numbers.swapAt(index, max)
        heapify(&numbers, max, lastIndex)
    }
}