首页 > 代码库 > Swift的排序算法总结
Swift的排序算法总结
下面让我们一起来见识一下swift中基于Array的扩展的冒泡排序，选择排序和快速排序吧。
1.冒泡排序
冒泡排序再基础不过了，这里就不再讲其原理了，实在不会可以看下百度百科冒泡排序
既然冒泡排序避免不了数组中两个数据交换，先写一个交换函数
// 交换数组中i和j两个位置的数据
extension Array {
fileprivate mutating func
swap(i:Int,j:Int) {
let temp = self[i]
self[i] = self[j]
self[j] = temp
}
}
下面就是排序了也很简单就不多解释了
//
MARK: - 冒泡排序
/**
* 通过与相邻元素的比较和交换，把小的数交换到最前面。
*/
extension Array where
Element:Comparable {
mutating func bubbleSort() {
for i in 0..<self.count-1 {
for j in (i+1...self.count-1).reversed()
{
// 后者小于前者，交换位置，即小的往上升大的往下沉
if self[j] < self[j-1] {
swap(i: j, j: j-1)
}
}
}
}
}
因为是排序，所以元素必须满足协议是可比较的。
下面快速排序和选择排序也是同样的道理。
2.快速排序
/** 快速排序的算法思想
* 一趟快速排序的算法是：
* 1、设置两个变量i、j，排序开始的时候：i=0，j=N-1；
* 2、以第一个数组元素作为基准数据，赋值给key，即key=A[0]；
* 3、从j开始向前搜索，即由后开始向前搜索(j减1)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
* 4、从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
* 5、重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，
* 使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。
* 另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
*/
extension Array where Element:Comparable {
private mutating func quickPartition(left:Int, right:Int)->Int {
var right = right
var left = left
// 记录哪个是基准数
let base = self[left]
// 记录基准数位置
let baseIndex = left
// 先从右边往左边扫描，找到第一个比base要小的数，但是不能与left相遇
while left < right
&& self[right] >= base {
right = right-1
}
// 再从左边往右边扫描，找到第一个比base还要大的数，但是不能与right相遇
while left < right
&& self[left] <= base {
left = left+1
}
// 交换 左边比base大的数和右边比base小的数
swap(i: left,j: right)
// 交换左边比base大的数和基准数
swap(i: baseIndex,j: left)
// 返回新的基准数
return left
}
/// 快速排序
/// - Parameters:
/// - a: 数组a
/// - left: 左边索引
/// - right: 右边索引
private mutating func quickSort(left: Int, right: Int) {
// 排序完毕，退出递归
if left >= right {
return
}
// 每一趟划分，使左边的比基准小，右边的比基准大，并返回新的基准的位置
let baseIndex = quickPartition(left: left, right: right)
// 判断左边是否排完，没排完递归排左边部分
if baseIndex - 1 > left {
quickSort(left: left, right:
baseIndex - 1)
}
// 判断右边是否排完，没排完递归排右边部分
if baseIndex + 1 < right {
quickSort(left: baseIndex + 1, right:
right)
}
}
mutating func quickSort() {
quickSort(left: 0, right: self.count-1)
}
}
3.选择排序
// MARK: - 选择排序
/** 选择排序算法思想
* 每一趟从前往后查找出值最小的索引（下标），最后通过比较是否需要交换。每一趟都将最小的元素交换到最前面。
* 大致过程
* 6, 4, 9, 7, 5（开始）
* 4, 6, 9, 7, 5（第一趟：将最小的4与6交换，使这一趟最小值4放到最前面）
* 4, 5, 9, 7, 6（第二趟：将最小的5与6交换，使这一趟最小值5放到最前面）
* 4, 5, 6, 7, 9（第三趟：将最小的6与9交换，使这一趟最小值6放到最前面）
* 4, 5, 6, 7, 9（第四趟：不需要交换，排序完成）
*/
extension Array where Element:Comparable {
mutating func selectorSort() {
var min = 0
// 只需要n-1趟即可，到最后一趟只有一个元素，一定是最小的了
for i in 0..<self.count-1 {
// 每一趟的开始，假设该趟的第一个元素是最小的
min = i
// 查找该趟有没有更小的，如果找到更小的，则更新最小值的下标
for j in i+1..<self.count-1 {
if self[j] < self[min] {
min = j
}
}
// 如果该趟的第一个元素不是最小的，说明需要交换
if min != i {
swap(i: min, j: i)
}
}
}
}
Swift的排序算法就总结到这里。
如果大家觉得这篇博文整理得不错，就给点个赞吧。 如果在再哪里整理得有疏忽的地方，还希望各位博友的指点。
感谢各位博友对这篇文章的支持哦！！！ 谢谢。
Swift的排序算法总结