前言
受visualgo這個(gè)網(wǎng)站啟發(fā)突勇，于是想要實(shí)現(xiàn)一個(gè)iOS版的排序動(dòng)畫(huà)演示版悯嗓，本篇主要介紹如何用swift3寫(xiě)一個(gè)帶有演示效果快速排序摸柄。同時(shí)希望以這種方式幫助大家趣味性沥寥、具體性的在腦海里形成回路來(lái)學(xué)習(xí)算法
你也可以在我的GitHub中下載源碼github Example
如有錯(cuò)誤歡迎指正碍舍，同時(shí)歡迎在GitHub上提issue
QuickSort.gif
提供自定義配置
需修改請(qǐng)參考QuickSortViewController.swift文件上部進(jìn)行修改
let JVMaxNumber:UInt32 = 50 //產(chǎn)生隨機(jī)數(shù)的最大值
let sleepTime:UInt32 = 300000 //1 sec = 1000000 休眠時(shí)間可調(diào)整動(dòng)畫(huà)快慢
let numberCount=13 //多少個(gè)待排序的數(shù)
let normalColor:UIColor = UIColor.init(red: 172/255, green: 216/255, blue: 231/255, alpha: 1.0)
let pivotColor:UIColor = UIColor.init(red: 255/255, green: 255/255, blue: 2/255, alpha: 1.0)
let currentColor:UIColor = UIColor.init(red: 220/255, green: 20/255, blue: 60/255, alpha: 1.0)
let minColor:UIColor = UIColor.init(red: 60/255, green: 179/255, blue: 113/255, alpha: 1.0)
let maxColor:UIColor = UIColor.init(red: 153/255, green: 51/255, blue: 204/255, alpha: 1.0)
let endColor:UIColor = UIColor.init(red: 255/255, green: 165/255, blue: 0/255, alpha: 1.0)
關(guān)鍵代碼
定義類(lèi)和接口
在下手之前，我們要構(gòu)思好我們要寫(xiě)的東西营曼，先抽象出類(lèi)乒验、寫(xiě)好提供給外部調(diào)用的方法。這也是一種好習(xí)慣與君共勉
我們需要自定義一個(gè)渲染的View來(lái)渲染出圖表蒂阱，這里我們定義為JVgraphView锻全。
JVgraphView需要提供一些方法給ViewController調(diào)用
func drawGraph(array:Array<Int>)
func startSort()
同時(shí)我們還需要自定義一個(gè)每一個(gè)Item的View來(lái)展示當(dāng)前的數(shù)字狂塘、長(zhǎng)短、顏色鳄厌，我們把它命名為JVgraphItemView荞胡，提供如下方法
init(frame: CGRect,itemValue:Int)
func changeState(state:GIoptionState)
／／表示狀態(tài)的枚舉，根據(jù)狀態(tài)來(lái)轉(zhuǎn)換顏色
enum GIoptionState:Int{
case normal,pivot,current,min,max,end
}
填充定義方法
JVgraphItemView
注意 你將在本文多次見(jiàn)到 ** usleep(sleepTime)** 是為了讓動(dòng)畫(huà)演示過(guò)程中有停頓了嚎，為了讓UI不被卡住泪漂，都是在次線(xiàn)程中停頓，再返回到主線(xiàn)程渲染UI
//MARK: - init 根據(jù)frame 和當(dāng)前的數(shù)字 渲染每一個(gè)Item
init(frame: CGRect,itemValue:Int) {
super.init(frame: frame)
number=itemValue
oneHeight=self.frame.height/CGFloat(JVMaxNumber)
let gHeight=oneHeight*CGFloat(itemValue)
let y = self.frame.height-gHeight
ghView.frame=CGRect.init(x: 0, y: y, width: self.frame.width, height: gHeight)
self.addSubview(ghView)
／／大于臨界值的數(shù)字渲染在圖像里面
if itemValue>critical {
valueLabel.frame=CGRect.init(x: 0, y: y, width: self.frame.width, height: labelHeight)
}else{
valueLabel.frame=CGRect.init(x: 0, y: y-labelHeight, width: self.frame.width, height: labelHeight)
}
valueLabel.text=String(itemValue)
valueLabel.textColor=UIColor.black
valueLabel.textAlignment=NSTextAlignment.center
self.addSubview(valueLabel)
self.ghView.backgroundColor=normalColor
}
//根據(jù)狀態(tài)改變顏色
func changeState(state:GIoptionState) {
DispatchQueue.main.async(execute: {
switch state {
case .normal:
self.ghView.backgroundColor=normalColor
case .current:
self.ghView.backgroundColor=currentColor
case .pivot:
self.ghView.backgroundColor=pivotColor
case .min:
self.ghView.backgroundColor=minColor
case .max:
self.ghView.backgroundColor=maxColor
default:
self.ghView.backgroundColor=endColor
}
})
}
JVgraphView code
// MARK: - draw UI
func drawGraph(array:Array<Int>) {
self.clearView()
count=array.count
//計(jì)算item之間的間隙
gap=(self.frame.width-CGFloat(count)*itemWidth)/CGFloat(count+1)
//for 循環(huán)渲染 item
for i in 0..<count {
let item=array[i]
let view=JVgraphItemView.init(frame: self.getItemRect(item: CGFloat(i)),itemValue: item)
self.addSubview(view)
viewArray.append(view)
}
}
//計(jì)算每一個(gè)item的frame
func getItemRect(item:CGFloat) -> CGRect {
var x:CGFloat=0,y:CGFloat=0,w:CGFloat=0,h:CGFloat=0
x=item==0 ? gap : (item+1)*gap+item*itemWidth
y=0
w=itemWidth
h=self.frame.height
return CGRect.init(x: x, y: y, width: w, height: h)
}
在實(shí)現(xiàn)func startSort()的相應(yīng)之前呢 我們需要實(shí)現(xiàn)快速排序：
func quickSort(start:Int,end:Int)
func swap(changeIdx:Int,toIdx:Int)
func swap 最簡(jiǎn)單我們先從簡(jiǎn)單的開(kāi)始
func swap(changeIdx:Int,toIdx:Int){
if changeIdx==toIdx {
return
}
let view1=self.viewArray[changeIdx]
let view2=self.viewArray[toIdx]
let cRT:CGRect=view1.frame
let tRT:CGRect=view2.frame
／／交換兩個(gè)數(shù)據(jù)
let temporary:JVgraphItemView = self.viewArray[changeIdx]
self.viewArray[changeIdx]=self.viewArray[toIdx]
self.viewArray[toIdx]=temporary
usleep(sleepTime)
//創(chuàng)建信號(hào)量次線(xiàn)程等待主線(xiàn)程更新完畢之后在執(zhí)行
let semaphore = DispatchSemaphore(value: 0)
//在主線(xiàn)程更新UI
DispatchQueue.main.sync {
UIView.animate(withDuration: 0.25, animations: {
view1.frame=tRT
view2.frame=cRT
}, completion: { (finished) in
// 執(zhí)行完畢發(fā)送信號(hào)
semaphore.signal()
})
}
// 等待信號(hào)
semaphore.wait()
}
func quickSort的關(guān)鍵代碼和注釋
func quickSort(start:Int,end:Int) {
//把已經(jīng)完成排序的改變endColor
if start == end{
usleep(sleepTime)
self.viewArray[start].changeState(state: .end)
}
//跳出遞歸
if start>=end {
return;
}
let startItem = self.viewArray[start]
usleep(sleepTime)
// 改變基準(zhǔn)點(diǎn)顏色
startItem.changeState(state: .pivot)
let pivot:Int=startItem.number
var i:Int=start+1
var storeIndex:Int=i
while i<end+1 {
// 再進(jìn)行排序之前需要改變之前進(jìn)行過(guò)判斷的item的顏色
// 這里我是把之前的信息用Dictionary<JVgraphItemView,Bool>來(lái)存儲(chǔ)歪泳，
// 每次里面只有一個(gè)key和一個(gè)value 其他存儲(chǔ)方式也是可以的萝勤， Bool表示之前的大小,根據(jù)大小改變對(duì)應(yīng)的顏色
if lastItemDict.keys.count>0 {
for item:JVgraphItemView in (lastItemDict.keys) {
if (lastItemDict[item])!{
usleep(sleepTime)
item.changeState(state: .max)
}else{
usleep(sleepTime)
item.changeState(state: .min)
}
}
lastItemDict.removeAll()
}
// 改變當(dāng)前光標(biāo)顏色
let currentItem=self.viewArray[i]
usleep(sleepTime)
currentItem.changeState(state: .current)
//交換比較小的到大小相鄰的位置
if currentItem.number<pivot {
self.swap(changeIdx: i, toIdx: storeIndex)
storeIndex+=1
// 存儲(chǔ)大小信息
lastItemDict.updateValue(false, forKey: currentItem)
}else{
// 存儲(chǔ)大小信息
lastItemDict.updateValue(true, forKey: currentItem)
}
i += 1
}
self.swap(changeIdx: start, toIdx: storeIndex-1)
usleep(sleepTime)
// 除了已經(jīng)確定的基準(zhǔn)點(diǎn)以外的點(diǎn)全部的狀態(tài)改為normal
for (i,item) in self.viewArray.enumerated() {
if i>=start&&i<=end {
if item.isEqual(startItem) {
item.changeState(state: .end)
}else{
item.changeState(state: .normal)
}
lastItemDict.removeAll()
}
}
//判斷特殊情況的顏色改變，只有兩個(gè)item的時(shí)候全部改為end狀態(tài)
if (end-start) == 1 {
usleep(sleepTime)
viewArray[end].changeState(state: .end)
}
// 遞歸調(diào)用
self.quickSort(start: start, end: storeIndex-2)
self.quickSort(start: storeIndex, end: end)
}
接下來(lái)只需要在func startSort里面調(diào)用就好了
// MARK: - QuckSort
func startSort(){
DispatchQueue.global().async {
self.quickSort(start: 0, end: self.viewArray.count-1)
// 提供給viewController 的回調(diào)
if self.finishAction != nil{
self.finishAction?()
}
usleep(sleepTime)
for item in self.viewArray{
item.changeState(state: .normal)
}
}
}
結(jié)束語(yǔ)
通過(guò)寫(xiě)完演示動(dòng)畫(huà)之后相信你一定不會(huì)在覺(jué)得算法枯燥了呐伞，無(wú)趣了吧敌卓。
后期如果有時(shí)間接著分享關(guān)于算法的趣味學(xué)習(xí)
Thank You
