算法学习（二）

上一篇算法学习(一)主要介绍了一下算法大体框架，以及以swift编程语言为基础的抽象数据结构实现。
其中实现了
二分法查询算法

//数据源必须已经升序排列
 class public func BinarySearch(_ target:Int,_ source:Array<Int>)->Int
    {
        let start:Int = 0
        var hightIndex = source.count-1
        while start<=hightIndex {
            //中间值
            let mid = start+(hightIndex-start)/2
            //改变最大下标来缩小范围
            if target<source[mid]
            {
                hightIndex = mid-1
            }
            else if target>source[mid]
            {
                hightIndex = mid+1
            }
            else
            {
                return mid
            }
        }
        return -1
    }

排序

初级排序算法

插入排序
插入排序是一种需要将其余所有元素在插入之前都想右移动一位的算法。当前索引之前的元素都是有序的，但是我们无法确定他们的最终位置。
插入排序所需的时间取决于数据源中的初始顺序。

//插入排序
class public func insertSort(_ source:NSArray) ->NSArray{
        let tmpArray = NSMutableArray.init(array: source)
        for i in 1...tmpArray.count-1
        {
            //索引逆序到1   而不是到0
            for j in (1...i).reversed(){
                if !(tmpArray[j] as!Double>tmpArray[j-1]as!Double) {
//                    let t = tmpArray[j-1]
//                    tmpArray[j-1] = tmpArray[j]
//                    tmpArray[j] = t
                    tmpArray.exchangeObject(at: j, withObjectAt: j-1)
                }
            }
        }
        return NSArray.init(array: tmpArray)
    }

选择排序
找到序列中最小的一个数，让他和当前索引进行交换，知道数组有序，这样的排序叫选择排序
算法的时间效率取决于比较的次数，也就是数组的长度

//选择排序
    class public func selection_sort(_ source:NSArray) ->NSArray{
        let tmpArray = NSMutableArray.init(array: source)
        for i in 0...tmpArray.count-1{
            var min = i //最小值下标
            if min+1 <= tmpArray.count-1 {
                for j in i+1...tmpArray.count-1{
                    let minx = tmpArray[min] as!Double
                    let next = tmpArray[j]  as!Double
                    if minx > next{
                        min = j
                    }
                }
                tmpArray.exchangeObject(at: i, withObjectAt: min)
            }
            
        }
        return tmpArray
    }

希尔排序
希尔排序的思想是使数组内任意间隔为h的元素都有序，这样的数组被称为h有序数组。在进行排序时，h很大时，就可以将元素移动很远，为实现更小的h有序创造了方便，这种方式，对于任何一个以1结尾的h序列，我们都能将这个数组排序。

//希尔排序
    class public func shell_sort(_ source:NSArray) -> NSArray {
        let tmpArray = NSMutableArray.init(array: source)
        //控制范围
        let area = 3
        //范围控制计数
        var h = 1
        //控制在h范围内有序
        while h < source.count/area {
            h = area * h + 1
        }
        
        while h >= 1 {
            for i in h...source.count-1 {
                for j in stride(from: i, through: h, by: -h) {
                    self.less(tmpArray, j, j-h)
                }
            }
            //当执行完h = 1时，排序完成
            h = h/area
        }
        
        return tmpArray
    }

也许不是每天记录一堂算法学习记录，一定会以高频率的方式记录总结实践学习到知识
Demo地址：https://github.com/StoneAi/Algorithms
持续更新

最后编辑于：2018.03.27 15:39:17

算法学习 （二）

排序

初级排序算法

算法学习（二）