App 開發(fā)是對計算機(jī)語言的使用趣效，當(dāng)然也需要設(shè)計算法的使用眼耀。雖然作為iOS開發(fā),似乎接觸的更多是界面和數(shù)據(jù)的處理哮伟， 但是妄帘，在實際開發(fā)中， 算法的使用能更高效的處理數(shù)據(jù)鬼廓，同時算法能幫助我們更好的了解底層語言致盟。
- 冒泡排序
- 選擇排序
- 插入排序
- 快速排序
- 堆排序
- 希爾排序
- 歸并排序
-
基數(shù)排序
排序算法.png
- 冒泡排序代碼如下：
// 冒泡排序 O（n^2）
func bubbleSort(arr: inout[Int]) -> [Int] {
for i in 0..<arr.count {
for j in i + 1..<arr.count {
if arr[i] > arr[j] {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
print(arr)
}
print("--------最終結(jié)果: \(arr)")
return arr
}
2 . 選擇排序算法代碼如下：
// 選擇排序 時間復(fù)雜度 O（n^2）
func selectSort(arr: inout[Int]) -> [Int] {
for i in 0..<arr.count {
var minIndex = i
for j in i + 1..<arr.count {
if arr[minIndex] > arr[j] {
minIndex = j
}
}
if i != minIndex{
let temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
print(arr)
}
return arr
}
- 插入排序算法如下：
// 插入排序
func insertSort(arr: inout[Int]) -> [Int] {
for i in 1..<arr.count {
let temp = arr[i]
var j = i
while j > 0, temp < arr[j - 1]{
arr[j] = arr[j - 1]
j -= 1
}
arr[j] = temp
print(arr)
}
return arr
}
- 快速排序算法如下：
// 快速排序
func partition(arr: inout[Int], left: Int, right: Int) -> Int {
var left = left
var right = right
let pivot = arr[left]
while left < right {
while left < right, arr[right] >= pivot{
right -= 1
}
arr[left] = arr[right]
while left < right, arr[left] < pivot{
left += 1
}
arr[right] = arr[left]
}
arr[left] = pivot
print(arr)
return left
}
func quickSort(arr: inout[Int], left: Int, right: Int){
guard left <= right else {
return
}
let prvotIndex = partition(arr: &arr, left: left, right: right)
quickSort(arr: &arr, left: left, right: prvotIndex - 1)
quickSort(arr: &arr, left: prvotIndex + 1, right: right)
}
5 . 堆排序：
// 堆排序
func maxHeapify(arr: inout[Int], index: Int, size: Int){
var i = index
while true {
var iMax = i
let iLeft = 2 * i + 1;
let iRight = 2 * i + 2;
if iLeft < size, arr[i] < arr[iLeft] {
iMax = iLeft
}
if iRight < size, arr[iMax] < arr[iRight] {
iMax = iRight
}
if iMax != i {
let temp = arr[iMax]
arr[iMax] = arr[i]
arr[i] = temp
i = iMax
}else{
break
}
}
}
func heapSoft (arr: inout[Int]) {
if arr.count <= 1 {
return
}
let lastParent = arr.count / 2 - 1
for i in (0...lastParent).reversed() {
maxHeapify(arr: &arr, index: i, size: arr.count)
}
print(arr)
for i in (1...arr.count-1).reversed() {
let temp = arr[0]
arr[0] = arr[i]
arr[i] = temp
maxHeapify(arr: &arr, index: 0, size: i)
}
print(arr)
}
- 希爾（shell）排序：
// 希爾排序
func shellSort(arr: inout[Int]) {
var gap = arr.count / 2
while gap >= 1 {
var i = gap
while i < arr.count {
let temp = arr[i]
var j = i - gap
while j >= 0, temp < arr[j] {
arr[j + gap] = arr[j]
j -= gap
}
if j != (i - gap){
arr[j + gap] = temp
}
i += 1
print(arr)
}
gap = gap / 2
}
}
