App 开发是对计算机语言的使用，当然也需要设计算法的使用。虽然作为iOS开发,似乎接触的更多是界面和数据的处理， 但是，在实际开发中， 算法的使用能更高效的处理数据，同时算法能帮助我们更好的了解底层语言。
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 堆排序
- 希尔排序
- 归并排序
-
基数排序
排序算法.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("--------最终结果: \(arr)")
return arr
}
2 . 选择排序算法代码如下：
// 选择排序 时间复杂度 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
}
}
