面试题总结

输入数字和字母混合的字符串，排序输出

    func sortStr(str:String) -> String  {
        let sortStr = str.characters.sorted()
        let text = sortStr.reduce("") { (a, c) -> String in
            return "\(a)" + "\(c)"
        }
        return text
    }

冒泡

for i in 0 ..< array.count {
    for j in 0 ..< array.count - 1 - i {
        if array[j] > array[j+1] {
            var  temp = array[j+1]
            array[j+1] = array[j]
            array[j] = temp
        }
    }
}

快排

//辅助空间快排
func quickSort(data:[Int])->[Int]{
        if data.count<=1 {
            return data
        }

        var left:[Int] = []
        var right:[Int] = []
        let pivot:Int = data[data.count-1]
        for index in 0..<data.count-1 {
            if data[index] < pivot {
                left.append(data[index])
            }else{
                right.append(data[index])
            }
        }

        var result = quickSort(data: left)
        result.append(pivot)
        let rightResult = quickSort(data: right)
        result.append(contentsOf: rightResult)
        return result
    }

// 经典快排
func partition( data:inout [Int],low:Int,high:Int) -> Int {

        let root = data[high]
        var index = low
        for i in low...high {
            if data[i] < root {
                if i != index {
                    swap(&data[i], &data[index])
                }
                index = index+1
            }
        }

        if high != index {
            swap(&data[high], &data[index])
        }
        return index
    }

    func quickSort(data:inout [Int],low:Int,high:Int) -> Void {
        if low > high {
            return
        }
        let sortIndex = partition(data: &data, low: low, high: high)
        quickSort(data: &data, low: low, high: sortIndex-1)
        quickSort(data: &data, low: sortIndex+1, high: high)
    }