上一篇算法學(xué)習(xí)(一)主要介紹了一下算法大體框架短曾，以及以swift編程語(yǔ)言為基礎(chǔ)的抽象數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
其中實(shí)現(xiàn)了
二分法查詢算法
//數(shù)據(jù)源必須已經(jīng)升序排列
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
//改變最大下標(biāo)來縮小范圍
if target<source[mid]
{
hightIndex = mid-1
}
else if target>source[mid]
{
hightIndex = mid+1
}
else
{
return mid
}
}
return -1
}
排序
初級(jí)排序算法
插入排序
插入排序是一種需要將其余所有元素在插入之前都想右移動(dòng)一位的算法翰意。當(dāng)前索引之前的元素都是有序的，但是我們無法確定他們的最終位置。
插入排序所需的時(shí)間取決于數(shù)據(jù)源中的初始順序。
//插入排序
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)
}
選擇排序
找到序列中最小的一個(gè)數(shù)魏滚，讓他和當(dāng)前索引進(jìn)行交換，知道數(shù)組有序坟漱，這樣的排序叫選擇排序
算法的時(shí)間效率取決于比較的次數(shù)鼠次，也就是數(shù)組的長(zhǎng)度
//選擇排序
class public func selection_sort(_ source:NSArray) ->NSArray{
let tmpArray = NSMutableArray.init(array: source)
for i in 0...tmpArray.count-1{
var min = i //最小值下標(biāo)
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
}
希爾排序
希爾排序的思想是使數(shù)組內(nèi)任意間隔為h的元素都有序，這樣的數(shù)組被稱為h有序數(shù)組芋齿。在進(jìn)行排序時(shí)腥寇，h很大時(shí)，就可以將元素移動(dòng)很遠(yuǎn)觅捆，為實(shí)現(xiàn)更小的h有序創(chuàng)造了方便赦役，這種方式，對(duì)于任何一個(gè)以1結(jié)尾的h序列栅炒，我們都能將這個(gè)數(shù)組排序掂摔。
//希爾排序
class public func shell_sort(_ source:NSArray) -> NSArray {
let tmpArray = NSMutableArray.init(array: source)
//控制范圍
let area = 3
//范圍控制計(jì)數(shù)
var h = 1
//控制在h范圍內(nèi)有序
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)
}
}
//當(dāng)執(zhí)行完h = 1時(shí)，排序完成
h = h/area
}
return tmpArray
}
也許不是每天記錄一堂算法學(xué)習(xí)記錄赢赊，一定會(huì)以高頻率的方式記錄總結(jié)實(shí)踐學(xué)習(xí)到知識(shí)
Demo地址：https://github.com/StoneAi/Algorithms
持續(xù)更新
