面试时常见算法小结

一些最基本的算法并不限于iOS，在我们大学课本数据结构中就有介绍，这里使用 Swift 语言实现。

• 参考链接：iOS常见算法
• 我们通常说的排序算法的稳定性，是指待排序列中相同的两个元素在排序后是否位置发生变化，若变化，则是不稳定排序。
• 建议在项目中创建一个 .playground 文件进行练习。

网上找的各种算法的复杂度对比，这里并不去深入每个算法特性，仅说明如何使用。

复杂度对比

冒泡排序

每经过一轮排序，就将当前数组的最大值或者最小值放到最前面或者最后面，即每轮比较至少确定一个元素位置。每次比较相邻的两个元素，位置关系不满足要求时则调整两个元素间位置。

创建待操作数组
var operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]

// MARK: - 👉冒泡排序，稳定排序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
func bubbleSort(operatorArray array: inout [Int], assend isAscend: Bool) {
    for i in 0 ... (array.count - 2) {
        for j in 0 ... (array.count - 2 - i) {
            // 升序
            if isAscend {
                if array[j] > array[j + 1] {
                    let temp = array[j]
                    operatorArray[j] = array[j + 1]
                    array[j + 1] = temp
                }
            } else {
                // 降序
                if array[j] < array[j + 1] {
                    let temp = array[j]
                    operatorArray[j] = array[j + 1]
                    array[j + 1] = temp
                }
            }
        }
    }
}
// 对 operatorArray 数组进行 升序 排序
bubbleSort(operatorArray: &operatorArray, assend: true)
// 对 operatorArray 数组进行 降序 排序
bubbleSort(operatorArray: &operatorArray, assend: false)

选择排序

选择排序有点类似冒泡排序，区别是相比于冒泡排序，选择排序执行更多的是元素比较，冒泡排序更多的是执行元素交换，由于交换时占用的 CPU 资源会比比较的时候更多，所以当数组元素较少时，选择排序比冒泡排序更好些。当元素过多时，由于选择排序最好的时间复杂度仍未 O(n * n)，所以不如冒泡。

选择排序简单来说就是拿数组中的一个元素和数组中剩余的所有未确定顺序的元素对比，从待排序列中选出最大或者最小元素放在序列起始位置，每次确定一个元素位置，直到全部待排数据排完。

// MARK: - 👉选择排序，不稳定排序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
func selectionSort(operatorArray array: inout [Int], assend isAssend: Bool) {
    for i in 0 ..< array.count {
        var minIndex = i
        for j in (i + 1) ..< array.count {
            if isAssend {
                if array[minIndex] > array[j] {
                    minIndex = j
                }
            } else {
                if array[minIndex] < array[j] {
                    minIndex = j
                }
            }
        }
        if minIndex != i {
            (array[i], array[minIndex]) = (array[minIndex], array[i])
        }
    }
}
// 对 operatorArray 数组进行升序排序
selectionSort(operatorArray: &operatorArray, assend: true)

快速排序

快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分所有数据都比另外一部分所有数据都小，然后按照此方法对两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个序列都变成有序序列。

从待排序列中任意选择一个元素作为比较的基准（pivot），通常选用第一个元素。

// MARK: - 👉快速排序，不稳定排序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
func quickSort(operatorArray array: [Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }
    let pivot = array.first!
    var left = [Int]()
    var right = [Int]()
    
    for index in 1 ..< array.count {
        if array[index] < pivot {
            left.append(array[index])
        } else {
            right.append(array[index])
        }
    }
    var result = quickSort(operatorArray: left)
    result.append(pivot)
    let rightResult = quickSort(operatorArray: right)
    result.append(contentsOf: rightResult)
    return result
}
quickSort(operatorArray: operatorArray)

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列之间有序。将两个有序表合成一个有序表，成为二路归并。

所以，实现归并排序前，需要辅助方法：二路归并。

// MARK: - 👉二路归并
// 1.将两个有序数组合并
func mergerArray(_ firstArray: [Int], _ secondArray: [Int]) -> [Int] {
    var result = [Int]()
    var firstIndex = 0
    var secondIndex = 0
    while firstIndex < firstArray.count && secondIndex < secondArray.count {
        if firstArray[firstIndex] < secondArray[secondIndex] {
            result.append(firstArray[firstIndex])
            firstIndex += 1
        } else {
            result.append(secondArray[secondIndex])
            secondIndex += 1
        }
    }
    // 将剩余元素加到数组
    while firstIndex < firstArray.count {
        result.append(firstArray[firstIndex])
        firstIndex += 1
    }
    while secondIndex < secondArray.count {
        result.append(secondArray[secondIndex])
        secondIndex += 1
    }
    return result
}

利用二路归并方法，对一个无序序列进行归并排序：

// MARK: - 👉归并排序, 稳定排序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
// 2.排序一个无需数组
func sortArray(_ items: [Int]) -> [Int] {
    // 分化数组
    var tempArray = [[Int]]()
    items.forEach { digit in
        tempArray.append([digit])
    }
    
    // 开始合并
    while tempArray.count != 1 {
        var index = 0
        while (index + 1) < tempArray.count {
            print("\(tempArray[index]) 与 \(tempArray[index + 1]) 合并")
            tempArray[index] = mergerArray(tempArray[index], tempArray[index + 1])
            tempArray.remove(at: index + 1)
            index += 1
        }
    }
    
    return tempArray.first!
}
sortArray(operatorArray)

二分查找

又称为折半查找。要求待查询序列必须是有序的。这里分两种方式实现。

1、循环方式。传入待查询数组以及要查询的元素，返回结果为该元素下标，若序列中不存在该元素，则返回 -1。

// MARK: - 👉二分查找算法，又称为折半查找，要求数组必须有序，假设为升序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
// 1、循环
func binarySearchArray1(_ operatorArray: [Int], _ target: Int, _ start: inout Int, _ end: inout Int) -> Int {
    
    if start > end || end >= operatorArray.count {
        return -1
    }

    while start <= end {
        let mid = (start + end) / 2
        if operatorArray[mid] < target {
            start = mid + 1
        } else if operatorArray[mid] > target {
            end = mid - 1
        } else {
            return mid
        }
    }
    return -1
}
var startIndex = 0
var endIndex = operatorArray.count - 1
binarySearchArray1(operatorArray, 12, &startIndex, &endIndex)

2、递归方式

// 递归
func binarySearch(operatorArray array: [Int], targetElement target: Int, startIndex start: Int, endIndex end: Int) -> Int {
    if start > end || end >= array.count {
        return -1
    }
    
    let mid = start + (end - start) / 2
    if target > array[mid] {
        return binarySearch(operatorArray: array, targetElement: target, startIndex: mid + 1, endIndex: end)
    } else if target < array[mid] {
        return binarySearch(operatorArray: array, targetElement: target, startIndex: start, endIndex: mid - 1)
    } else {
        return mid
    }
}
binarySearch(operatorArray: operatorArray, targetElement: 9, startIndex: 0, endIndex: operatorArray.count - 1)

链表逆序

这里使用了元组的数据交换。并且方法本身是在原有的数组上操作的。如果想保留原有数组不改变，只需在方法中复制原有数组，并返回新建的数组即可。

// MARK: - 链表逆序
operatorArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
func reverseArray(operatorArray array: inout [Int]) {
    let mid = array.count / 2
    var index = 0
    while index <= mid {
        (array[index], array[array.count - index - 1]) = (array[array.count - index - 1], array[index])
        index += 1
    }
}
reverseArray(operatorArray: &operatorArray)

逆序输出一个字符串

这里主要使用了 String 的一些基本方法。

// MARK: - 逆序输出一个字符串
func reverseString(_ str: String) -> String {

    var tempArray1 = str.characters
    var tempArray2 = str.characters
    
    var tempCharacters = ""
    
    // 用来组建逆序字符串
    tempArray1.forEach { char in
        tempCharacters.append(tempArray1.removeLast())
    }
    
    // 用来输出展示
    tempArray2.forEach { char in
        print(tempArray2.removeLast())
    }
    
    return tempCharacters
}
reverseString("Hello")

查询一个字符串中唯一出现并且最靠前的字符

// MARK: - 字符串中只出现一次且最靠前的字符‘
func compartDifferentChar(_ str: String) -> (index: Int, char: Character?) {
    var strArray = str.characters
    var isOnly = true
        for i in strArray.enumerated() {
        strArray.removeFirst()
        isOnly = true
        strArray.forEach { j in
            if i.element == j {
                isOnly = false
            }
        }
        if isOnly == true {
            return (i.offset, i.element)
        }
    }
    return (-1, nil)
}
compartDifferentChar("asfghjkadhsg")