欢迎加QQ群： 457236811 ，我们一起来探讨！
一、冒泡排序
定义：
-
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
-
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序算法的原理如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
swift代码：
protocol SortType { // 排序算法协议
func sort(items: Array<Int>) -> Array<Int>
}
class BubbleSort: SortType {
func sort(items: Array<Int>) -> Array<Int> {
print("冒泡排序：时间复杂度 --- o(n^2) ")
var list: Array<Int> = items
for i in 0..<list.count { // 外循环为排序趟数，i个数进行list.count - 1 趟
var j = list.count - 1
while j > i { // 内循环为每趟比较的次数，第i趟比较list.count - i次
if list[j-1] > list[j] { // 比较大小替换位置 （升序为左大于右，降序反之）
let temp = list[j]
list[j] = list[j-1]
list[j-1] = temp
}
j -= 1
}
}
return list
}
}
运行结果：
冒泡排序：时间复杂度 --- o(n^2)
35 37 47 52 58 62 62 72 88 93 99
二、插入排序
定义：
-
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
-
如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
-
是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序算法的原理如下：
1.每一轮插入都会取出无序数列中的第一个元素插入到有序数列中，这个插入的过程其实就是一个比较交换的过程.
- 如果要插入的值比前面的值要小，就要交换，直到不能交换为止.
swift代码：
class InsertSort: SortType {
func sort(items: Array<Int>) -> Array<Int> {
print("\n\n插入排序：时间复杂度 --- o(n^2) ")
var list: Array<Int> = items
for i in 0..<list.count { // 循序无序数列
var j = i
while j > 0 { //遍历有序数列寻找合适的插入
if list[j-1] > list[j] { // 比较大小替换位置 （升序为左大于右，降序反之）
let temp = list[j]
list[j] = list[j-1]
list[j-1] = temp
}
j -= 1
}
}
return list
}
}
运行结果：
插入排序：时间复杂度 --- o(n^2)
35 37 47 52 58 62 62 72 88 93 99
三、希尔排序
定义：
-
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
-
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序算法的原理如下：
1、首先按照增量进行分组，因为我们要排序的数列有11个，增量初始值是step = 11 / 2 = 5。也就是按照增量为5的步长对数组进行分组。在下方第一步中就是按照增量为5的方式进行分组的。我们将为一组的元素使用直线进行相连，分完组后，我们就将组内中的元素进行插入排序。
2、将上一步使用的增量进行缩小，也就是本步骤的step = 5 / 2 = 2。 本部分，就要按照2的增量将上一步排序后的数组进行分组，然后再次将每个组内的数据进行插入排序。
3、再次缩小增量，此刻step = 2 / 2 = 1, 当增量为1时，其实就是我们上一部分的插入排序。将整个数组进行插入排序，然后我们的数组就是有序的了。
swift代码：
class ShellSort: SortType {
func sort(items: Array<Int>) -> Array<Int> {
print("\n\n希尔排序：时间复杂度 --- o(n^3/2)")
var list: Array<Int> = items
var step = list.count / 2 // 增量初始值
while step > 0 {
for i in 0..<items.count {
var j = i + step
while j >= step && j < list.count {
if list[j-step] > list[j] { // 比较大小替换位置 （升序为左大于右，降序反之）
let temp = list[j-step]
list[j-step] = list[j]
list[j] = temp
}
j = j - step // 搜小增量
}
}
step = step / 2
}
return list
}
}
运行结果：
希尔排序：时间复杂度 --- o(n^3/2)
35 37 47 52 58 62 62 72 88 93 99
四、选择排序
定义：
- 选择排序（Selection sort）是一种简单直观的排序算法。
- 它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
- 以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序算法的原理如下：
- 初识状态下，我们整个数组就是无序的，从整个数组中我们找到了最小的元素。然后将其与无序序列第一个元素进行交换。交换后，有序序列中就有了一个值，而无序序列中就少了一个值。
- 重复的从无序序列中选择最小的值进行交换
swift代码：
class SelectionSort: SortType {
func sort(items: Array<Int>) -> Array<Int> {
print("\n\n选择排序：时间复杂度 --- o(n^2)")
var list: Array<Int> = items
for i in 0..<list.count {
var j = i+1
var miniValue = list[i] // 定义一个最小值
var miniIndex = i // 定义最小值的下标
while j < list.count { // 遍历获取最小值
if miniValue > list[j] {
miniValue = list[j]
miniIndex = j
}
j += 1
}
// 与无序表中第一个值交换，让其成为有序表的最后一个值
if miniIndex != i {
let temp = list[i]
list[i] = list[miniIndex]
list[miniIndex] = temp
}
}
return list
}
}
运行结果：
选择排序：时间复杂度 --- o(n^2)
35 37 47 52 58 62 62 72 88 93 99
以上GitHub代码地址
网友评论