归并排序（Swift）

归并排序.jpg

最近在学习算法，归并排序和快速排序都用到分治思想，编程实现方式是通过递归。本文旨在给Swift语言开发者提供编程思路，具体什么是归并和快排就不做详细介绍了，毕竟各种书籍和文章很容易搜索。。

归并排序，本文包含三个函数，进行排序的函数是func merge()，merge（）注意细节是参数是有序数组。

由于之前一直是OC开发，对Swift不熟，所数组的操作浪费了自己很多时间，还好实现出来了，代码如下，提供给大家参考，也欢迎指正...

class Sort {

   // 合并有序数组
    private func merge(_ array1:[Int], _ array2:[Int])->[Int]{
        
        var a = [Int]()
        let m = array1.count
        let n = array2.count
        
        var i:Int = 0
        var j:Int = 0
        
        while i<m && j<n {
            if array1[i] <= array2[j] {
                a.append(array1[i])
                i += 1
            }else{
                a.append(array2[j])
                j += 1
            }
        }
        
        if i == m {
            a += array2[j..<n]
        }else{
            a += array1[i..<m]
        }
        return a
    }
    // 递归分解
    private func mergeSortC(_ array:[Int]) -> [Int]{
        if array.count <= 1 {
            print("count = 1,array:\(array)")
            
            return array
        }
        print(array)
        let tmpArray = array
        let n = array.count
        let q = (0+n-1)/2
        
        let leftArray = mergeSortC(Array(tmpArray[0...q]))
        let rightArray = mergeSortC(Array(tmpArray[q+1...n-1]))

        return merge(leftArray,rightArray)

    }

    // 排序对外函数
    public func mergeSort(array:[Int]) -> [Int] {
        let b:[Int] = mergeSortC(array)
        return b
    }
}

函数调用：

var sort = Sort()
let array = sort.mergeSort(array: [11,8,3,9,7,1,2,5])
print(array)

控制台输出:
[1, 2, 3, 5, 7, 8, 9, 11]