理解排序算法

在计算机科学与数学中,一个排序算法是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法(例如搜索算法与合并算法)中是重要的,

算法分析

目的: 找到比较快的算法,完成问题。

  • 算法分析中,通常采用单处理器 将 指定序列 串行执行
  • 通常不考虑缓存 ,虚存
  • 算法的基本符号等不要用错
  • 时间复杂度为旧称,标准叫法为:运行时间 (元操作的运行次数,为O())
  • 在运行时间中,要考虑 最好情况最坏情况,但是通常下主要考虑最坏情况

插入排序

针对小规模的数据排序效果较好,所以在数据不大的时候,可以将一些复杂的问题,简化成插入排序问题,有着较好的效果。

思想:插入排序的核心其实就是插入,遍历一次数组,然后每次遍历到的元素和前面所有的元素比较,直到找到一个大于左边小于右边的位置,然后将元素插入。这样,当前被遍历的元素左边一定是有序的,右边是为排序的元素,遍历完成后,数组就排序完成了。

就地算法,为了避免空间复杂度的增加,最好不要开辟的一个新的内存空间,所以在插入排序中,不要创建一个新的数组存储排序好的数组,可以通过相邻的两个数交换元素,来完成元素的移动,这样就可以模拟出“插入”的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

var list = [0,2,1,7,4,5,8,9,2,4,5,7,1,2,3,4,5,4,5,6]

for (index, value) in list.enumerated() {

if index == 0 {
continue
}

var whileCondition = index - 1
while whileCondition >= 0 {

if value < list[whileCondition] {

let temp = list[whileCondition]
list[whileCondition] = value
list[whileCondition + 1] = temp
whileCondition -= 1
}
else {
break
}
}
}

print("\(list)")

// [0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 7, 7, 8, 9]

时间复杂度O(n^2),最好情况下是O(n)

元素去重 Swif学习总结

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×